前往小程序，Get更优阅读体验！
立即前往
文档建议反馈控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP最新优惠活动
返回腾讯云官网
社区首页 >专栏 >DS：循环队列的实现

DS：循环队列的实现

作者头像
小陈在拼命
发布于 2024-02-21 11:57:20
980
发布于 2024-02-21 11:57:20
举报
文章被收录于专栏：C/C＋＋、数据结构、算法

创作不易，给个三连吧！！

一、前言

对于循环队列，博主也是源自于一道力扣的OJ题

力扣：循环队列的设置

后来我在网上查过，这个循环队列是有自己的应用场景的！！并不是出题者为了出题而产生的，所以我觉得不光要能做会这道题，还得多去探究这道题的不同方式。而且这道题虽然是循环队列，看似好像要把头和尾连起来，但实际上实现过程中是可以不需要的！这也是他非常特别的一点，因此在这我会重点介绍他的数组实现和链式结构实现。

二、数组实现循环队列

怎么用数组去实现循环队列呢？我们来画图研究一下：

2.1 结构体的创建

代码语言：javascript
复制
typedef int QDataType;
typedef struct MyCircularQueue
{  
	QDataType* a;//动态数组
	int capacity;//记录循环队列的容量
	int front;//记录队首
	int rear;//记录队尾
} MyCircularQueue;

2.2 构造一个k长度的队列并返回

根据我们之前的思路，我们要多创建一块空间！！

代码语言：javascript
复制
MyCircularQueue* myCircularQueueCreate(int k) 
{
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	if (obj == NULL)
	{
		perror("malloc obj fail");
		exit(1);
	}
	obj->a = (QDataType*)malloc(sizeof(QDataType) * (k + 1));
	if (obj->a == NULL)
	{
		perror("malloc obj->a fail");
		exit(1);
	}
	obj->front = obj->rear = 0;
	obj->capacity = k;
	return obj;
}

2.3 向循环队列插入一个元素。如果成功插入则返回真。

我们要往循环队列中插入一个元素，那么首先必须确保队列不为满（后面会封装），那我们之前分析过队列不为满的情况是rear指针的下一个位置是front，但是我们要注意一个特殊情况，如下图：

代码语言：javascript
复制
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{
	if (myCircularQueueIsFull(obj))
		return false;
	obj->a[obj->rear] = value;
	obj->rear++;
	obj->rear %= (obj->capacity + 1);
	return true;
}

但是我们要注意的是实际上我们是多开了一个空间！！！%的时候要把多的空间算上

2.4 向循环队列删除一个元素。如果成功删除则返回真。

我们要往循环队列中删除一个元素，那么首先必须确保队列不为空（后面会封装），front++就行了，同样front也会遇到上面这种情况，处理当时一样，++完后%上数组的实际大小

代码语言：javascript
复制
bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
	if (myCircularQueueIsEmpty(obj))
		return false;
	obj->front++;
	obj->front %= (obj->capacity + 1);
	return true;
}

2.5 从队首获取元素。如果队列为空，返回 - 1

直接取头指针就行了

代码语言：javascript
复制
int myCircularQueueFront(MyCircularQueue* obj)
{
	if (myCircularQueueIsEmpty(obj))
		return -1;
	return obj->a[obj->front];
}

2.6 从队尾获取元素。如果队列为空，返回 - 1

要注意rear指针指向的是最后一个元素的下一个位置，所以要取得的话就要找到rear的前一个位置的下标，这里我们不能直接让rear--，因为我们只是获取队列尾的元素，并不能去改变rear的指向，所以我们要算出rear前面那个位置的下标，其实也是一样，利用%的修正，让rear加上数组实际大小-1，然后再%数组的大小，就刚还是rear前面的位置的下标了！！

代码语言：javascript
复制
int myCircularQueueRear(MyCircularQueue* obj) 
{
	if (myCircularQueueIsEmpty(obj))
		return -1;
	return obj->a[(obj->rear + obj->capacity) % (obj->capacity + 1)];
}

2.7 判断循环队列是否为空

代码语言：javascript
复制
bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
	return obj->front == obj->rear;
}

2.8 判断循环队列是否为满

代码语言：javascript
复制
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
	return (obj->rear + 1)%(obj->capacity + 1) ==obj->front;//rear为k的时候正好
}

2.9 销毁循环队列

代码语言：javascript
复制
void myCircularQueueFree(MyCircularQueue* obj)
{
	free(obj->a);//没必要置空，因为obj用不了，obj->a也用不了  front rear k 也没必要释放
	free(obj);
	//obj = NULL;
}

2.10 全部代码

2.10.1 MyCircularQueue.h
代码语言：javascript
复制
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int QDataType;
typedef struct MyCircularQueue
{  
	QDataType* a;//动态数组
	int capacity;//记录循环队列的容量
	int front;//记录队首
	int rear;//记录队尾
} MyCircularQueue;


MyCircularQueue* myCircularQueueCreate(int k);//构造一个k长度的队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value);// 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj);// 向循环队列删除一个元素。如果成功删除则返回真。
int myCircularQueueFront(MyCircularQueue* obj); //从队首获取元素。如果队列为空，返回 - 1 。
int myCircularQueueRear(MyCircularQueue* obj);//从队尾获取元素。如果队列为空，返回 - 1 。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空
bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满
void myCircularQueueFree(MyCircularQueue* obj);//销毁循环队列
2.10.2 MyCircularQueue.c
代码语言：javascript
复制
#include"MyCircularQueue.h"

MyCircularQueue* myCircularQueueCreate(int k) 
{
	MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
	if (obj == NULL)
	{
		perror("malloc obj fail");
		exit(1);
	}
	obj->a = (QDataType*)malloc(sizeof(QDataType) * (k + 1));
	if (obj->a == NULL)
	{
		perror("malloc obj->a fail");
		exit(1);
	}
	obj->front = obj->rear = 0;
	obj->capacity = k;
	return obj;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{
	if (myCircularQueueIsFull(obj))
		return false;
	obj->a[obj->rear] = value;
	obj->rear++;
	obj->rear %= (obj->capacity + 1);
	return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj) 
{
	if (myCircularQueueIsEmpty(obj))
		return false;
	obj->front++;
	obj->front %= (obj->capacity + 1);
	return true;
}

int myCircularQueueFront(MyCircularQueue* obj)
{
	if (myCircularQueueIsEmpty(obj))
		return -1;
	return obj->a[obj->front];
}

int myCircularQueueRear(MyCircularQueue* obj) 
{
	if (myCircularQueueIsEmpty(obj))
		return -1;
	return obj->a[(obj->rear + obj->capacity) % (obj->capacity + 1)];
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj) 
{
	return obj->front == obj->rear;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
	return (obj->rear + 1)%(obj->capacity + 1) ==obj->front;//rear为k的时候正好
}

void myCircularQueueFree(MyCircularQueue* obj)
{
	free(obj->a);//没必要置空，因为obj用不了，obj->a也用不了  front rear k 也没必要释放
	free(obj);
	//obj = NULL;
}

2.11 相关选择题

5.现有一循环队列，其队头指针为front，队尾指针为rear；循环队列长度为N。其队内有效长度为？(假设队头不存放数据)（ ？） A (rear - front + N) % N + 1 B (rear - front + N) % N C (rear - front) % (N + 1) D (rear - front + N) % (N - 1)

答：这题就是根据我们上面那道题的一个变形，所以我们知道肯定是%上长度的，所以可以直接选B

三、链式结构实现循环队列

怎么用链式结构来实现循环队列呢？我们来分析一下：

3.1 结构体的创建

我们按照链式队列的思路，创建一个队列结构体来管理头尾指针，同时加上capacity（容量）和size（有效数据）

代码语言：javascript
复制
typedef int QDataType;
typedef struct QNode
{
	struct QNode* next;//节点
	QDataType val;//数据域
}QNode;

typedef struct MyCircularQueue
{
	QNode* front;//链表的头指针
	QNode* rear;//链表的尾指针
	int capacity;//记录链表的容量
	int size;//记录链表的有效节点
}MyCircularQueue;

3.2 构造一个k长度的队列并返回

代码语言：javascript
复制
MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (obj == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    obj->front = obj->rear = NULL;
    obj->size = 0;
    obj->capacity = k;
    return obj;
}

3.3 向循环队列插入一个元素。如果成功插入则返回真。

代码语言：javascript
复制
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{
    //如果为满了，直接就返回false
    if (myCircularQueueIsFull(obj))
        return false;
    //不满足就创建节点
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->val = value;
    newnode->next = NULL;
    //创建成功，要考虑队列为空和不为空的情况
    if (myCircularQueueIsEmpty(obj))//为空，让新节点成为头
        obj->front = obj->rear = newnode;
    else//不为空，让tail继续往后遍历
    {
        obj->rear->next = newnode;
        obj->rear = newnode;
    }
    obj->size++;
    return true;
}

3.4 向循环队列删除一个元素。如果成功删除则返回真。

代码语言：javascript
复制
bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    //为空就没有删的必要了
    if (myCircularQueueIsEmpty(obj))
        return false;
    //不为空，删除头节点，让下一个节点成为新的头，然后释放掉
    QNode* cur = obj->front->next;
    free(obj->front);
    obj->front = cur;
    obj->size--;
    return true;
}

3.5 从队首获取元素。如果队列为空，返回 - 1

代码语言：javascript
复制
int myCircularQueueFront(MyCircularQueue* obj)
{
    //为空，返回1
    if (myCircularQueueIsEmpty(obj))
        return -1;
    //不为空，就获取头指针的数据
    return obj->front->val;
}

3.6 从队尾获取元素。如果队列为空，返回 - 1

代码语言：javascript
复制
int myCircularQueueRear(MyCircularQueue* obj)
{
    //为空，返回1
    if (myCircularQueueIsEmpty(obj))
        return -1;
    //不为空，就获取尾指针的数据
    return obj->rear->val;
}

3.7 判断循环队列是否为空

代码语言：javascript
复制
bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    return obj->size == 0;
}

3.8 判断循环队列是否为满

代码语言：javascript
复制
bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    return obj->size == obj->capacity;
}

3.9 销毁循环队列

代码语言：javascript
复制
void myCircularQueueFree(MyCircularQueue* obj)
{
    //本质是链表，要一个个释放
    QNode* pcur = obj->front;//用来遍历删除的
    while (pcur)
    {
        QNode* next= pcur->next;
        free(pcur);
        pcur = next;
    }
    free(obj);
}

3.10 全部代码

3.10.1 MyCircularQueue.h
代码语言：javascript
复制
#pragma once
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>

typedef int QDataType;
typedef struct QNode
{
	struct QNode* next;//节点
	QDataType val;//数据域
}QNode;

typedef struct MyCircularQueue
{
	QNode* front;//链表的头指针
	QNode* rear;//链表的尾指针
	int capacity;//记录链表的容量
	int size;//记录链表的有效节点
}MyCircularQueue;

MyCircularQueue* myCircularQueueCreate(int k);//构造一个k长度的队列
bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value);// 向循环队列插入一个元素。如果成功插入则返回真。
bool myCircularQueueDeQueue(MyCircularQueue* obj);// 向循环队列删除一个元素。如果成功删除则返回真。
int myCircularQueueFront(MyCircularQueue* obj); //从队首获取元素。如果队列为空，返回 - 1 。
int myCircularQueueRear(MyCircularQueue* obj);//从队尾获取元素。如果队列为空，返回 - 1 。
bool myCircularQueueIsEmpty(MyCircularQueue* obj);//判断循环队列是否为空
bool myCircularQueueIsFull(MyCircularQueue* obj);//判断循环队列是否为满
void myCircularQueueFree(MyCircularQueue* obj);//销毁循环队列
3.10.2 MyCircularQueue.c
代码语言：javascript
复制
MyCircularQueue* myCircularQueueCreate(int k)
{
    MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));
    if (obj == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    obj->front = obj->rear = NULL;
    obj->size = 0;
    obj->capacity = k;
}

bool myCircularQueueEnQueue(MyCircularQueue* obj, QDataType value)
{
    //如果为满了，直接就返回false
    if (myCircularQueueIsFull(obj))
        return false;
    //不满足就创建节点
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->val = value;
    newnode->next = NULL;
    //创建成功，要考虑队列为空和不为空的情况
    if (myCircularQueueIsEmpty(obj))//为空，让新节点成为头
        obj->front = obj->rear = newnode;
    else//不为空，让tail继续往后遍历
    {
        obj->rear->next = newnode;
        obj->rear = newnode;
    }
    obj->size++;
    return true;
}

bool myCircularQueueDeQueue(MyCircularQueue* obj)
{
    //为空就没有删的必要了
    if (myCircularQueueIsEmpty(obj))
        return false;
    //不为空，删除头节点，让下一个节点成为新的头，然后释放掉
    QNode* cur = obj->front->next;
    free(obj->front);
    obj->front = cur;
    obj->size--;
    return true;
}

int myCircularQueueFront(MyCircularQueue* obj)
{
    //为空，返回1
    if (myCircularQueueIsEmpty(obj))
        return -1;
    //不为空，就获取头指针的数据
    return obj->front->val;
}

int myCircularQueueRear(MyCircularQueue* obj)
{
    //为空，返回1
    if (myCircularQueueIsEmpty(obj))
        return -1;
    //不为空，就获取尾指针的数据
    return obj->rear->val;
}

bool myCircularQueueIsEmpty(MyCircularQueue* obj)
{
    return obj->size == 0;
}

bool myCircularQueueIsFull(MyCircularQueue* obj)
{
    return obj->size == obj->capacity;
}

void myCircularQueueFree(MyCircularQueue* obj)
{
    //本质是链表，要一个个释放
    QNode* pcur = obj->front;//用来遍历删除的
    while (pcur)
    {
        QNode* next= pcur->next;
        free(pcur);
        pcur = next;
    }
    free(obj);
}

四、总结

我们会发现，在这边无论是用数组实现和链表实现，本质上我们只是从逻辑层次上把它认为是相连的，但是物理层次上并没有把它连在一起，虽然链表是可以做到相连的，但是相连的话会比较复杂，不相连我们也可以解决，只要保证我们能够控制得住边界问题就行！！

本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2024-02-20，如有侵权请联系 cloudcommunity@tencent.com 删除
数据
数组
指针
队列
链表

本文分享自 作者个人站点/博客 前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ，欢迎热爱写作的你一起参与！

数据
数组
指针
队列
链表
评论
登录后参与评论
0 条评论
热度
最新
登录 后参与评论
推荐阅读
LV.
文章
0
获赞
0
目录
  • 一、前言
  • 二、数组实现循环队列
    • 2.1 结构体的创建
      • 2.2 构造一个k长度的队列并返回
        • 2.3 向循环队列插入一个元素。如果成功插入则返回真。
          • 2.4 向循环队列删除一个元素。如果成功删除则返回真。
            • 2.5 从队首获取元素。如果队列为空，返回 - 1
              • 2.6 从队尾获取元素。如果队列为空，返回 - 1
                • 2.7 判断循环队列是否为空
                  • 2.8 判断循环队列是否为满
                    • 2.9 销毁循环队列
                      • 2.10 全部代码
                        • 2.10.1 MyCircularQueue.h
                        • 2.10.2 MyCircularQueue.c
                      • 2.11 相关选择题
                      • 三、链式结构实现循环队列
                        • 3.1 结构体的创建
                          • 3.2 构造一个k长度的队列并返回
                            • 3.3 向循环队列插入一个元素。如果成功插入则返回真。
                              • 3.4 向循环队列删除一个元素。如果成功删除则返回真。
                                • 3.5 从队首获取元素。如果队列为空，返回 - 1
                                  • 3.6 从队尾获取元素。如果队列为空，返回 - 1
                                    • 3.7 判断循环队列是否为空
                                      • 3.8 判断循环队列是否为满
                                        • 3.9 销毁循环队列
                                          • 3.10 全部代码
                                            • 3.10.1 MyCircularQueue.h
                                            • 3.10.2 MyCircularQueue.c
                                        • 四、总结
                                        领券

                                        腾讯云开发者

                                        扫码关注腾讯云开发者

                                        扫码关注腾讯云开发者

                                        领取腾讯云代金券

                                        热门产品

                                        热门推荐

                                        更多推荐

                                        Copyright © 2013 - 2024 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有 

                                        深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 深公网安备号 44030502008569

                                        腾讯云计算（北京）有限责任公司 京ICP证150476号 |  京ICP备11018762号 | 京公网安备号11010802020287

                                        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档

                                        Copyright © 2013 - 2024 Tencent Cloud.

                                        All Rights Reserved. 腾讯云 版权所有

                                        登录 后参与评论