循环队列的数组（C/C++）实现及详细讲解 |
您所在的位置：网站首页 › 遍历数组代码 › 循环队列的数组（C/C++）实现及详细讲解 |
循环队列的数组（C/C++）实现及详细讲解
|
本篇博客将实现循环队列的数组结构，实现功能有入队、出队、计算队列长度、判断队列是否为空、为满等。 队列的初始状态如下： 入队操作示意图如下：
出队操作示意图如下所示：
队列空满示意图如下： 具体实现代码如下： 1.头文件CircleQueue.h #pragma once #ifndef CIRCLEQUEUE_H #define CIRCLEQUEUE_H #define NumOfQueue 10 typedef int ElementType; struct queue { int Capacity; int size; int front; int rear; ElementType* Array; }; typedef struct queue* Queue; Queue CreatQueue();//创建空队列； int IsEmpty(Queue Q);//判断队列是否为空； int IsFull(Queue Q);//判断队列是否为满； void MakeEmpty(Queue Q);//置空 int LengthOfQueue(Queue Q);//计算队列长度 void EnQueue(Queue Q, ElementType data);//入队 void DeQueue(Queue Q);//出队 void PrintQueue(Q);//打印队列 #endif // !CIRCLEQUEUE_H2.源文件CircleQueue.c #include #include #include"CircleQueue.h" Queue CreatQueue()//创建空队列； { Queue Q = malloc(sizeof(struct queue)); if (Q == NULL) { printf("out of space!!!"); exit(1); } Q->Array = malloc(sizeof(ElementType) * NumOfQueue); if (!Q->Array) { printf("out of space!!!"); exit(1); } Q->front = Q->rear = 0; Q->size = 0; Q->Capacity = NumOfQueue; return Q; } int IsEmpty(Queue Q)//判断队列是否为空； { return Q->size ==0 ; } int IsFull(Queue Q)//判断队列是否为满； { return Q->size == Q->Capacity; } void MakeEmpty(Queue Q)//置空 { Q->front = Q->rear = 0; Q->size = 0; } int LengthOfQueue(Queue Q)//计算队列长度 { return Q->size; } void EnQueue(Queue Q, ElementType data)//入队 { if (IsFull(Q)) { printf("Enqueue Error:the queue is full !!!"); exit(1); } Q->Array[Q->rear++] = data; if (Q->rear == Q->Capacity) Q->rear = 0; ++Q->size; } void DeQueue(Queue Q)//出队 { if (IsEmpty(Q)) { printf("Dequeue Error: the queue is empty !!!"); exit(1); } ++Q->front; if (Q->front == Q->Capacity) Q->front = 0; --Q->size; } void PrintQueue(Queue Q)//打印队列 { if (IsEmpty(Q)) { printf("Print warning: the queue is empty !!!"); exit(1); } int i = Q->front; if(Q->rear>Q->front) for (; i rear; i++) { printf("%d ", Q->Array[i]); } else for (; i front+Q->size; i++) { printf("%d ", Q->Array[i%Q->Capacity]); } printf("\n"); }3.主程序main.c /******************************************************************************************************** Function：循环队列的数组实现 Date：2020/06/02 *********************************************************************************************************/ #include"CircleQueue.h" int main() { Queue Q=CreatQueue();//创建一个空队列 for (int i = 0; i DeQueue(Q);//出队 } PrintQueue(Q);//打印队列 printf("the length of the queue is:%d\n", LengthOfQueue(Q));//打印队列长度 for (int i = 0; i |
初始状态时，front=rear=0，size=0。
入队时，在数组原来的rear位置插入数据，插入数据后将rear+1向后移动一位，同时将队列长度size+1。
如上图所示，当rear已经指向数组最后一个位置时，再进行入队操作，rear将重新回到起始位置0.
当要将a元素出队时，原本指向a的front指针将移向下一个元素，同时将size-1。要注意的是这时的a其实还在数组中，只是不在有效区域，即实际存在于队列中的数据是front到rear之间的数组数据，而这时的a不在front到rear之间。
如上图所示队列在空和满时，front和rear指针都将重合，因此将很难通过front和rear指针位置判断队列是空还是满。为了方便判断可以采取用实际队列的长度size来进行判断，即size=0时，队列为空；size=capacity（数组的最大容量）时，队列为满。【本文地址】
今日新闻 |
推荐新闻 |