循环队列代码实现（FIFO）

╰半橙微兮° 2022-06-16 07:45 294阅读 0赞

**1.概念**

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

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

![20170509222406705][]![20170509222421267][]![20170509222427470][]

**2.代码**

//circular Queue 循环队列实现
    
    #include <stdlib.h>
    #include <stdio.h>
    
    #define MAXSIZE 100
    typedef int ElemType ;
    
    typedef struct  
    {
    	ElemType *base; //存储内存分配基地址
    	int front;      //队列头索引
    	int rear;       //队列尾索引
    }circularQueue;
    
    //初始化队列
    InitQueue(circularQueue *q)
    {
    	q->base = (ElemType *)malloc((MAXSIZE) * sizeof(ElemType));
    	if (!q->base) exit(0);
    	q->front = q->rear = 0;
    }
    
    //入队列操作
    InsertQueue(circularQueue *q, ElemType e)
    {
    	if ((q->rear + 1) % MAXSIZE == q->front) return; //队列已满时，不执行入队操作
    	q->base[q->rear] = e;  //将元素放入队列尾部
    	q->rear = (q->rear + 1) % MAXSIZE; //尾部元素指向下一个空间位置,取模运算保证了索引不越界（余数一定小于除数）
    }
    
    //出队列操作
    DeleteQueue(circularQueue *q, ElemType *e)
    {
    	if (q->front == q->rear)  return;  //空队列，直接返回
    	*e = q->base[q->front];            //头部元素出队
    	q->front = (q->front + 1) % MAXSIZE;
    }

[20170509222406705]: https://img-blog.csdn.net/20170509222406705
[20170509222421267]: https://img-blog.csdn.net/20170509222421267
[20170509222427470]: /images/20220616/5c33ac977c214553979135bdf63c0514.png