数据结构学习——链式队列解析（C语言版）

╰半橙微兮° 2022-12-24 04:56 152阅读 0赞

### 数据结构——链队列解析过程和简单代码实现： ###

*  一、简单概念：
 *   *  动图展示：
     *   *  (1)入队：
         *  (2)出队：
 *  二、顺序队列：
 *   *  思路
     *  步奏：
     *   *  （1）入队操作：
         *  （2）出队操作：
     *  简单实现代码：
 *  三、链式队列
 *   *  （1）声明
     *  （2）入队操作：
     *  （3）出队操作：
     *  （4）检查队列是否为空：
     *  全部代码：

# 一、简单概念： #

> 队列，又称为伫列（queue），是先进先出（FIFO,First-In-First-Out）的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端（称为rear）进行插入操作，在前端（称为front）进行删除操作

> 队列的操作方式和堆栈类似，唯一的区别在于队列只允许新数据在后端进行添加

与栈（stack）不同的是，队列是FIFO（First In First Out，先进先出），进入队列的一端叫尾部（rear），出队列的一端叫头部（front）。队列的主要操作也有两个：入队（offer）、出队（poll）

## 动图展示： ##

### (1)入队： ###

![在这里插入图片描述][20201126202502398.gif_pic_center]

> 从图中可以看到，A、B、C三个元素都是从队尾（rear）进入，就像现实生活中的排队，先来的就排在前面

### (2)出队： ###

![在这里插入图片描述][20201126202617706.gif_pic_center]

> 从图中可以看出，出队的顺序是A->B->C，也就是入队的顺序，即说明了队列是遵循FIFO的。队列的引用也十分广泛，锁的实现、生产者-消费者模型等都离不开队列

队列也有两种实现方式：**顺序队列**、**链式队列**

# 二、顺序队列： #

## 思路 ##

> 在顺序队列中，通常让队尾指针rear指向刚进队的元素的位置，让队首指针 front 指向刚出队的元素的位置。因此，元素进队的时候rear指针要向后移动，元素出队的时候front指针也要向后移动。这样经过一系列的操作后，两个指针最终会到达数组的末端处，虽然队中已没有了元素，但是仍然无法插入元素，这就是所谓的“假溢出”。

> 为了解决假溢出的问题，可以将数组弄成一个环状，让 rear 和 front 指针沿着环走，这样就不会出现无法继续走下去的情况，这样就产生了循环队列，如下图所示 :

*  队空状态 ：qu.rear == qu.front
 *  队满状态 ： (qu.rear + 1) % Maxsize == qu.front
 *  元素的进队操作 ：qu.rear = (qu.rear + 1) % Maxsize ; qu.data\[qu.rear\] = x ;
 *  元素的出队操作 ：qu.front = (qu.front + 1) % Maxsize ; x = qu.data\[qu.front\] ;

**本次思路中** 元素入队时先移动指针，后存入元素；元素出队时也是先移动指针，后元素出队

## 步奏： ##

### （1）入队操作： ###

int inQueue(Squeue &qu,int x)
    {
        
        //判断队列是否已满，若满则无法入队
    	if((qu.rear + 1) % Maxsize == qu.front)
    	{
        
    		return 0;
    	}
        //队列没有满，则先移动指针，在插入元素
    	qu.rear = (qu.rear + 1) % Maxsize;
    	qu.data[qu.rear] = x;
    	return 1; 
    }

### （2）出队操作： ###

int deQueue(Squeue &qu,int &x)
    {
        
        //若队列已空，则无法取出元素
    	if(qu.front == qu.rear)
    	{
        
    		return 0;
    	}
        //否则先移动指针，再将元素取出
    	qu.front = (qu.front + 1) % Maxsize;
    	x = qu.data[qu.front];
    	return 1;
    }

## 简单实现代码： ##

//顺序队列
    #include <stdio.h>
    #include <stdlib.h>
    #define Maxsize 20
     
    //定义队列的结构体 
    typedef struct Squeue{
        
    	int data[Maxsize];
    	int front;
    	int rear;
    }Squeue; 
     
    //初始化队列 
    void InitQueue(Squeue &qu)
    {
        
    	qu.front = qu.rear = 0;
    }
     
    //判断队列是否为空 
    int isQueueEmpty(Squeue qu)
    {
        
    	if(qu.front == qu.rear)
    	{
        
    		return 1;
    	}
    	else
    	{
        
    		return 0;
    	}
    }
     
    //元素入队操作 
    int inQueue(Squeue &qu,int x)
    {
        
    	//若队满则无法入队 
    	if((qu.rear + 1) % Maxsize == qu.front)
    	{
        
    		return 0;
    	}
    	qu.rear = (qu.rear + 1) % Maxsize;
    	qu.data[qu.rear] = x;
    	return 1; 
    }
     
    //元素出队操作 
    int deQueue(Squeue &qu,int &x)
    {
        
    	//若队空则无法出队 
    	if(qu.front == qu.rear)
    	{
        
    		return 0;
    	}
    	qu.front = (qu.front + 1) % Maxsize;
    	x = qu.data[qu.front];
    	return 1;
    }
     
    int main()
    {
        
    	Squeue q;
    	int i , n , x , a;
    	InitQueue(q);
    	scanf("%d",&n);
    	for(i = 0;i < n;i++)
    	{
        
    		scanf("%d",&a);
    		inQueue(q,a);
    	}
    	//当队列非空时，输出队列中所有数据 
    	while(!isQueueEmpty(q))
    	{
        
    		deQueue(q,x);
    		printf("%d ",x);
    	}
    	return 0;
    }

# 三、链式队列 #

**以 模拟患者在医院等待就诊的情况为例子 实现链式队列：**

*  患者到达诊室，将病历交给护士，排到等待队列中候诊
 *  护士从等待队列中取出下一位患者的病历，该患者进入诊室就诊
 *  功能如下：

> 1）排队： 输入排队患者的病历号（随机产生），加入到就诊患者排队队列中  
> 2）就诊： 患者队列中最前面的病人就诊，并将其从队列中删除  
> 3）查看： 从队首到队尾列出所有排队患者的病历号  
> 4）下班： 退出运行

## （1）声明 ##

## （2）入队操作： ##

//	创建链表，存放数据
    Node *Create_Link(ElementType data)
    {
        
    	Node * new = (Node *)malloc(sizeof(Node));	//	开辟空间存数据 
    	
    	if(new == NULL)
    	{
        
    		printf("开辟空间失败\n");
    	}
    	
    	new ->data = data;			//	存放队列数据
    	new ->next = NULL;			//	让尾巴指向NULL
    	
    	return new;					//	返回节点指针
    }
    
    //	判断队列是否为空
    bool QueueEmpty(Queue q) {
        
    
    	if (q->head == NULL)
    		return true;		//		队列为空
    	return false;
    }
    
    //	入队 
    Queue * Push(Queue sum,ElementType data)	
    {
        
    	Node *LinkHead = Create_Link(data);		//	接收链表空间节点指针
    	Queue p = sum;
    	if(QueueEmpty(p) == true){
        
    	
    		p->head = p->wei= LinkHead;		//		第一次赋值会进入 
    	
    		return p;			//	返回值指向队列的头指针
    	}else{
        
    		
    		p->wei->next = LinkHead;		//		让队尾next指针指向这个空间 
    		
    		p->wei = LinkHead;				//		队尾指针存入这个空间 
    	}
    	
    	p->size++;				//		计算队伍长度 
    }

## （3）出队操作： ##

//	出队 
    ElementType Pop(Queue q)
    {
        
    	ElementType count;		//	取队列数据 
    	Node *Link;				
    	
    	if(QueueEmpty(q) == true)
    	{
        
    		printf("数据已经从队列出完\n");
    		q->wei = NULL;
    		return -1;
    	}
    	
    	Link = q->head;			//	让队列头给链表指针 
    	count = Link->data;		//	链表头指针取出数据 
    	q->head = Link->next;	//	让队列头指针移到链表头指针下一个节点位置，并指向它 
    	free(Link);				//	释放已经出队的链表节点 
    	
    	return count;			//	返回取出的数据 
    }

## （4）检查队列是否为空： ##

//	判断队列是否为空
    bool QueueEmpty(Queue q) {
        
    
    	if (q->head == NULL)
    		return true;		//		队列为空
    	return false;
    }

## 全部代码： ##

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    
    typedef int ElementType;
    
    typedef struct Node{
        
    	
    	ElementType data;		//	存放数据 
    	struct Node *next;		//	链表指针 
    	
    }Node;
    
    typedef struct SeqQueue{
        
    	
    	Node *head;				//	队列头部 
    	Node *wei; 				//	队列尾巴 
    	ElementType size;		//	计算队列长度 
    }Seq; 
    
    typedef struct SeqQueue* Queue;
    
    //	初始化队列 
    void Init_SeqQueue(Queue q)
    {
        
    	q->head = NULL;
    	q->wei  = NULL;
    	q->size = 0;	
    }
    
    //	创建链表，存放数据
    Node *Create_Link(ElementType data)
    {
        
    	Node * new = (Node *)malloc(sizeof(Node));	//	开辟空间存数据 
    	
    	if(new == NULL)
    	{
        
    		printf("开辟空间失败\n");
    	}
    	
    	new ->data = data;			//	存放队列数据
    	new ->next = NULL;			//	让尾巴指向NULL
    	
    	return new;					//	返回节点指针
    }
    
    //	判断队列是否为空
    bool QueueEmpty(Queue q) {
        
    
    	if (q->head == NULL)
    		return true;		//		队列为空
    	return false;
    }
    
    //	入队 
    Queue Push(Queue sum,ElementType data)	
    {
        
    	Node *LinkHead = Create_Link(data);		//	接收链表空间节点指针
    	Queue p = sum;
    	if(QueueEmpty(p) == true){
        
    	
    		p->head = p->wei= LinkHead;		//		第一次赋值会进入 
    	
    		return p;			//	返回值指向队列的头指针
    	}else{
        
    		
    		p->wei->next = LinkHead;		//		让队尾next指针指向这个空间 
    		
    		p->wei = LinkHead;				//		队尾指针存入这个空间 
    	}
    	
    	p->size++;				//		计算队伍长度 
    }
    
    //	出队 
    ElementType Pop(Queue q)
    {
        
    	ElementType count;		//	取队列数据 
    	Node *Link;				
    	
    	if(QueueEmpty(q) == true)
    	{
        
    		printf("数据已经从队列出完\n");
    		q->wei = NULL;
    		return -1;
    	}
    	
    	Link = q->head;			//	让队列头给链表指针 
    	count = Link->data;		//	链表头指针取出数据 
    	q->head = Link->next;	//	让队列头指针移到链表头指针下一个节点位置，并指向它 
    	free(Link);				//	释放已经出队的链表节点 
    	
    	return count;			//	返回取出的数据 
    }
    
    //	初始化菜单 
    void Init_Memu()
    {
        
    	printf("***********************************\n");
    	printf("*          1.入队                 *\n");
    	printf("*          2.出队                 *\n");
    	printf("*          3.取队头元素           *\n");
    	printf("*          4.查看队列是否为空     *\n");
    	printf("*          5.插入队列(排队)       *\n");
    	printf("*          6.就诊                 *\n");
    	printf("*          7.查看                 *\n");
    	printf("*          8.下班                 *\n");
    	printf("***********************************\n");
    	
    }
    
    //功能选择函数 
    ElementType Choose_GN()
    {
        
    	int flag;
    	scanf("%d",&flag);
    	return flag;
    }
    
    //	主函数 
    int main()
    {
        
    	Seq S_Queue;			//	创建队列结构体对象 
    	Init_SeqQueue(&S_Queue);	//	初始化队列 
    	Queue q = NULL;			 
    
    	int temp;
    	int num=0;
    	while(1)
    	{
        
    		Init_Memu();
    		printf("请选择你的需求:\n"); 
    		temp =  Choose_GN();
    		Node* p = NULL;
    		switch(temp)
    		{
        
    			//	入队 
    			case 1:
    			{
        
    				ElementType num;
    				while(1){
        
    					printf("请输入你要进队列的数据(输入0时结束输入):\n"); 
    					scanf("%d",&num);
    					if( num == 0)
    					{
        
    						break;
    					}
    					q = Push(&S_Queue,num);		//	接受队头指针head 
    				}
    			}
    				break;
    			
    			//	出队	
    			case 2:
    			{
        
    				int flag;
    				while(1){
        
    					flag = Pop(&S_Queue);
    					if(flag == -1)
    					{
        
    						printf("出队列完毕\n");	
    						break;
    					}else{
        
    						printf("出队数据为: %d\n",flag);
    					}
    				}
    				
    			}
    				break;
    			
    			//	取队头元素	
    			case 3:
    			{
        
    				ElementType sum;
    				p = q->head;		//	取出队头指针 
    				if( p == NULL)
    				{
        
    					printf("队伍已经出队，没有数据\n");
    					break;
    				} 
    				sum = p->data;		//	队头指针取值 
    			 
    				printf("队列头数据为: %d \n",sum);
    			}	
    				break;
    			
    			//	查看队列是否为空	
    			case 4:
    			{
        
    				if(QueueEmpty(q) == true)
    				{
        
    					printf("队伍为空\n");
    				}else{
        
    					printf("队伍还有数据,不为空\n"); 
    				}
    			}
    				break;
    			
    			//	插入队列元素 
    			case 5:
    			{
        
    				int s;
    				printf("请输入你要添加到就诊队伍的病历号:\n");
    				scanf("%d",&s);
    				q = Push(q,s);		//	把输入的数据插入队列中 
    				printf("添加成功！\n");	
    			} 
    				break;
    			
    			//	就诊	
    			case 6:
    			{
        
    				ElementType count1;
    				Node *Link1;
    				
    				Link1 = q->head;			//	取队头指针 
    				count1 = Link1->data;		//	队头指针指向内容取值 
    				q->head = Link1->next;		//	让队头指针移到下一个节点 
    				free(Link1);				//	释放刚才那个头节点
    				 
    				printf("第%d 个患者开始就诊，病历号为: %d\n",++num,count1);
    				
    				if(QueueEmpty(q) == true)	//	判断队伍是否还有人 
    				{
        
    					printf("病人已经全部就诊完毕\n");
    					break; 
    				}
    			}
    				break;
    			
    			//	查看（相当于出队） 
    			case 7:
    			{
        
    				int flag1;
    				int i=0; 
    				while(1){
        
    					flag1 = Pop(&S_Queue);
    					if(flag1 == -1)
    					{
        
    						printf("查看完毕完毕\n");	
    						break;
    					}else{
        
    						printf("第%d 个患者病历号为: %d\n",++i,flag1);
    					}
    				}		
    			}
    				break;
    			
    			//	下班	
    			case 8:
    				printf("工作结束,打卡下班\n");
    				exit(-1);		//	结束进程 
    				
    			default:printf("选择功能错误，请重新选择！！！！\n");break;
    		}
    		
    	}
    	
    	return 0;
    }

**学习笔记，欢迎交流，共同进步**

[20201126202502398.gif_pic_center]: /images/20221120/2fe9d3d7ff7847e8baf2b7d685b3c5a3.png
[20201126202617706.gif_pic_center]: https://img-blog.csdnimg.cn/20201126202617706.gif#pic_center