-
2020-03-13 22:56:22
循环队列
(一) 要求
假设以数组sequ[m]存放循环队列的元素,同时设变量rear和quelen 分别指示循环队列中队尾元素的位置和内含元素的个数。编写实现该循环队列的入队和出队操作的算法。提示:队空的条件:sq->quelen0;队满的条件:sq->quelenm。
(二)循环队列
定义:为充分利用向量空间,克服”假溢出”现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。这种循环队列可以以单链表的方式来在实际编程应用中来实现, 当然也可以利用顺序表来实现。顺序表就是我们熟悉的数组 eg. sun[] 。
回顾:我们再来回顾一下关于顺序队列的重要知识点。队列通常与栈对应,栈是一种后进先出的单端(尾端)处理的数据结构;那么与之对应的队列是一种先进先出的双端(头尾两端)的数据结构。队列的特点就是在一段进行入队(存储数据)操作,在另一端进行出队(删除数据)操作。
为什么设计循环队列:大家在处理队列的时候,会遇到如下情况。例如说:我们的队列空间能够容纳1000个元素。首先,格格入队1000个元素,队列上溢,此时为“真溢出”。那么现在我们进行出队操作,我们一直出队,一直出队, 知道1000个元素全部被删除,此时我们发现队列仍然处于“上溢”状态,why? 其实原因很简单,在非循环队列当中,无论我们的front指(偏移)到哪里,只要我们的rear指(偏移)向上阙,那么队列就是“满溢”的。这就造成了空间明明还被占据着,但是队列却已经无用武之地的窘境。对于空间有限的计算机来说,这无疑是一种浪费。也不是一个优秀的程序猿想要看到的。所以在这种情况下,循环队列诞生了。循环队列当中的“满溢”只有一种情况,那就是所有数据空降都被占领了。而不会存在非循环队列当中的“假溢出”现象。结构一
typedef struct { datatype sequ[m]; //sequ[]为我们所建立的顺序表(sequence) int front,rear; //front表示队列头的偏移量,rear表示队列的尾的偏移量 }qu;//qu是队列(queue)的缩写
结构二
typedef struct { datatype sequ[m]; //sequ[]为我们所建立的顺序表(sequence) int rear, quelen; //rear表示队列的尾的偏移量,quelen表示的是队列中元素的个数 }qu;//qu是队列(queue)的缩写
(三) 循环队列的算法设计
在上面我们了解了循环队列的数据机构,但是仅仅学会了数据结构还远远不够。我们设计数据结构的目的是为了更好的存储数据,并利用数据。下面我们来看一看关于循环队列我们要掌握哪些最基本的算法(利用数据机构)。
3.1 建立循环队列
//建立队 qu* creatqueue();//函数声明 qu* creatqueue()//函数实现 { qu *sq; sq=(qu*)malloc(sizeof(qu)); return sq; }
3.2 置空队列
//置空队 void setnull(qu*);//函数声明 void setnull(qu *sq)//函数实现 { sq->rear = m - 1; sq->quelen = 0; }
3.3 入队
//入队 void enqueue(qu*, datatype);//函数声明 void enqueue(qu*sq, datatype x)//函数实现 { if (sq->quelen == 5) printf("Errot! The queue will be overflow! \n"); else if((sq->rear+1)==m) { sq->rear = (sq->rear + 1) % m; sq->sequ[sq->rear] = x; sq->quelen++; printf("过5入队成功!\n"); } else { sq->rear++; sq->sequ[sq->rear] = x; sq->quelen++; printf("入队成功!\n"); } }
3.4 出队
//出队 datatype *dequeue(qu*);//函数声明 datatype *dequeue(qu*sq)//函数实现 { datatype sun=0; if (sq->quelen == 0) { printf("Error! The queue will be under flow!\n"); return 0; } else if ((sq->rear + 1) >= sq->quelen) { sq->quelen--; sun = sq->sequ[sq->rear - sq->quelen]; return(&sun); } else // if(sq->rear < sq->quelen) { sq->quelen--; sun = sq->sequ[sq->rear - sq->quelen + m]; return(&sun); } }
3.5 打印队
//打印队 void print(qu*);//函数声明 void print(qu*sq)//函数定义 { if (sq->quelen == 0) printf("Error! The queue is Null!\n"); else if ((sq->rear + 1) >= sq->quelen) { int i = sq->rear + 1 - sq->quelen; for (i; i <= sq->rear; i++) printf("%d ", sq->sequ[i]); } else { int t = sq->rear - sq->quelen + m +1; int time = 1; for (t; time <= (sq->quelen); time++) { printf("%d ", sq->sequ[t]); t++; if (t == m) { t = 0; continue; } else { continue; } } } printf("\n"); }
3.6 完整代码
#include<stdio.h> #include<stdlib.h> #include<malloc.h> #define m 5 //循环队列的结构类型定义 typedef int datatype; typedef struct { datatype sequ[m]; int rear, quelen; }qu; //函数声明 qu* creatqueue(); void setnull(qu*); void enqueue(qu*, datatype); datatype *dequeue(qu*); void print(qu*); //主函数 void main() { qu *sq= creatqueue(); datatype x, *p; int key; setnull(sq); do { printf("1.Enter Queue 2.Delete Queue 3.clc display 4.print queue -1.Quit:"); scanf_s("%d", &key); switch (key) { case 1: printf("Enter the Data:"); scanf_s("%d", &x); enqueue(sq, x); break; case 2: p = dequeue(sq); if (p != NULL) printf("%d\n", *p); break; case 3:system("cls"); break; case 4:print(sq); break; case -1: exit(0); } } while (1); } //建立队 qu* creatqueue() { qu *sq; sq=(qu*)malloc(sizeof(qu)); return sq; } //置空队 void setnull(qu *sq) { sq->rear = m - 1; sq->quelen = 0; } //入队 void enqueue(qu*sq, datatype x) { if (sq->quelen == 5) printf("Errot! The queue will be overflow! \n"); else if((sq->rear+1)==m) { sq->rear = (sq->rear + 1) % m; sq->sequ[sq->rear] = x; sq->quelen++; printf("过5入队成功!\n"); } else { sq->rear++; sq->sequ[sq->rear] = x; sq->quelen++; printf("入队成功!\n"); } } //出队 datatype *dequeue(qu*sq) { datatype sun=0; if (sq->quelen == 0) { printf("Error! The queue will be under flow!\n"); return 0; } else if ((sq->rear + 1) >= sq->quelen) { sq->quelen--; sun = sq->sequ[sq->rear - sq->quelen]; return(&sun); } else // if(sq->rear < sq->quelen) { sq->quelen--; sun = sq->sequ[sq->rear - sq->quelen + m]; return(&sun); } } //打印队列 void print(qu*sq) { if (sq->quelen == 0) printf("Error! The queue is Null!\n"); else if ((sq->rear + 1) >= sq->quelen) { int i = sq->rear + 1 - sq->quelen; for (i; i <= sq->rear; i++) printf("%d ", sq->sequ[i]); } else { int t = sq->rear - sq->quelen + m +1; int time = 1; for (t; time <= (sq->quelen); time++) { printf("%d ", sq->sequ[t]); t++; if (t == m) { t = 0; continue; } else { continue; } } } printf("\n"); }
更多相关内容 -
队列文档之循环队列
2022-05-09 22:28:50循环队列就是将顺序队列臆造成一个环状的空间(实际上不是,只是把它看成是环状的),即把存储队列元素的顺序表从逻辑上视为一个环。循环队列
定义
概念
为了解决顺序队列“假溢出”的缺陷,所以引入了循环队列。
关于顺序队列请参考:顺序队列。
循环队列就是将顺序队列臆造成一个环状的空间(实际上不是,只是把它看成是环状的),即把存储队列元素的顺序表从逻辑上视为一个环。当队头指针
queue.front==MAXSIZE-1
时(即到数组的最后一个位置了),再前进一个位置就自动到 0,这可以利用除法取余运算(%
)来实现。通常采用数组来实现,当然也可以通过链表来实现循环队列。
关于循环队列的状态和操作如下:
- 初始化:
queue.front=0; queue.rear=0;
。
- 入队操作:先将新元素赋予队尾指针所指向的位置,然后队尾指针加一。但循环队列中加一操作与顺序队列有所不同:
queue.rear=(queue.rear+1)%MAXSIZE
。是为了当达到MAXSIZE-1
位置后下一个位置自动到 0 去。 - 出队操作:取出队头指针所指向的位置的元素,然后队头指针加一。但循环队列中加一操作与顺序队列有所不同:
queue.front=(queue.front+1)%MAXSIZE
。 - 队列长度:也跟顺序队列求队列长度有所不同,是:
(queue.rear-queue.front+MAXSIZE)%MAXSIZE
。
循环队列最大的问题就是如何判断队空和队满。之前顺序队列判断队空的条件
queue.front==queue.rear
是无法判断循环队列是队空还是队满的,因为循环队列队空和队满时queue.front==queue.rear
条件都成立。如图:为什么循环队列队满时,队头指针
front
和队尾指针rear
会重合呢?如图所示,因为队头指针始终指向队头元素,而队尾指针指向队尾元素的下一个位置,所以当队满时,它们会重合。所以queue.front==queue.rear
是无法作为单独判断队空和队满条件。因此,为了区分是队空还是队满的清空,有三种处理方式:
- 第一种,牺牲一个单元来区分队空和队满,入队时少用一个队列单元,这是一种比较普通的做法,本篇也是采用的这种做法。约定以队头指针在队尾指针的下一位置作为队满的标志。如图所示:
- 队满条件:
(queue.rear+1)%MAXSIZE==queue.front
。 - 队空条件:
queue.front==queue.rear
。 - 队列种的元素个数:
(queue.rear-queue.front+MAXSIZE)%MAXSIZE
。
- 队满条件:
-
结构体类型中增设表示元素个数的数据成员
size
。这两种情况都有queue.front==queue.rear
,但不再作为判空或判满的条件。- 队满条件:
queue.size==MAXSIZE
。 - 队空条件:
queue.size==0
。
- 队满条件:
-
结构体类型中增设
tag
数据成员,用来区分是队满还是队空。约定 tag 等于 0 时,若因删除导致queue.front==queue.rear
则为队空;当 tag 等于 1 时,若因插入导致queue.front==queue.rear
则为队满。有一道练习题就是实现该队列:Example004-设计一个循环队列,用 front 和 rear 分别作为队头和队尾指针,另外用一个标志 tag 表示队列是空还是不空。- 队满条件:
queue.tag==1 && queue.front==queue.rear
。 - 队空条件:
queue.tag==0 && queue.front==queue.rear
。
- 队满条件:
结构体
/** * 循环队列结构体定义 */ typedef struct { /** * 数据域,存储循环队列中的数据 */ int data[MAXSIZE]; /** * 指针域,存储循环队列中队头元素的位置 */ int front; /** * 指针域,存储循环队列中队尾元素的位置 */ int rear; } CircularQueue;
特点
front
表示队头指针,实际上就是数组下标,指向顺序队列的队头元素;rear
表示队尾指针,指向顺序队列的队尾元素的下一个位置。- 如果队尾指针
rear
到达MAXSIZE-1
位置,则会自动跳到 0 位置。 - 循环队列能充分利用队列中的空余空间,直到队列中所有空间(除了用来判断队空或队满的一个空间)都被使用。
基本操作
注,完整代码请参考:
概述
循环队列的常见操作如下:
void init(CircularQueue *queue)
:初始化循环队列。其中queue
表示循环队列。int isEmpty(CircularQueue queue)
:判断循环队列是否为空。其中queue
表示循环队列。如果循环队列为空则返回 1,否则返回 0。int isFull(CircularQueue queue)
:判断循环队列是否已满。其中queue
表示循环队列。如果循环队列已满则返回 1,否则返回 0。int enQueue(CircularQueue *queue, int ele)
:将元素入队。其中queue
表示循环队列;ele
表示待入队的元素。如果循环队列已满则不能入队,返回 0 表示入队失败;否则如果入队成功则返回 1。int deQueue(CircularQueue *queue, int *ele)
:将元素出队。其中queue
表示循环队列;ele
用来保存出队的元素。如果循环队列为空则不能出队,返回 0 表示出队失败;否则如果出队成功则返回 1。int size(CircularQueue queue)
:获取循环队列中的元素个数。其中queue
表示循环队列。返回循环队列中的元素个数。int getFront(CircularQueue queue, int *ele)
:读取循环队列中的队头元素。其中queue
表示循环队列;ele
用来保存队头的元素。如果队列为空则无法获取队头元素则返回 0,否则返回 1。int getRear(CircularQueue queue, int *ele)
:读取循环队列中的队尾元素。其中queue
表示循环队列;ele
用来保存队尾的元素。如果队列为空则无法获取队尾元素则返回 0,否则返回 1。void clear(CircularQueue *queue)
:清空循环队列中所有元素。其中queue
表示循环队列。void print(CircularQueue queue)
:打印循环队列中所有元素。其中queue
表示循环队列。
init
初始化循环队列。
实现步骤:
- 将队头指针
front
和队尾指针rear
都指向 0,表示空队列。
实现代码如下:
/** * 初始化循环队列 * @param queue 待初始化的循环队列 */ void init(CircularQueue *queue) { // 循环队列初始时,队头指针和队尾指针仍然都指向 0,表示是空队列 queue->front = 0; queue->rear = 0; }
isEmpty
判断循环队列是否为空。如果为空则返回 1,否则返回 0 表示非空。
实现步骤:
- 判断队头指针
front
和队尾指针rear
是否指向同一位置,即queue.front==queue.rear
。
实现代码如下:
/** * 判断循环队列是否为空 * @param queue 循环队列 * @return 如果循环队列为空则返回 1,否则返回 0 表示非空 */ int isEmpty(CircularQueue queue) { // 只要队头指针和队尾指针相等,那么表示循环队列为空,无论指针在哪个位置 if (queue.rear == queue.front) { return 1; } else { return 0; } }
isFull
判断循环队列是否已经满队。如果已满则返回 1,否则返回 0 表示未满。
实现步骤:
- 如果满足条件
(queue.rear+1)%MAXSIZE==queue.front
,那么就认为队满。
实现代码如下:
/** * 判断循环队列是否已满 * @param queue 循环队列 * @return 如果循环队列已满则返回 1,否则返回 0 表示队列非满 */ int isFull(CircularQueue queue) { // 队尾指针再加上一,然后对 MAXSIZE 取余,如果等于队头指针,那么表示队满 if ((queue.rear + 1) % MAXSIZE == queue.front) { return 1; } else { return 0; } }
enQueue
将元素入队。如果队未满才能入队,否则返回 0 表示入队失败。如果入队成功则返回 1。以
queue=[a, b, c]; ele=x
为例如图:实现步骤:
- 参数校验,如果队满则不能入队。返回 0 表示入队失败。
- 先进行赋值,将队尾指针所指向的位置赋予
ele
值。 - 接着队尾指针加一,指向队尾元素的下一个位置。保证队尾指针始终指向队尾元素的下一位置。
- 返回 1 表示入队成功。
实现代码如下:
/** * 将元素入队 * @param queue 循环队列 * @param ele 指定元素 * @return 如果队列已满则不能入队返回 0 表示入队失败;否则返回 1 表示入队成功 */ int enQueue(CircularQueue *queue, int ele) { // 0.参数校验,如果队满则不能入队 if ((queue->rear + 1) % MAXSIZE == queue->front) { return 0; } // 1.将元素入队 // 1.1 先进行赋值,即将新元素填充到队尾指针指向的位置。因为队尾指针指向队尾元素的下一个位置 queue->data[queue->rear] = ele; // 1.2 然后将队尾指针加一。因为是循环队列,如果到了队尾,那么又要从 0 开始,所以加一后需要对 MAXSIZE 进行取余 queue->rear = (queue->rear + 1) % MAXSIZE; return 1; }
deQueue
将元素出队。如果队空则不能出队,返回 0 表示出队失败。将出队元素保存到 ele,并返回 1 表示出队成功。以
queue=[a, b, c, d, e, f, g]
为例如图所示:实现步骤:
- 参数校验,如果队空,则不能出队。返回 0 表示出队失败。
- 将元素出队。用
ele
保存队头指针所指向的元素。 - 然后将队头指针加一,保证队头指针始终指向队头元素。
- 返回 1 表示出队成功。
实现代码如下:
/** * 将元素出队 * @param queue 循环队列 * @param ele 用来保存出队的元素 * @return 如果队空则不能出队则将返回 0 表示出队失败;否则返回 1 表示出队成功 */ int deQueue(CircularQueue *queue, int *ele) { // 0.参数校验,如果队空则不能出队 if (queue->rear == queue->front) { return 0; } // 1.将队头元素出队 // 1.1 用 ele 保存队头指针所指向的元素 *ele = queue->data[queue->front]; // 1.2 将队头指针加一,表示删除队头元素。因为是循环队列,所以要对 MAXSIZE 取余 queue->front = (queue->front + 1) % MAXSIZE; // 1.3 返回 1 表示出队成功 return 1; }
size
获取循环队列中实际的元素个数。
实现步骤:
- 循环队列的元素个数即
(rear-front+MAXSIZE)%MAXISZE
。
实现代码如下:
/** * 获取循环队列中的元素个数 * @param queue 循环队列 * @return 队列中的元素个数 */ int size(CircularQueue queue) { // 如果是顺序队列,则元素个数是 rear-front // 如果是循环队列,则元素个数是 (rear-front+MAXSIZE)%MAXSIZE return (queue.rear - queue.front + MAXSIZE) % MAXSIZE; }
getFront
读取队头元素,但并不出队。如果队空则不能读取,则返回 0,否则用 ele 保存队头元素,返回 1 表示读取成功。
实现步骤:
- 参数校验,如果队空则没有队头元素,自然也无法获取。返回 0 表示读取失败。
- 直接读取队头指针所指向的元素。因为队头指针始终指向队头元素。
实现代码如下:
/** * 获取循环队列的队头元素 * @param queue 循环队列 * @param ele 用来保存队头元素 * @return 如果队列为空则返回 0 表示获取失败;否则返回 1 表示获取成功。 */ int getFront(CircularQueue queue, int *ele) { // 0.参数校验,如果队列为空则没有队头元素,自然无法获取,所以返回 0 表示获取失败 if (queue.rear == queue.front) { return 0; } // 1.用 ele 保存队头元素,即队头指针所指向的元素 *ele = queue.data[queue.front]; return 1; }
getRear
读取循环队列的队尾元素。如果循环队空为空则返回 0 表示读取失败。否则用
ele
保存队尾元素,并返回 1 读取成功。实现步骤:
- 参数校验,如果队空,则不能读取队尾元素。返回 0 表示读取失败。
- 读取队尾指针所指向位置的前一个位置的元素,用 ele 保存。因为队尾指针始终指向队尾元素的下一个位置,所以要读取队尾元素,需要读取到队尾指针的前一个位置的元素。但并不是队尾指针单纯的减一,因为是循环队列。
- 返回 1 表示读取成功。
实现代码如下:
/** * 获取循环队列中的队尾元素 * @param queue 循环队列 * @param ele 用来保存队尾元素 * @return 如果队列为空则返回 0 表示获取失败;否则返回 1 表示获取成功。 */ int getRear(CircularQueue queue, int *ele) { // 0.参数校验,如果队列为空则没有队尾元素,自然无法获取,所以返回 0 表示获取失败 if (queue.rear == queue.front) { return 0; } // 1.用 ele 保存队尾元素,由于队尾指针指向队尾元素的下一个位置,所以要队尾指针减一 *ele = queue.data[(queue.rear - 1 + MAXSIZE) % MAXSIZE]; return 1; }
clear
清空循环队列。
实现步骤:
- 将双端队列的队头指针
front
和队尾指针rear
都指向 0,表示空队列。但实际上队列中原有的元素仍然存在,并没有被重置为某个值。
实现代码如下:
/** * 清空循环队列 * @param queue 循环队列 */ void clear(CircularQueue *queue) { // 即将队头指针和队尾指针都指向 0,表示恢复循环队列的初始状态,即空表 queue->front = 0; queue->rear = 0; }
print
打印循环队列中的所有有效元素。
实现步骤:
- 从队头指针开始扫描整个循环队列,直到队尾指针结束,但不包括队尾指针所指向的元素。
实现代码如下:
/** * 打印循环队列中从队头到队尾的所有元素 * @param queue 循环队列 */ void print(CircularQueue queue) { printf("["); int front = queue.front; while (front != queue.rear) { printf("%d", queue.data[front]); if (front != (queue.rear - 1 + MAXSIZE) % MAXSIZE) { printf(", "); } front = (front + 1) % MAXSIZE; } printf("]\n"); }
注意事项
无。
练习题
- 初始化:
-
C语言循环队列的表示与实现实例详解
2021-01-01 15:24:58在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。 循环队列可以更简单的防止伪溢出的发生,但是队列大小是固定的。 2.实例代码: /* 队列的... -
数据结构——循环队列
2022-03-28 19:10:43概念 基于队列的先进先出的...但是使用循环队列,我们能使用这些空间去存储新的值。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/design-circular-queue 题目 设置循环队列 注意事项 .目录
概念
基于队列的先进先出的原则,在确定了队列长度的前提下,另队列首尾相接而实现的一种结构。
循环队列的作用
循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/design-circular-queue题目
注意事项
单纯把链表的首尾相接就可以吗?
那么我们来想想这样一个问题:空的循环队列是什么样的?
我们规定将头指针放在首元素的位置,尾指针放到尾元素的下一个位置,那空队列就是头指针和尾指针指向同一个位置。
那么,满的循环链表又是什么样的呢?
尾指针放在a8元素的后面,恰好又与空链表的指向完全相同。
那我们怎么解决呢?
难道在结构体放一个变量判断它是否以满吗?不是不可以,但稍微有点“笨重”。
所以我们不妨让队列多添加一个位置,这个位置不放任何元素,仅仅是为了区别空与满:
题解
与通常队列相似,循环队列同样也可以用链表与顺序表两种方式实现
用顺序表的实现
typedef int CQDataType; typedef struct { CQDataType* cq; int head; int tail; int size; } myCircularQueueEnQueue; bool myCircularQueueEnQueueIsFull(myCircularQueueEnQueue* obj); bool myCircularQueueEnQueueIsEmpty(myCircularQueueEnQueue* obj); //构造器,设置队列长度为 k myCircularQueueEnQueue* myCircularQueueEnQueueCreate(int k) { myCircularQueueEnQueue* newCQ = (myCircularQueueEnQueue*)malloc(sizeof(myCircularQueueEnQueue)); assert(newCQ); CQDataType* newcq = (CQDataType*)malloc(sizeof(CQDataType) * (k + 1)); assert(newcq); newCQ->size = k; newCQ->cq = newcq; newCQ->head = 0; newCQ->tail = 0; return newCQ; } //向循环队列插入一个元素。如果成功插入则返回真 bool myCircularQueueEnQueueEnQueue(myCircularQueueEnQueue* obj, int value) { if (myCircularQueueEnQueueIsFull(obj)) { return 0; } obj->cq[obj->tail] = value; obj->tail = (obj->tail + 1) % (obj->size + 1); return 1; } //从循环队列中删除一个元素。如果成功删除则返回真 bool myCircularQueueEnQueueDeQueue(myCircularQueueEnQueue* obj) { if (myCircularQueueEnQueueIsEmpty(obj)) { return 0; } //obj->head = ((obj->size + 1) + (obj->tail - 1)) % (obj->size + 1); obj->head = (obj->head + 1) % (obj->size + 1); return 1; } //从队首获取元素。如果队列为空,返回 -1 int myCircularQueueEnQueueFront(myCircularQueueEnQueue* obj) { if (obj->head == obj->tail) { return -1; } else { return obj->cq[obj->head]; } } // 获取队尾元素。如果队列为空,返回 -1 int myCircularQueueEnQueueRear(myCircularQueueEnQueue* obj) { if (obj->head == obj->tail) { return -1; } else { return obj->cq[((obj->size + 1) + (obj->tail - 1)) % (obj->size + 1)]; } } //检查循环队列是否为空 bool myCircularQueueEnQueueIsEmpty(myCircularQueueEnQueue* obj) { return obj->head == obj->tail; } //检查循环队列是否已满 bool myCircularQueueEnQueueIsFull(myCircularQueueEnQueue* obj) { return (obj->tail + 1) % (obj->size + 1) == obj->head; } //释放 void myCircularQueueEnQueueFree(myCircularQueueEnQueue* obj) { free(obj->cq); free(obj); }
用链表的实现
typedef int CQDataType; typedef struct CQListNode { struct CQListNode* _next; CQDataType _data; }CQNode; typedef struct { CQNode* _head; CQNode* _tail; int size; } MyCircularQueue; bool myCircularQueueIsFull(MyCircularQueue* obj); bool myCircularQueueIsEmpty(MyCircularQueue* obj); MyCircularQueue* myCircularQueueCreate(int k) { MyCircularQueue* CQ = (MyCircularQueue*)malloc(sizeof(MyCircularQueue)); assert(CQ); CQ->size = k; CQNode* head = (CQNode*)malloc(sizeof(CQNode)); assert(head); CQNode* cur = CQ->_head = CQ->_tail = head; for (int i = 0; i < k; i++)//加上面共k+1个节点 { CQNode* cq = (CQNode*)malloc(sizeof(CQNode)); assert(cq); cur->_next = cq; cq->_next = NULL; cur = cur->_next; } cur->_next = head; return CQ; } bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) { if (!myCircularQueueIsFull(obj)) { obj->_tail->_data = value; obj->_tail = obj->_tail->_next; return 1; } else { return 0; } } bool myCircularQueueDeQueue(MyCircularQueue* obj) { if (!myCircularQueueIsEmpty(obj)) { obj->_head = obj->_head->_next; return 1; } else { return 0; } } int myCircularQueueFront(MyCircularQueue* obj) { if (!myCircularQueueIsEmpty(obj)) return obj->_head->_data; else return -1; } int myCircularQueueRear(MyCircularQueue* obj) { if (!myCircularQueueIsEmpty(obj)) { CQNode* cur = obj->_head; while (cur->_next != obj->_tail) { cur = cur->_next; } return cur->_data; } else return -1; } bool myCircularQueueIsEmpty(MyCircularQueue* obj) { return obj->_head == obj->_tail; } bool myCircularQueueIsFull(MyCircularQueue* obj) { return obj->_tail->_next == obj->_head; } void myCircularQueueFree(MyCircularQueue* obj) { /*CQListNode* cur = obj->_head; while(cur->_next!=cur)*/ CQNode* cur = obj->_head; CQNode* next = NULL; for (int i = 0; i < obj->size; i++) { next = cur->_next; free(cur); cur = next; } free(obj); }
-
为什么循环队列要浪费一个存储空间
2022-01-09 17:56:30单向队列会出现“假溢出”问题,而循环队列却能解决“假溢出”问题。常规的循环队列实现方法需要浪费一个存储空间,那么如果不浪费一个空间是否也能实现一个循环队列呢?什么是队列
队列和数组,链表,栈一样都是属于线性数据结构,而队列又和栈比较相似,都属于操作受限的数据结构,其中栈是“后入先出”,而队列是“先进先出”。
和栈一样,队列也仅有两个基本操作:入队和出队(栈则是入栈和出栈)。往队列中放元素称之为入队,往队列中取元素称之为出队,然而相对于栈来说,队列又会复杂一点。
队列中通常需要定义两个指针:
head
和tail
(当然,也有称之为:front
和rear
)分别用来表示头指针和尾指针。初始化队列时,head
和tail
相等,当有元素入队时,tail
指针往后移动一位,当有元素出队时,head
指针往后移动一位。队空和队满
根据上面的队列初始化和入队出队的过程,我们可以得到以下三个关系:
- 初始化队列时:
head=tail=-1
(这里也可以设置为0
,看具体实现)。 - 队列满时:
tail=size-1
(其中size
为初始化队列时队列的大小)。 - 队列空时:
head=tail
(比如上图中的第一和第三个队列)。
队列的实现
和栈一样,队列也可以通过数组或者链表来实现,通过数组来实现的队列我们称之为“顺序队列”,通过链表实现的队列称之为“链式队列”。
数组实现队列
package com.lonely.wolf.note.queue; /** * 基于数组实现自定义单向队列。FIFO(first in first out)先进先出 * @author lonely_wolf * @version 1.0 * @date 2021/12/26 * @since jdk1.8 */ public class MyQueueByArray<E> { public static void main(String[] args) { MyQueueByArray myQueue = new MyQueueByArray(3); System.out.println("队列是否为空:" + myQueue.isEmpty());//输出:true myQueue.enqueue(1); myQueue.enqueue(2); myQueue.enqueue(3); System.out.println("队列是否已满:" + myQueue.isFull());//输出:true System.out.println("第1次出队:" + myQueue.dequeue());//输出:1 System.out.println("第2次出队:" + myQueue.dequeue());//输出:2 System.out.println("第3次出队:" + myQueue.dequeue());//输出:3 System.out.println("队列是否为空:" + myQueue.isEmpty());//输出:true System.out.println("队列是否已满:" + myQueue.isFull());//输出:true } private Object[] data; private int size;//队列长度 private int head;//队列头部 private int tail;//队列尾部 public MyQueueByArray(int size) {//初始化 this.size = size; data = new Object[size]; head = -1; tail = -1; } /** * tail=size-1 表示队列已满 * @return */ public boolean isFull(){ return tail == size - 1; } /** * head=tail表示队列为空 * @return */ public boolean isEmpty(){ return head == tail; } /** * 元素入队,tail指针后移一位 * @param e * @return */ public boolean enqueue (E e){ if (isFull()){ return false; } data[++tail] = e;//tail 指针后移 return true; } /** * 元素出丢 * @return */ public E dequeue (){ if (isEmpty()){ return null; } E e = (E)data[++head];//出队 return e; } }
链表实现队列
有了上面基于数组实现的简单队列例子,基于链表实现队列相信大家也能写出来,如果用链表实现队列,我们们同样需要
head
指针和tail
指针。其中head
指向链表的第一个结点,tail
指向最后一个结点。入队时:
tail.next = newNode; tail = tail.next;
出队时:
head = head.next;
假溢出问题
我们回到上面数组实现的例子中,我们发现最后的两个输出语句两个都是
true
,也就是队列又是空的又是满的,这看起来是一个自相矛盾的事情却在队列里面出现了,我们来看看这时候队列的示意图:通过上图中我们发现,因为
tail=size-1
,所以队列是满的;而此时又同时满足:head=tail
,所以根据上面队空的条件,我们又可以得到当前队列是空的,也就是当前队列是没有元素的。这时候我们已经无法继续入队了,但是这时候队列中的其实是有空间的,有空间却不能被利用,这就是单向队列的“假溢出”问题。那么如何解决这个问题呢?解决这个问题有两个思路。
- 思路一
前面我们学习数组的时候提到了,当数组中删除一个元素,那么这个位置之后的所有元素都需要往前移动一位,所以队列中也是同理,假如我们用数组来实现的话,当元素出队时,我们把所有元素都往前移,不过这样因为每次都需要搬移数据,导致入队的时间复杂度是
O(n)
。- 思路二
因为搬移数据会影响到入队效率,那么如何不搬移数据又能将队列的空闲空间利用起来呢?答案也很简单,那就是当再次有新元素入队时,我们把
tail
指针又重新移动到队列的最开头位置,这样也能避免出现“假溢出”问题,同时时间复杂度仍然保持为O(1)
。循环队列
上面提到的第二种思路来解决单向队列的“假溢出”问题,实际上就构成了一个循环队列。而上面单向队列判断当前队列是否队满时仅需要满足
tail=size-1
即可,但是循环队列肯定不行,因为当tail=size-1
时继续添加元素,tail
可能可以移动到size=0
的位置,所以如果要实现循环队列最关键还是需要确定好队空和队满的条件。队空和队满
在循环队列中,当初始化队列时,一般会将其设置为
0
,而队空条件仍然是head=tail
,循环队列最关键的是如何确定队满条件。下图是初始化一个长度为
6
的队列以及连续入队5
个元素后的循环队列中head
,tail
指针示意图:上图中第二个队列表示的是入队
5
个元素之后tail
指针的位置,这时候如果继续入队,那么tail
只能指向队列开头也就是元素1
所在的位置,此时会得到下面这个示意图的场景:
这时候发现
head=tail
,和队空时的条件冲突了,那么如何解决这个问题呢?主要有三种解决办法:- 当
(tail+1)%size=head
时就表示队列已满,这时候tail
所在位置为空,所以会浪费一个空间(也就是第一幅图中第二个队列的场景就算队列已满)。 - 新增一个容量
capacity
字段,并进行维护,当capacity=size
表示队列已满。 - 和第二个办法差不多,我们可以再维护一个标记,或者当
head=tail
时同步判断当前位置是否有元素来判断当前是队空还是队满。
这三种思路我们发现都各有缺点:方法
1
会浪费一个空间;方法2
每次入队和出队时候都需要维护capacity
字段;方法3
就是不论队列空或者队列满时都要多一次判断方式。相互比较之下,其实方法一的思路就是空间换时间,而另外两种办法当数据量并发量很大时,多一次判断其实也是会对性能有所影响,常规的循环链表会采用方法
1
进行处理,也就是选择浪费一个空间的方式。当然大家在实际开发过程中也可以自行斟酌。实现循环队列
下面我们就以方法
1
的思路基于数组来实现一个循环队列:package com.lonely.wolf.note.queue; /** * * 实现循环队列 * @author lonely_wolf * @version 1.0 * @date 2021/12/26 * @since jdk1.8 */ public class MyCycleQueueByArray<E> { public static void main(String[] args) { MyCycleQueueByArray cycleQueue = new MyCycleQueueByArray(3); System.out.println("循环队列是否为空:" + cycleQueue.isEmpty());//输出:true System.out.println("1是否入队成功:" + cycleQueue.enqueue(1));//输出:true System.out.println("2是否入队成功:" + cycleQueue.enqueue(2));//输出:true System.out.println("3是否入队成功:" + cycleQueue.enqueue(3));//输出:false System.out.println("循环队列是否已满:" + cycleQueue.isFull());//输出:true System.out.println("第1次出队:" + cycleQueue.dequeue());//输出:1 System.out.println("第2次出队:" + cycleQueue.dequeue());//输出:2 System.out.println("第3次出队:" + cycleQueue.dequeue());//输出:null,因为 3 入队失败 System.out.println("循环队列是否为空:" + cycleQueue.isEmpty());//输出:true System.out.println("循环队列是否已满:" + cycleQueue.isFull());//输出:false } private Object[] data; private int size; private int head;//队列头部 private int tail;//队列尾部 public MyCycleQueueByArray(int size) { this.size = size; data = new Object[size]; head = 0; tail = 0; } public boolean isFull(){ return (tail + 1) % size == head; } public boolean isEmpty(){ return head == tail; } /** * 入队 * @param e * @return */ public boolean enqueue (E e){ if (isFull()){ return false; } data[tail] = e; tail = (tail + 1) % size;//注意这里不能直接 tail++,否则无法循环使用 return true; } /** * 出队 * @return */ public E dequeue (){ if (isEmpty()){ return null; } E e = (E)data[head]; head = (head + 1) % size;//head 也同样不能直接 head++ return e; } }
这时候我们发现,虽然队列空间有
3
个,但是实际上只能存放2
个元素,而最后两条输出语句的输出结果也说明了循环队列不会出现单向队列的“假溢出问题”。队列实战
队列其实在
Java
的juc
中有广泛应用,比如AQS
等,在这里,我们继续来看一看队列的相关算法题来加深对队列的理解。两个栈实现队列
前面我们讲栈的时候,用了两个队列来实现栈,这道题却正好相反,是利用两个栈来实现队列。
LeetCode
第232
题:请你仅使⽤两个栈实现先⼊先出队列,队列应当⽀持⼀般队列⽀持的所有操作(push、pop、peek、empty)。这道题目其实相比较之前两个队列实现栈还是会更简单一点,因为栈是后入先出,所以我们只需要将入队和出队使用不同的栈就可以解决了。
具体解题思路为:将⼀个栈当作输⼊栈,⽤于压⼊(
push
)传⼊的数据;另⼀个栈当作输出栈,⽤于pop
(出队) 和peek
(查看队列头部元素) 操作。 每次pop
或peek
时,若输出栈为空则将输⼊栈的全部数据依次弹出并压⼊输出栈,再将元素从输出栈输出。具体代码实现为:
package com.lonely.wolf.note.queue; import java.util.Stack; /** * LeetCode 232 * 请你仅使⽤两个栈实现先⼊先出队列。队列应当⽀持⼀般队列⽀持的所有操作(push、pop、peek、empty): * * void push(int x) 将元素 x 推到队列的末尾 * int pop() 从队列的开头移除并返回元素 * int peek() 返回队列开头的元素 * boolean empty() 如果队列为空,返回 true ;否则,返回 false * * 说明: * 你只能使⽤标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 * 你所使⽤的语⾔也许不⽀持栈。你可以使⽤ list 或者 deque(双端队列)来模拟⼀个栈,只要是标准的栈操作即可。 * * 解题思路 * 将⼀个栈当作输⼊栈,⽤于压⼊ push 传⼊的数据;另⼀个栈当作输出栈,⽤于 pop 和 peek 操作。 * 每次 pop 或 peek 时,若输出栈为空则将输⼊栈的全部数据依次弹出并压⼊输出栈, * * @author lonely_wolf * @version 1.0 * @date 2021/12/26 * @since jdk1.8 */ public class MyQueueByTwoStack<Integer> { private Stack<Integer> inStack;//输入栈 private Stack<Integer> outStack;//输出栈 /** * 即入队:enqueue 操作 * @param e */ public void push(Integer e){ inStack.push(e);//压入输入栈 } /** * 查看并移除队列头部元素,即:出队 dequeue 操作 * @return */ public Integer pop(){ if (!outStack.isEmpty()){//输出栈不为空则直接出栈 return outStack.pop(); } while (!inStack.isEmpty()){//输出栈为空,则检查输入栈 outStack.push(inStack.pop());//输入栈不为空,则将其压入输出栈 } if (!outStack.isEmpty()){//再次检查输出栈是否有元素出栈 return outStack.pop(); } return null; } /** * 查看队列头部元素,相比较 pop,这里只查看元素,并不移除元素 **/ public Integer peek(){ if (!outStack.isEmpty()){ return outStack.peek(); } while (!inStack.isEmpty()){ outStack.push(inStack.pop()); } if (!outStack.isEmpty()){ return outStack.peek(); } return null; } /** * 队列是否为空 * @return */ public boolean empty(){ return inStack.isEmpty() && outStack.isEmpty(); } }
总结
本文主要讲述了队列这种操作受限的数据结构,文中通过一个例子说明了单向链表为什么会存在“假溢出“问题,并最终引出了循环链表,而循环链表的实现同样有三种不同思路,并通过以空间换时间的方法基于数组实现了一个简单的循环链表。最后我们还讲述了如何利用两个栈来实现一个队列。
- 初始化队列时:
-
数据结构队列顺序循环队列、加入、删除、取头元素
2022-04-21 13:19:21队列的插入操作通常称为入队或进队,删除操作通常称为出队。如果队列中没有元素,则称为空队列 队列抽象数据类型:其中T表示队列中数据的类型 public interface Queue { public void enqueue(T t); //元素入队,在... -
用数组实现循环队列(新思路)
2022-01-27 18:26:06用数组实现循环队列(新思路) 用数组实现一个循环队列,难点就在于如何判断数组是否满了,不论是书上的方法,还是一些大佬的写法,都是利用一个计算去判断:(rear + maxSize - front) % maxSize 有的小伙伴天资... -
数据结构—队列的顺序表示和实现--循环队列
2019-07-03 17:29:08和顺序栈相类似,在队列的顺序存储结构中,除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外,尚需附设两个整型变量 front和rear分别指示队列头元素及队列尾元素 1.队列的顺序表示 typedef ... -
循环队列的各种基本运算
2017-12-04 16:07:33循环队列的各种基本运算 码文不易,如果帮助到您,希望您可以帮我刷一下点击量,与您无害,与我有益谢谢 支持原创 。 欢迎大家阅读我的博客,如果有错误请指正,有问题请提问,我会尽我全力改正错误回答... -
循环队列(链式表示和实现)
2021-07-21 17:13:04通常链队用单链表来表示,如下图所示。一个链队显然需要两个分别指向队头和队尾的指针(分别称为头指针和尾指针)才能唯一确定。这里和线性表的单链表一样。为了操作方便起见,给链队添加一个头节点,并令头指针始终... -
循环队列简介
2020-12-12 09:34:53循环队列的出现是为了克服普通队列存在“假溢出”的现象,将存储空间想象成一个首位相接的圆环,当写指针写到末尾后重新从首部写入。由于存储空间有限,当设计循环队列时,需要考虑队满的情况,通常循环队列在队满时... -
【线性表】队列:顺序队列、顺序循环队列、链式队列的基本特性
2020-06-06 14:36:15队列是一种特殊的线性表,特殊之处在于它只允许头部和尾部进行操作。 -
数据结构——循环队列PTA习题
2020-12-17 23:39:58文章目录单选题题解函数题6-1 另类循环队列 (20分)输入样例:输出样例:代码6-2 双端队列 (25分)输入样例:输出样例:代码编程题7-1 堆栈模拟队列 (25分)输入格式:输出格式:输入样例:输出样例:代码模拟队列直接用... -
数据结构之循环队列C语言实现(详细)
2020-05-25 23:59:25队列的一些说明 队列的定义 队列,一种特殊的线性表...循环队列使用的是数组,但是这个数组比较特别,为循环数组。为什么要使用循环数组呢? 可以想象一下,假如我们使用通常的数组。 那么在使用过程中,我们是从后面加 -
【队列】队列 Queue(一):顺序队列与循环队列
2018-09-20 22:37:00最常见的就是去超市买菜称重时大妈们排得贼长的队列(这是理想情况,通常是围成一圈),还有超市结账的队伍,还有以前食堂打饭的队伍。是不是很有印象呢~~~ 那队列有什么特点呢? 就拿食堂打饭来说,下课... -
对循环队列的理解
2021-07-06 22:17:45循环队列存储在数组A[0…n-1]中,其头尾指针分别为f和r,头指针f总是指向队头元素,尾指针r总是指向队尾元素的下一个位置,则元素e入队时的操作为(B )。 A.A[r]=e; r=r+1 B.A[r]=e; r=(r+1)%n C.A[r]=e;r=(r+1)%(n... -
数据结构--队列--顺序循环队列的操作实现(C语言)
2022-04-15 15:48:49循环队列顺序循环队列的实现⭐1.创建初始化队列⭐2.入队⭐3.出队⭐4.队列遍历打印⭐5.清空队列⭐6.判断队列空⭐7.判断队列满⭐8.动态内存释放总结 本文中涉及的完整代码及各操作测试代码均已提交至Gitee,大家可以... -
数据结构—循环队列
2022-04-13 21:15:28循环队列 -
数据结构-第三章-栈和队列(4)-循环队列
2022-01-22 13:29:31数据结构 ⚡️数据结构-第一章 ⚡️抽象数据类型案例 ⚡️数据结构-第二章(1)-线性结构 ⚡️数据结构-第二章(2)-线性表的顺序表示和...数据结构-第三章-栈和队列(4)-循环队列数据结构队列队列的抽象数据类型 -
顺序队列的实现(循环队列)
2019-12-01 16:24:57在顺序队列中,通常让队尾指针rear指向刚进队的元素的位置,让队首指针front指向刚出队的元素的位置。因此,元素进队的时候rear指针要向后移动,元素出队的时候front指针也要向后移动。 #define _CRT_SECURE_NO_... -
c++循环队列与链队列基本操作的实现
2022-04-19 22:31:42就是与顺序表对应的队列类型,使用一组连续的存储单元依次存放队列从头到尾的元素,同时使用两个整型变量:front(头指针)与rear(尾指针)分别指示队首元素和队尾元素。 循环队列存储结构表示 typ -
队列,循环队列,链队列的基础操作
2020-02-03 14:34:18队列 队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端... -
队列基础知识
2022-03-29 00:10:2727.循环队列存储在数组A[0…m]中,则入队时的操作为( )。【中山大学 1999 一、6(1分)】 A. rear=rear+1 B. rear=(rear+1) mod (m-1) C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1) 队列:像栈一样,队列也... -
循环队列---实际项目的运用
2018-04-10 22:46:48此文主要记录IPC项目中如何运用循环队列来处理多则消息的。 (网络摄像头以下简称IPC) 在项目中,经常会有网络消息处理。现在的安防摄像头很多,通常也会配套一个APP去控制IPC,比如设置移动检测、人脸识别、婴儿... -
数据结构-----循环队列 链式队列
2019-04-02 13:05:59循环队列 循环队列的实现 链式队列 链式队列的实现 队列的定义 队列是一种只允许一端进行插入操作,一端只允许进行删除操作的线性表。 队列是一种先进先出(FIFO)的线性表,它只允许在表的一端进行插入... -
顺序循环队列&链队列
2021-11-12 22:53:02队列与栈同样是一种操作受限制的线性表,队列的特点是先进先出即 FIFO,一般在尾部插入头部删除,在通常使用过程中,顺序队列经常产生假溢出等情况,因此时常采用顺序循环队列。 除顺序队列外还有链队,双端队列等... -
解决顺序队列的“假溢出”问题之环形队列(循环队列)——Python实现
2019-11-15 16:09:22队列通常可以用数组或者是链表实现。这里以数组举例,假设这儿有一个长度为5的数组,左端为头部,负责取出数据,右端为尾部,负责存入数据。 从尾部加入数据A 再从尾部加入数据B 再从尾... -
循环队列问题
2014-06-05 16:31:351. 一循环队列,队头指针为front,队尾指针为rear,循环队列长度为N,其队内有效长度为_______ 2.