循环队列的存储设计实现（C语言版）

本是古典何须时尚 2022-05-24 09:06 145阅读 0赞

1.概念

为充分利用向量空间，克服顺序存储结构的"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现。

循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。使用求余运算可以判断队列是否已满。

基本操作：

/\* 定义链表队列 \*/

定义结构体中front指示队头位置，rear指示队尾位置，base指针用于申请空间并存放数据。

![1146465-20170511173911972-1039080071.png][]

/\* 初始化队列 \*/

使用指针\*base申请100个内存空间，front和rear分别为0，此时队列为空

![1146465-20170511173912910-1271954550.png][]

/\* 判断空或满 \*/

*  初始化时， front = rear = 0  时为空， Q->rear =  （ 0+1 ） %100 = 1 ，队列未满可以插入队列
    
    ![1146465-20170511173913879-1961465367.png][]
 *  入队 3 个元素时， rear = 3 ， Q->rear =  （ 3+1 ） %100 = 4 ，队列未满
    
    ![1146465-20170511173915410-1080193125.png][]
 *  入队 99 个元素时， rear = 99 ， Q->rear =  （ 99+1 ） %100 = 0 ，队列满，不可入队
    
    ![1146465-20170511173916676-1275242472.png][]
 *  出队 2 个元素时， front = 2
    
    出队后，执行两次 Q->front = (Q->front + 1) % MAXQSIZE，得到Q->front = 2
    
    ![1146465-20170511173917707-206641612.png][]
 *  再次入队 1 个元素时， rear = 0 ， Q->rear =  （ 99+1 ） %100=0 ，队列未满，可以入队
    
    ![1146465-20170511173919004-316510306.png][]
 *  通用的计算队列长度公式：（rear-front+QueueSize）%QueueSize
 *      #include <stdio.h>
        #include <stdlib.h>
        #define OK 1
        #define ERROR 0
        #define OVERFLOW -2
        #define MAXQSIZE 10
        typedef int Status;
        typedef int QElemType;
        
        //循环队列的顺序存储结构
        typedef struct Node
        {
        	QElemType *base; //初始化动态分配存储空间
        	int front;//头指针
        	int rear;//尾指针-若队列不空,指向队列尾元素的下一个位置
        } SqQueue;
        
        //初始化一个空的队列
        Status InitQueue(SqQueue *Q)
        {
        	Q->base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));
        	if (!Q->base)
        		exit(OVERFLOW);
        	Q->front = Q->rear = 0;
        	return OK;
        }
        //若队列未满 则插入元素elem为Q新的队尾元素
        Status EnQueue(SqQueue *Q, QElemType elem)
        {
        	//队列为空时 1%10==1,队列满时(9+1)%100==0,最多容纳9个元素
        	if ((Q->rear + 1) % MAXQSIZE == (Q->front))//队列满的判断
        		return ERROR;
        	Q->base[Q->rear] = elem;//将元素elem赋值给队尾
        	Q->rear = (Q->rear + 1) % MAXQSIZE; //rear始终在0-10中循环
        	return OK;
        }
        //循环队列的出队列操作代码
        Status OutQueue(SqQueue *Q, QElemType *e)
        {
        	if (Q->front == Q->rear)//队列为空的判断
        		return ERROR;
        	*e = Q->base[Q->front];//将队头元素赋值给元素e
        	Q->front = (Q->front + 1) % MAXQSIZE;//front指针像后移一位置
        	return OK;
        }
        
        //遍历整个队列,进行打印操作
        Status PrintQueue(SqQueue Q)
        {
        	printf("the queue is:");
        	for (int i = Q.front; i < Q.rear; ++i)
        		printf("%d ", Q.base[i]);
        	return OK;
        }
        int main()
        {
        	SqQueue queue;
        	QElemType elem;
        	int i;
        	InitQueue(&queue);
        	printf("input:");
        	for ( i = 0; i < 10; i++)
        	{
        		elem = i + 1;
        		EnQueue(&queue, elem);
        	}
        
        	PrintQueue(queue);
        	/* 输入要出队列的个数 */
        	printf("\noutput:");
        	scanf("%d", &i);
        	while (i != 0)
        	{
        		OutQueue(&queue, &elem);
        		i--;
        	}
        	PrintQueue(queue);
        	return OK;
        }

[1146465-20170511173911972-1039080071.png]: /images/20220524/542256831d29416b8a5357cc3c62ddb5.png
[1146465-20170511173912910-1271954550.png]: /images/20220524/da264307fea7456d978f93cf181e4ea4.png
[1146465-20170511173913879-1961465367.png]: /images/20220524/5149a8c928274582870e6bea27002b69.png
[1146465-20170511173915410-1080193125.png]: /images/20220524/70d2d066dabe4161afdb667c79878470.png
[1146465-20170511173916676-1275242472.png]: /images/20220524/b7b524e7710c42d48d7ebd92562379b2.png
[1146465-20170511173917707-206641612.png]: /images/20220524/2d3defd1f5bb442289b274b0fe8b81f6.png
[1146465-20170511173919004-316510306.png]: /images/20220524/143fa209ffbe42fb81cb99d65b8730b3.png