C语言实现顺序队列

本是古典何须时尚 2022-02-01 15:19 286阅读 0赞

有关C语言实现队列

1.队列也是一种运算受限制的线性表，它只允许在表的一段(front)进行插入，在另一端(rear)进行删除。  
2.队列亦称作先进先出的线性表，注意不能称为后进后出。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5namlhYWFhYQ_size_16_color_FFFFFF_t_70]  
\#define MAX 5

//顺序队列结构描述  
struct Sq\_Queue  
\{  
Elemtype data\[MAX\];  
Elemtype front;//对头指针  
Elemtype rear;//对尾指针  
\};  
typedef struct Sq\_Queue SqQueue;

SqQueue Q;

为方便起见，规定front指向当前对头元素，rear指向当前队尾所在位置的下一个位置，所以队列总会有一个位置不放数据元素。

于是，一开始初始化都让front,rear为0，若不考虑溢出，入队的操作为  
Q.data\[Q.rear\]=data;  
Q.rear++;//尾指针加1

若不考虑队空，出队的操作为，其中temp为第三者，用来当函数的返回值  
temp=Q.data\[Q.front\];  
Q.front++;//头指针加1

显然此时，判断队满的条件为  
(Q.rear)-(Q.front)=MAX-1，此时再做入队操作则会上溢，此情况称为真溢出，假溢出的情况后面解决。

判断队空的条件为  
Q.front==Q.rear

假溢出的原因是：如果当前尾指针等于向量的上界（即Q.rear==MAX-1），即使队列不满（即当前队列长度小于MAX-1）,再入队操作也会引发溢出。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5namlhYWFhYQ_size_16_color_FFFFFF_t_70 1]  
如此时队列还有两个空位，但是再入队（即Q.rear++大于MAX-1）就会溢出，  
产生该现象的原因是：被删元素的空间在该元素删除以后就永远是用不到。  
为客服这个问题，下面介绍一种方法。

即设想（注意是设想！！）向量Q.data\[MAX\]是一个首尾相接的圆环，即Q.data\[0\]接在Q.data\[MAX-1\]后面，我们称这种意义下的向量称为循环向量，并将循环向量中的队列称为循环队列。再回到上面假溢出的情况，此时再做入队操作时，令尾指针等于向量的下界，这样就能利用已被删除的元素空间，克服假上溢现象。  
此时，入队操作为（判断队满情况下面介绍）  
Q.data\[Q.rear\]=data;  
Q.rear=(Q.rear+1)%MAX;  
出队操作为  
temp=Q.data\[Q.front\];  
Q.front=(Q.front+1)%MAX;  
为什么要用%即模运算，看回上图，若此时再入队，那么Q.rear=(4+1)%5=0,就入队成功了。  
判断队满的条件为：(Q.rear+1)%MAX=Q.front  
判断队空的条件为：Q.front=Q.rear

下面贴上代码

#include <stdio.h>
    #include <stdlib.h>
    
    
    #define MAX 5
    #define OK 1
    #define ERROR -1
    #define QUEUE_SIZE 100 
    
    typedef int Elemtype;
    
    
    //顺序队列结构描述 
    struct Sq_Queue
    { 
    	Elemtype data[MAX];
    	Elemtype front;//队头指针 
    	Elemtype rear;//队尾指针 
    };
    typedef struct Sq_Queue SqQueue;
    
    
    //初始化队列 
    void InitSqQueue(SqQueue &Q)
    { 
    	Q.front=0;
    	Q.rear=0;
    	
    	printf("\n---success---\n");
    }
    
    
    
    //入队函数 
    void AddQueue(SqQueue &Q,Elemtype data)
    { 
    	if((Q.rear+1)%MAX==Q.front)
    	   printf("\n***Full***\n");
    	   
        else
        { 
    	    Q.data[Q.rear]=data;
        	Q.rear=(Q.rear+1)%MAX;
        	
        }
    }
    
    
    //出队函数
    Elemtype DelQueue(SqQueue &Q)
    { 
    	Elemtype temp;
    	
    	if(Q.front==Q.rear)
    	  printf("\n***Empty***\n");
    	else
    	{ 
    		temp=Q.data[Q.front];
    		Q.front=(Q.front+1)%MAX;
    	}  
    	
    	return temp;
    } 
    
    
    //打印队列函数
    void printf_SqQueue(SqQueue &Q)
    { 
    	Elemtype temp;
    	
    	temp=Q.front;
    	
    	if(Q.front==Q.rear)
    	   printf("***Empty***\n");
    	else
    	{ 
    		printf("输出该队列:");
    		while(Q.front!=Q.rear)
    		{ 
    			printf(" [%d] ",Q.data[Q.front]);
    			Q.front=(Q.front+1)%MAX;
    		}
    	}
    	
    	printf("\n");
    	Q.front=temp;   
    } 
    
    
    
    int main(int argc, char *argv[])
    { 
    	Elemtype temp,temp1,temp2;
    	
    	SqQueue Q;
    	
    	InitSqQueue(Q);
    	
    	do
    	{ 
    		printf("\n***请输入你想执行的功能***\n");
    		printf("(1)入队 （2）出队 （3）EXIT\n");
    		scanf("%d",&temp);
    		
    		switch(temp)
    		{ 
    			
    			case 1:
    			{ 
    				printf("请输入你想入队的数据：");
    				scanf("%d",&temp1);
    				
    				AddQueue(Q,temp1);
    				printf_SqQueue(Q);
    			}break;
    			
    			case 2:
    			{ 
    				temp2=DelQueue(Q);
    				printf("出队的数据为:（%d）\n",temp2);
    				
    				printf_SqQueue(Q);
    			}break;
    			
    		} 
    		
    	}
    	while(temp!=3);
    	
    	
    	printf("\n****感谢您的使用****\n"); 
    	printf("\n");
    	
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5namlhYWFhYQ_size_16_color_FFFFFF_t_70]: /images/20220201/2cf749a317cc48dabe87e01698212865.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2h1YW5namlhYWFhYQ_size_16_color_FFFFFF_t_70 1]: /images/20220201/1d4637380d6e456ab40964730677d032.png