循环队列实现（C语言）

妖狐艹你老母 2022-07-15 00:39 237阅读 0赞

** 背景：**

生活中有很多队列的影子，比如打饭排队，买火车票排队问题等，可以说与时间相关的问题，一般都会涉及到队列问题；从生活中，可以抽象出队列的概念，队列就是一个能够实现“先进先出”的存储结构。队列分为链式队列和静态队列；静态队列一般用数组来实现，但此时的队列必须是循环队列，否则会造成巨大的内存浪费；链式队列是用链表来实现队列的。这里讲的是循环队列。

**1、循环队列**

循环队列的提出：为充分利用向量空间，克服"[假溢出][Link 1]"现象

方法：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。存储在其中的队列称为循环队列（Circular Queue）

实现方式：这种循环队列可以以[单链表][Link 2]的方式来在实际编程应用中来实现

特点：队列的操作特点是“先进先出”。前者主要是头指针、尾指针的使用，后者主要是理解循环队列提出的原因及其特点。两者都要掌握队列空与满的判定条件以及出队列、入队列操作的实现。

**2、实现循环队列的注意事项**

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

解决这个问题的方法至少有两种：

1）另设一[变量][Link 3]，用来记录数组中当前元素的个数，以区别队列的空和满；

2）另一种方式就是数据结构常用的：队满时：(rear+1)%n==front，n为队列长度（所用[数组][Link 4]大小），由于rear，front均为所用空间的指针，循环只是逻辑上的循环，所以需要求余运算。如图a情况，队已满，但是rear（5）\+1=6！=front（0），对空间长度求余，作用就在此6%6=0=front（0）。（**其二是少用一个元素空间，也就是最后一个存储空间不用，如图1，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列呈“满”状态的标志。**当（rear+1）%maxsiz=front时，队列满。）

> > > > ![Center][]
> > > > 
> > > > > > 图a

![Center 1][]

> > > > > > 图1

![Center 2][]

> > > > > 图2

3、源码

#ifndef __QUEUE_H_  
    #define __QUEUE_H_  
    
    typedef  int QueueElementDataType;
    
    
    
    ///
    //利用空一个元素空间区分队空还是队满
    //
    typedef struct queue   
    {  
    	QueueElementDataType *pBase;	  //初始化的动态非配存储空间
    	int front;    //队头指针，指向队首位置，删除一个元素就将front顺时针移动一位  
    	int rear;    //队尾指针，指向队列最后一个元素的下一个元素，插入一个元素就将rear顺时针移动一位 
    	int QueueMaxsize; //循环队列的最大存储空间  
    }QUEUE,*PQUEUE;  
    
    void InitialQueue(PQUEUE Q,int QueueMaxsize);   
    bool FullQueue(PQUEUE Q);  
    bool EmptyQueue(PQUEUE Q);  
    bool Enqueue(PQUEUE Q, int val);  
    bool Dequeue(PQUEUE Q, int *val);  
    
    ///
    //利用计数标志区分队空还是队满
    //
    typedef struct queue2   
    {  
    	QueueElementDataType *pBase;	  //初始化的动态非配存储空间
    	int front;    //队头指针，指向队首位置，删除一个元素就将front顺时针移动一位  
    	int rear;    //队尾指针，指向队列最后一个元素的下一个元素，插入一个元素就将rear顺时针移动一位 
    	int QueueMaxsize; //循环队列的最大存储空间  
    	int nCount;	 //计算器
    }QUEUE2,*PQUEUE2;  
    
    void InitialQueue2(PQUEUE2 Q,int QueueMaxsize); 
    bool FullQueue2(PQUEUE2 Q);  
    bool EmptyQueue2(PQUEUE2 Q); 
    bool Enqueue2(PQUEUE2 Q, int val);  
    bool Dequeue2(PQUEUE2 Q, int *val);  
    
    #endif

#include "CirculeQueue.h"
    #include <stdlib.h>
    
    //队列初始化
    void InitialQueue(PQUEUE Q,int QueueMaxsize)
    {
    	Q->front = Q->rear = 0;	//对头对尾指向同一个存储空间，置队空
    	Q->pBase = (int *)malloc(QueueMaxsize * sizeof(QueueElementDataType));//动态申请队列存储空间（对已知队列长度的前提下，用循环队列）
    }
    
    //入队
    bool Enqueue(PQUEUE Q, int val)  
    {  
    	if(FullQueue(Q))  
    		return false;  
    	else  
    	{  
    		Q->pBase[Q->rear]=val;  
    		Q->rear=(Q->rear+1)%Q->QueueMaxsize; 
    
    		return true;  
    	}  
    } 
    
    //出队
    bool Dequeue(PQUEUE Q, int *val)  
    {  
    	if(EmptyQueue(Q))  
    	{  
    		return false;  
    	}  
    	else  
    	{  
    		*val=Q->pBase[Q->front];  
    		Q->front=(Q->front+1)%Q->QueueMaxsize;
    
    		return true;  
    	}  
    }  
    
    //队列判空
    bool EmptyQueue(PQUEUE Q)  
    {  
    	if(Q->front==Q->rear)    //队空  
    		return true;  
    	else  
    		return false;  
    }  
    
    //队列判满
    bool FullQueue(PQUEUE Q)  
    {  
    	if(Q->front==(Q->rear+1)%Q->QueueMaxsize)    //队满，留一个预留空间不用  
    		return true;  
    	else  
    		return false;  
    }  
    
    
    void InitialQueue2(PQUEUE2 Q,int QueueMaxsize)
    {
    	Q->front = Q->rear;	//对头对尾指向同一个存储空间，置队空
    	Q->pBase = (int *)malloc(QueueMaxsize * sizeof(QueueElementDataType));//动态申请队列存储空间（对已知队列长度的前提下，用循环队列）
    }
    
    bool EmptyQueue2(PQUEUE2 Q)
    {
    	if(Q->nCount == 0)	//队空 
    		return true;
    	else
    		return false;
    }
    
    bool FullQueue2(PQUEUE2 Q)
    {
    	if(Q->nCount == Q->QueueMaxsize) //队满
    		return true;
    	else
    		return false;
    }
    
    bool Enqueue2(PQUEUE2 Q, int val)
    {
    	if(EmptyQueue2(Q))  
    	{  
    		return false;  
    	}  
    	else  
    	{  
    		Q->pBase[Q->rear] = val; //新元素插入队尾  每当插入新的队列尾元素时，“尾指针增1”
    		Q->rear = (Q->rear + 1)%Q->QueueMaxsize;//队尾指针指向下一个元素
    		Q->nCount++; //队列元素个数加1
    
    		return true;  
    	} 
    }
    bool Dequeue2(PQUEUE2 Q, int *val)
    {
    	if (FullQueue2(Q))
    	{
    		return false;
    	} 
    	else
    	{
    		*val = Q->front;
    		Q->front = (Q->front + 1)%Q->QueueMaxsize;//每当删除队列头元素时，“头指针增1”
    		Q->nCount--; //队列元素个数减1
    
    		return true;
    	}
    }
    
    int main()
    {
    	QUEUE Q;
    	Q.QueueMaxsize = 100;//队列长度
    
    	InitialQueue(&Q,100);//初始化队列
    
    	for(int i = 0;i< Q.QueueMaxsize -2;i++)//空一个存储空间
    	{
    		Enqueue(&Q,i);
    	}
    
    	for(int i = 0;i< Q.QueueMaxsize -2;i++)
    	{
    		Dequeue(&Q,&i);
    	}
    
    	//
    
    	QUEUE2 Q2;
    	Q2.QueueMaxsize = 100;//队列长度
    
    	InitialQueue2(&Q2,Q2.QueueMaxsize);//初始化队列
    
    	for(int i = 0;i< Q2.QueueMaxsize -1;i++)//装满所有存储空间
    	{
    		Enqueue2(&Q2,i);
    	}
    
    	for(int i = 0;i< Q2.QueueMaxsize -1;i++)
    	{
    		Dequeue2(&Q2,&i);
    	}
    	
    
    	return 0;
    }

[Link 1]: http://baike.baidu.com/view/697422.htm
[Link 2]: http://baike.baidu.com/view/178637.htm
[Link 3]: http://baike.baidu.com/view/2792492.htm
[Link 4]: http://baike.baidu.com/view/209670.htm
[Center]: /images/20220715/ba722fc7029045a48b2e21c6e7bfd3a9.png
[Center 1]: /images/20220715/40fbb11dfc8543cb9ff1af24808288a9.png
[Center 2]: /images/20220715/8af21acf4209479d84307daf658638ec.png