最简单的队列

矫情吗；* 2021-11-05 15:10 237阅读 0赞

## 一。什么是队列： ##

队列（Queue）是一种只允许在一端**插入数据**（入队），而另一端**删除数据**（出队）的线性表。  
插入数据的端口叫队头(head)，另一端叫队尾（rear），  
**特点**：先进先出（你去排队买东西，先排队的人肯定先买，后排队的人后买）

## 二。（顺序存储结构）队列的基本操作 ##

1.  队列初始化InitQueue(Q)，构造一个空队列Q
2.  判断一个队列是否为空QueueEmpty(Q)，队列Q为空返回1
3.  销毁队列DestroyQueue(&Q)，释放队列所占的存储空间
4.  入队EnQueue(Q,x)，将元素x插入队列Q
5.  出队DeQueue(Q)，删去Q的队头元素并且将它的元素值返回
6.  读取队头元素GetHead(Q),返回Q的队头元素，不改变队列Q的状态
7.  判断队列是否已满QueueFull(Q)，诺队列Q为满，则返回1

## 三。具体的代码及其分析： ##

#include<stdio.h>
    	#include<stdlib.h>
    	#define MaxSize 21//给队列一个最大长度21 
    	typedef int QueueElemType;//队列元素的类型设定为整型 
    	 
    	typedef struct{
    		QueueElemType *base;//base指向队列存储区的首地址 
    		int front;//队头指针，指向队头元素 
    		int rear;//队尾指针，指向队尾元素 
    	}SeqQueue; //循环队列 
    	//1队列的初始化--------------------------------- 
    	SeqQueue InitQueue(){
    		SeqQueue Q;//实例化一个Q队列 
    		Q.base = (QueueElemType *)malloc(MaxSize * sizeof(QueueElemType));//给队列申请MaxSize个存储空间 
    		if(!Q.base){//如果Q.base存在则Q.base的值等于true，存储空间分配成功， 
    			printf("申请存储空间失败");
    			exit(0); 
    		}
    		Q.front=0;//队列置空 
    		Q.rear=0;
    		return Q;
    		
    	} 
    	//2判断队列是否为空-------------------------------- 
    	int QueueEmpty(SeqQueue Q){
    		return (Q.front==Q.rear)? 1: 0;//如果Q.front==Q.rear则队列为空返回1，否则返回0 
    	} 
    	//3判断队满------------------------------------------- 
    	int QueueFull(SeqQueue Q){
    		return (Q.front==(Q.rear+1)%MaxSize)? 1: 0;//如果Q.front==(Q.rear+1)%MaxSize则循环队列为满返回1，否则返回0 
    	} 
    	//4入队------------------------------------------------- 
    	SeqQueue EnQueue(SeqQueue Q,QueueElemType x){
    		if(QueueFull(Q)){
    			printf("队满，入队失败");
    	//        exit(0); 
    		}
    		else{
    			*(Q.base+Q.rear) = x;//插入元素存入队尾 
    			Q.rear=(Q.rear+1)%MaxSize;//队尾指针加一，入队完成 
    			//为什么写Q.rear=(Q.rear+1)%MaxSize而不是Q.rear=Q.rear+1
    			//Q.rear=(Q.rear+1)%MaxSize可以将Q.rear的值限定在0~MaxSize中 
    		}
    		return Q;
    	} 
    	//5出队----------------------------------------------- 
    	SeqQueue DeQueue(SeqQueue Q,QueueElemType *e){
    		if(Q.front==Q.rear){
    			printf("队空，出队失败");
    	        exit(0); 
    		}
    		else{
    			*e = *(Q.base+Q.front);//取出队头元素，由实参e带回 
    			Q.front=(Q.front+1)%MaxSize;//令Q.front+1在0~MaxSize中，出队完成 
    		}
    		return Q;
    	} 
    	//6读取队头元素------------------------------------------ 
    	 QueueElemType GetHead(SeqQueue Q){
    	 	if(QueueEmpty(Q)){
    	 		printf("\n队列为空，读取队头失败");
    			 exit(0); 
    		 }
    		 else{
    		 	return *(Q.base+Q.front);
    		 	//这里为什么返回的是*(Q.base+Q.front)而不是*Q.front
    		    //因为这里有*  所以是对地址的操作，Q.base是这个队列的首地址，Q.front是相对于首地址的偏移量
    			//比如是Q.base的地址为5，Q.front等于5，则Q.front的真正地址为Q.base+偏移量5==10 
    		 }
    	 } 
    	 //7销毁队列---------------------------------------------- 
    	 void DestroyQueue(SeqQueue Q){
    	 	free(Q.base);//free()为#include<stdio.h>中的一个库函数，可以释放存储空间 
    	 	printf("\n队列已经销毁，空间释放完成");
    		 return ; 
    	 } 
    	 //8遍历输出队列中的各个元素------------------------------- 
    	 void QueueDisplay(SeqQueue Q){
    	 	int i;
    	 	if(QueueEmpty(Q)){
    	 		printf("队列为空！无元素输出"); 
    		 }
    		else{
    			printf("\n遍历队列元素--------------------\n");
    			for(i=Q.front;Q.rear!=i%MaxSize;i=(i+1)%MaxSize)
    			printf("\n%3d",*(Q.base+i));
    		}
    		return ;
    	 } 
    	 int main(){
    	 	int i;
    	 	QueueElemType m,t,temp;//定义一个QueueElemType类型的临时变量temp,以便出队时存放出队元素的值 
    	 	printf("\n\ntemp的默认值=%d\n",temp);
    	 	printf("\n\nt的默认值=%d\n",t);
    	 	printf("\n\nm的默认值=%d\n",m);
    	 	printf("这t,m和temp的默认值都不相等，你发现了什么？\n");
    	 	SeqQueue queue;
    	 	queue=InitQueue();
    	 	printf("入队开始：-----------------------\n");
    	 	for(i=1;i<21;i++){
    	 		queue=EnQueue(queue,i*i);
    	 		printf("\n%d入队完成",i*i); 
    		 }
    		printf("\n入队结束！----------------------\n");
    		QueueDisplay(queue);
    		printf("\n执行出队！----------------------\n");
    		for(i=1;i<5;i++){
    			queue=DeQueue(queue,&temp);
    			printf("\n\n%d出队完成",temp);
    		}
    		QueueDisplay(queue);
    		printf("\n\n读取当前的队头元素=%d\n",GetHead(queue));
    		
    		QueueDisplay(queue);
    		DestroyQueue(queue);
    		return 0;
    	 }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDg0MTMxMg_size_16_color_FFFFFF_t_70]: /images/20211105/ecb3e4e9bc4b47eaaa8864de01ee206b.png