有趣的数据结构算法13——队列的初始化、入队与出队

水深无声 2021-11-10 05:32 513阅读 0赞

### 有趣的数据结构算法13——队列的初始化、入队与出队 ###

*  什么是队列
 *   *  队列的初始化
     *  入队
     *  出队
 *  实现代码
 *  GITHUB下载连接

前两天出去找女朋友玩了，过两天又可以去旅游了，回来还是要好好学习呀！新的结构又要出现了。我心里有点害怕，但是！  
![在这里插入图片描述][20190723170158884.jpg_pic_center]

# 什么是队列 #

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。  
假设一个队列里面有元素1、2、3、4、5，其具体情况如图所示：  
![队列][20190802095509420.png]  
当我们需要入队的时候，其元素处于队尾方向。  
![入队][20190802095657221.png]  
从队尾入队，其入队结果如图所示。  
![入队2][2]  
当我们需要出队的时候，其元素从队头出队。其入队示意图如图所示。  
![出队][20190802095830417.png]

## 队列的初始化 ##

对队列进行操作前要定义队列的结构体。

struct Node{
        
    	Ele data;
    	struct Node* Next;		//data用于存储信息，Next用于存储下一个结点的地址。
    };
    
    typedef struct Node* LinkedList;
    
    struct Queue{
        
    	LinkedList head;
    	LinkedList tail;		//head为队头，tail为队尾。
    };
    
    typedef struct Queue QueueList;

Node结构体定义的是队列的每一个结点的结构体，其中有两个元素，分别是data和Next，data用于存储信息，Next用于存储队列下一个结点的地址。  
Queue结构体中分别存储了每一个队列的队头与队尾，其中有两个元素，分别是head和tail，head为队头，tail为队尾。  
初始化的过程可以分为两步，分别为：  
**1、申请空间**  
**2、队头与队尾同时指向该空间**

void init(QueueList* q){
        
    	q->head = q->tail = (LinkedList)malloc(sizeof(struct Node));
    	if (q->head == NULL){
        
    		printf("内存空间分配失败");
    		exit(1);
    	}
    	q->head->Next = NULL;
    }

## 入队 ##

如何进行入队呢？从入队函数出发，入队函数需要输入一个队列和一个入队的元素。

void push(QueueList* q,Ele e);

元素入队的过程也可以分为三步，分别为：  
**动态申请空间**  
**将元素压入队列**  
**将队尾指针指向新节点**

void push(QueueList* q,Ele e){
        
    	LinkedList p;
    	p = (LinkedList)malloc(sizeof(struct Node));
    	if (p == NULL){
        
    		printf("内存空间分配失败");
    		exit(1);
    	}
    	p->Next = NULL;
    	p->data = e;
    
    	q->tail->Next = p;	//将元素压入队列、将队尾指针指向新节点
    	q->tail = p;
    }

## 出队 ##

如何进行出队呢？从出队函数出发，出队函数需要输入一个队列和一个接收信息的元素。

void pop(QueueList* q, Ele* e);

元素出队的过程也可以分为三步，分别为：  
**判断队列是否空，是则报错**  
**通过中间节点取出队头**  
**释放中间节点**

void pop(QueueList* q, Ele* e){
        
    	LinkedList p;
    	if (q->head == q->tail){
        
    		printf("队列已空");
    		exit(1);
    	}
    	p = q->head->Next;
    	q->head->Next = p->Next;	//利用p取出队头
    	*e = p->data;				//信息存入元素e
    	if (q->tail == p){
        
    		q->tail = q->head;		//判断是否取出所有元素，如果取出所有元素，队头指向队尾
    	}
    	free(p);					//释放中间节点
    }

# 实现代码 #

#include <stdio.h>
    #include <stdlib.h>
    
    typedef int Ele;
    
    struct Node{
        
    	Ele data;
    	struct Node* Next;		//data用于存储信息，Next用于存储下一个队列下一个元素的地址。
    };
    
    typedef struct Node* LinkedList;
    
    struct Queue{
        
    	LinkedList head;
    	LinkedList tail;		//head为队头，tail为队尾。
    };
    
    typedef struct Queue QueueList;
    
    void init(QueueList* q){
        
    	q->head = q->tail = (LinkedList)malloc(sizeof(struct Node));
    	if (q->head == NULL){
        
    		printf("内存空间分配失败");
    		exit(1);
    	}
    	q->head->Next = NULL;
    }
    
    void push(QueueList* q,Ele e){
        
    	LinkedList p;
    	p = (LinkedList)malloc(sizeof(struct Node));
    	if (p == NULL){
        
    		printf("内存空间分配失败");
    		exit(1);
    	}
    	p->Next = NULL;
    	p->data = e;
    
    	q->tail->Next = p;	//将元素压入队列、将队尾指针指向新节点
    	q->tail = p;
    }
    
    void pop(QueueList* q, Ele* e){
        
    	LinkedList p;
    	if (q->head == q->tail){
        
    		printf("队列已空");
    		exit(1);
    	}
    	p = q->head->Next;
    	q->head->Next = p->Next;	//利用p取出队头
    	*e = p->data;				//信息存入元素e
    	if (q->tail == p){
        
    		q->tail = q->head;		//判断是否取出所有元素，如果取出所有元素，队头指向队尾
    	}
    	free(p);					//释放中间节点
    }
    
    void release(QueueList* q){
        
    	LinkedList p;
    	p = q->head;
    	while (p){
        
    		q->head = q->head->Next;
    		free(p);
    		
    		p = q->head;
    	}
    }
    
    int main(){
        
    	QueueList q;
    	int num,i;
    	Ele e;
    	init(&q);
    	printf("请输入你要输入几个数字：");
    	scanf("%d", &num);
    	for (i = 0; i < num; i++){
        
    		scanf("%d", &e);
    		push(&q, e);
    	}
    	for (i = 0; i < num; i++){
        
    		pop(&q, &e);
    		printf("%d\n", e);
    	}
    
    
    
    	return 0;
    }

# GITHUB下载连接 #

https://github.com/bubbliiiing/Data-Structure-and-Algorithm

希望得到朋友们的喜欢。  
有问题的朋友可以提问噢。

[20190723170158884.jpg_pic_center]: /images/20211109/eae12052c4ec450d98c93678716a0fae.png
[20190802095509420.png]: /images/20211109/da196c1605ed48428cc607e948796c08.png
[20190802095657221.png]: /images/20211109/977d47db81784bd2bedba61f89b578e2.png
[2]: /images/20211109/d96fbccac2b84995ae35d9fa53682a52.png
[20190802095830417.png]: /images/20211109/361bb819d0634db7803d05142b8690f8.png