线性表之顺序队列（循环队列）(C语言实现)

我就是我 2022-03-27 05:30 247阅读 0赞

一、队列概念

1、队列(queue)是一种只允许在一端进行插入操作，而在另一端进行删除的操作的线性表

2、队列是一种先进先出(first in first out)的线性表，简称FIFO。允许插入的一端成为队尾，允许删除的一端成为对头。假设队列是q=(a1,a2,...,an),那么a1就是对头元素，an就是队尾元素。这样我们删除时，总是从a1开始，而插入时，列在最后。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70][]

二、循环队列

1、为了解决顺序队列插入和删除时需要移动数据、"假溢出"问题，引入循环队列。循环队列的定义：我们把队列的这种头尾相接的顺序存储结构成为循环队列。

2、顺序队列的插入删除的时间复杂度为O（1）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70 1][]

二、循环队列数据结构

typedef int QElemType;//根据实际情况而定，这里假设为int
    /********循环队列的顺序存储数据结构**********/
    typedef struct queue 
    {
    	QElemType *pBase;	  //顺序存储内存分配基地址
    	int front;    //指向队列第一个元素
    	int rear;    //指向队列最后一个元素的下一个元素
    	int maxsize; //循环队列的最大存储空间
    }QUEUE,*PQUEUE;

三、循环队列基本操作

1、创建队列

bool CreateQueue(PQUEUE Q,int maxsize)
    {
    	if(!Q)
    		return false;
    
    	Q->pBase = (QElemType *)malloc(sizeof(QElemType)*maxsize);
    	if(!Q->pBase)
    	{
    		printf("Memory allocation failure");
    		return false;
    	}
    	else
    	{
    		Q->front=0;         //初始化参数
    		Q->rear=0;
    		Q->maxsize=maxsize;
    	}
    	
    	return true;
    }

2、空队列

bool EmptyQueue(PQUEUE Q)
    {
    	if(!Q)
    		return false;
    
    	if(Q->front==Q->rear)    //判断是否为空
    		return true;
    	else
    		return false;
    }

3、满队列

bool FullQueue(PQUEUE Q)
    {
    	if(!Q)
    		return false;
    
    	if(Q->front==(Q->rear+1)%Q->maxsize)    //判断循环链表是否满，留一个预留空间不用
    		return true;
    	else
    		return false;
    }

4、入队

bool Enqueue(PQUEUE Q, QElemType val)
    {
    	if(!Q)
    		return false;
    
    	if(FullQueue(Q))
    		return false;
    	else
    	{
    		Q->pBase[Q->rear]=val;
    		Q->rear=(Q->rear+1)%Q->maxsize;
    		return true;
    	}
    }

5、出队

bool Dequeue(PQUEUE Q, QElemType *val)
    {
    	if(!Q)
    		return false;
    
    	if(EmptyQueue(Q))
    	{
    		return false;
    	}
    	else
    	{
    		*val=Q->pBase[Q->front];
    		Q->front=(Q->front+1)%Q->maxsize;
    		return true;
    	}
    }

6、获取队列长度

int QueueLength(PQUEUE Q)
    {
    	if(!Q)return -1;
    	else
    		return (Q->rear-Q->front+Q->maxsize)%Q->maxsize;
    }

7、

bool GetHead(PQUEUE Q, QElemType *val) 
    {
    	if(EmptyQueue(Q))
    	{
    		return false;
    	}
    	else
    	{
    		*val=Q->pBase[Q->front];
    		return true;
    	}
    }

8、清空队列

bool ClearQueue(PQUEUE Q)
    {
    	if(!Q)
    		return false;
    
    	Q->front = Q->rear;
    
    	return true;
    }

9、销毁队列

int DestroyQueue(PQUEUE Q)
    {
    	if(!Q)
    		return false;
    
    	if(Q->pBase)
    		free(Q->pBase);
    
    	Q->pBase = NULL;
    
    	return true;
    }

10、遍历队列

bool TraverseQueue(PQUEUE Q)
    {
    	if(!Q)
    		return false;
    		
    	int i=Q->front;
    	printf("队中的元素是:\n");
    	while(i%Q->maxsize!=Q->rear)
    	{
    		printf("%d ",Q->pBase[i]);
    		i++;
    	}
    	printf("\n");
    
    	return true;
    }

四、测试代码及测试结果

void main(void)
    {	
    	QUEUE MyQueue;
    
    	int ret = CreateQueue(&MyQueue,10);
    	if(false == ret)
    		return;
    
    	QElemType i;
    	for(i = 0;i < 20;i++)
    	{
    		if(false == Enqueue(&MyQueue,i)) break;
    		else
    			printf("依次入队元素：%d\n",i);
    	}
    
    	int len = QueueLength(&MyQueue);
    	printf("===========len：%d===========\n",len);
    
    	TraverseQueue(&MyQueue);
    
    	QElemType val;
    
    	GetHead(&MyQueue,&val);
    	printf("===========对头元素：%d===========\n",val);
    
    	for(i = 0;i < 5;i++)
    	{
    		if(false == Dequeue(&MyQueue,&val)) break;
    		else
    			printf("依次出队元素：%d\n",val);
    	}
    
    	TraverseQueue(&MyQueue);
    
    	ClearQueue(&MyQueue);
    
    	DestroyQueue(&MyQueue);
    
    
    	system("pause");
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70 2][]

注意:此循环队列/环形缓冲，当缓冲区满时，只实现了不覆盖old data

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70]: /images/20220327/ad7429eedaab4b58baf38eec8668fb2c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70 1]: /images/20220327/61578fe5c7a744639929429fbfc1c215.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW5neW91cm1pbmQ_size_16_color_FFFFFF_t_70 2]: /images/20220327/202ed06a68de4fd295038d0aabf00e07.png