顺序队列

快来打我* 2023-03-12 09:28 19阅读 0赞

![20200515101018261.jpg][]

顺序队列就是拿数组来存储的，不过它的存取规则变为先进先出，就和排队一样先到先得。

不过以这种形式，在进行多次入队出队操作之后，rear指向数组最后一个元素，无法继续插入但前面还有空位置没有利用到，这就是假溢出。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70][]

解决它的方法就是顺序循环队列：

把顺序队列构造成一个逻辑上首尾相连的循环队列，即当rear、front指针指向MaxQueueSize-1的位置的时候，再前进一个位置就自动到0；

数学上解决+1归0的方法是求余：例如，设MaxQueueSize=6，当rear=5时，若再+1，则rear = (rear+1)%6=0，实现了需求。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70 1][]

typedef int DataType;
    #include<stdio.h>
    #define MaxQueueSize 10
    
    typedef struct
    {
    	DataType queue[MaxQueueSize];
    	int rear;//队尾指针负责入数据 
    	int front;//队头指针负责出数据 
    	int count;//计数器 
    }SeqCQueue;
    //
    void  QueueInitiate(SeqCQueue *Q)
    {
    	Q->rear = 0;
    	Q->front = 0;
    	Q->count = 0;
     } 
     //
     int QueueNotEmpty(SeqCQueue Q)
     {
     	if(Q.count != 0) return 1;
     	else return 0;
     }
     //
     int QueueAppend(SeqCQueue *Q,DataType x)
     {
     	if(Q->count>0&&Q->rear==Q->front)
     	{
     		printf("队列已满无法插入！\n");
    		 return 0; 
    	 }
    	 else
    	 {
    	 	Q->queue[Q->rear] = x;
    	 	Q->rear = (Q->rear + 1)%MaxQueueSize;
    	 	Q->count++;
    	 	return 1;
    	 }
     }
     //
     int QueueDelete(SeqCQueue *Q,DataType *d)
     {
     	if(Q->count==0)
     	{
     		printf("队列已空无元素出队列！\n");
    		 return 0; 
    	 }
    	 else
    	 {
    	 	*d = Q->queue[Q->front];
    	 	Q->front = (Q->front+1)%MaxQueueSize;
    	 	Q->count--;
    	 	return 1;
    	  } 
     }
     //
     int QueueGet(SeqCQueue Q,DataType *d)
     {
     	if(Q.count==0)
     	{
     		printf("队列已空无数据可取！\n");
    		 return 0; 
    	 }
    	 else
    	 {
    	 	*d = Q.queue[Q.front];
    	 	return 1;
    	  } 
     }

测试

#include<stdio.h>
    #include"head.h"
    int main()
    {
    	SeqCQueue myQueue;
    	QueueInitiate(&myQueue);
    	int i,x;
    	for(i=0;i<10;i++)
    	{
    		QueueAppend(&myQueue,i+1);
    	}
    	printf("依次出队列的数据元素序列如下：\n");
    	while(QueueNotEmpty(myQueue))
    	{
    		QueueDelete(&myQueue,&x);
    		printf("%d ",x);
    	 } 
    	return 0;
     }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70 2][]

队尾加数据，对头出数据。

[20200515101018261.jpg]: /images/20230312/a50b27a9ce30484f84aaaeb71f4e3207.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70]: /images/20230312/bf70a7d9e90d4afcb25bed131d4b4f51.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70 1]: /images/20230312/3279613a514a40a3906f4682dc8b42fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ludDg4ODg4OA_size_16_color_FFFFFF_t_70 2]: /images/20230312/eb3f228b84f646b7a5b5f74c38446ec6.png