【数据结构-初阶】详解线性表(5)---队列
🎈主页传送门:良木生香
🔥个人专栏:《C语言》 《数据结构-初阶》 《程序设计》
🌟人为善,福随未至,祸已远行;人为恶,祸虽未至,福已远离
上期回顾:在上一篇文章(【数据结构-初阶】详解栈和队列(1)---栈)中我们讲到了在顺序表与链表之外的另一种线性表---栈,知道了这是一种具有先进后出和后进先出特点的数据结构,既然有先进后出,那么肯定就有先进先出的数据结构,所以这就是我们今天要讲的------队列
一、队列的概念
既然我们想要实现先进先出的效果，那肯定就不像栈那样有一端是堵起来的，想必应该是两端都开口吧。嗯，事实确实如此。
队列：是只允许在一端进行数据的插入操作，在另一端进行数据的删除操作的一种特殊的线性表，其具有先进先出FIFO(first in first out)的结构特点.
入队列:进行插入操作的一端叫做队尾
出队列:进行删除操作的一端叫做队头
下面是队列的示意图:
名字叫做队列,其实就像我们排队一样,先排的人先得服务,后排的人后得到服务,在队列中,先进来的元素先得到操作,后进来的服务后得到操作
二、队列的实现
想要实现队列,我们就要考虑与实现栈时一样的问题,那就是:底层用数组实现还是用链表实现?
首先我们来分析一下,队列是需要在队尾和队头进行频繁操作的数据结构,队尾通常容易实现,但是相较于队头,数组要实现所需要的时间成本就要远远大于链表了,所以综上所述,我们决定用链表为底来实现队列
2.1、队列的结构
既然底层用的是链表实现，那么接涉及到节点的问题，我们依旧将队列的节点设置成与链表节点相同即可。但这时候又有一个新的问题：用单链表还是双链表？我们依旧是从队列的定义出发。既然是一端进一端出，那只用考虑头尾位置的节点就行，不会像顺序表或者链表那样涉及到pos位置的插入删除,同时兼顾运行效率,我们决定采用单链表的作为队列节点的结构,这样一来,队列节点的结构就成了这样:
//现在定义队列节点: typedef struct QueueNode { Elemtype data; //数据域 struct QueueNode* next; //指针域 }QueueNode;在队列中,哦不,应该说是在链表中,我们对于头部删除的操作是很方便的,但是队尾部插入的话就要经常遍历一遍链表然后再能进行操.像队列这种经常对队尾进行操作的数据结构,我们总不能每次插入都遍历一遍吧?这样的话真的就比老奶奶过马路还慢了,所以我们要定义一个尾指针,使它一直指向尾结点,所以下面才是队列真正的结构体:
//现在定义队列结构体: typedef struct Queue { QueueNode* phead; QueueNode* ptail; }Queue;
2.2、队列的初始化
队列的初始化与其他数据结构一样，都是对自己结构体里面的元素进行初始化，那在队列中，我们是对队列的节点进行初始化呢？还是对队列的头尾指针进行初始化呢？答案是对队列的头尾指针进行初始化，因为队列这个数据结构我们对是对头尾指针进行操作的，对于节点只是一个过程而已：
//现在初始化队列: void Init_Queue(Queue* pQueue) { pQueue->phead = pQueue->ptail = NULL; } 将两个指针置为空就行
2.3、入队
队列的入队一般是在队尾进行操作的，我们在编写代码的时候要留个心眼，如果当前队列一个元素都没有，那在插入的时候就是头尾指针指向同一个节点，如果队列中已经有元素了，那就只用对尾指针进行操作，最后记得将尾指针指向最新的节点下面是具体代码：
//现在是入队列 void Push_Queue(Queue* pQueue,Elemtype data) { assert(pQueue); //创建新节点 QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); if (newNode == NULL) { printf("新节点创建失败....\n"); return; } newNode->data = data; newNode->next = NULL; if (pQueue->phead == NULL) { //说明是头节点 pQueue->phead = pQueue->ptail = newNode; } //ptail newNode pQueue->ptail->next = newNode; pQueue->ptail = newNode; size++; //这是用来记录当前队列有效元素个数的变量的 }
2.4、出队
出队一般来说是对头指针进行操作的，与入队一样，我们也考虑到当队列中只有一个元素时，释放完头指针，要将头指针与尾指针同时置为NULL，如果队列中不止一个元素，那就只用对头指针进行操作，然后将头指针指向下一个元素，下面是具体的代码：
//出队列 void Pop_Queue(Queue* pQueue) { assert(pQueue); if (pQueue->phead == NULL) { printf("当前队列为空,无法出队...\n"); return; } //如果只有一个节点 if (pQueue->phead == pQueue->ptail) { free(pQueue->phead); pQueue->phead = pQueue->ptail = NULL; } //phead phaed->next //delet phead else { QueueNode* delet = pQueue->phead; pQueue->phead = pQueue->phead->next; free(delet); delet = NULL; } size--; //这是用来记录当前队列中有效元素个数的变量 }
2.5、取队头队尾数据：
这个操作相对简单一点，我们只用返回队头队尾的节点元素即可，代码如下：
//取队头元素 Elemtype Get_first_elem(Queue* pQueue) { assert(pQueue); return pQueue->phead->data; } //取队尾元素 Elemtype Get_tail_elem(Queue* pQueue) { assert(pQueue); return pQueue->ptail->data; } 这里要注意的是，我们在设计返回类型的时候，要将返回值设置为我们想要的类型，在这里我提前将int 类型重命名为了Elmetype ,在代码总和那一块我会展示出来。
2.6、队列中有效的元素个数
在这个操作中，我们有两种操作方式，第一种就是传统的使用遍历的方式，将节点数一一记录下来；第二种就是在入队的时候用一个变量size++,在出队的时候对size--,这样就能实时更新队列中的元素个数了,第二种方式在返回个数的时候要比第一种快很多,下面是两种代码的展示:
//第一种的传统方式: //计算队列中有效的元素个数 int Size_Queue(Queue* pQueue) { assert(pQueue); int size = 0; QueueNode* pcur = pQueue->phead; while (pcur) { size++; pcur = pcur->next; } return size; } //第二种返回方式 int Size_Queue(Queue* pQueue,int size){ assert(pQueue)); return size; }
2.7、队列的销毁
队列的销毁与链表的销毁相同，用遍历指针逐一将节点一一销毁，最后将头尾指针置为NULL:
void Destory_Queue(Queue* pQueue) { assert(pQueue); QueueNode* pcur = pQueue->phead; while (pcur) { QueueNode* delet = pcur; pcur = pcur->next; free(delet); delet = NULL; } pQueue->phead = pQueue->ptail = NULL; }要提醒的是,一定要将头尾指针置为NULL,不要这两个指针会成为野指针!!!!
三、综合代码
#define _CRT_SECURE_NO_WARNINGS 520 #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<windows.h> typedef int Elemtype; //现在定义队列节点: typedef struct QueueNode { Elemtype data; //数据域 struct QueueNode* next; //指针域 }QueueNode; //现在定义队列结构体: typedef struct Queue { QueueNode* phead; QueueNode* ptail; }Queue; //现在初始化队列: void Init_Queue(Queue* pQueue) { pQueue->phead = pQueue->ptail = NULL; } //现在是入队列 void Push_Queue(Queue* pQueue,Elemtype data) { assert(pQueue); //创建新节点 QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode)); if (newNode == NULL) { printf("新节点创建失败....\n"); return; } newNode->data = data; newNode->next = NULL; if (pQueue->phead == NULL) { //说明是头节点 pQueue->phead = pQueue->ptail = newNode; } //ptail newNode pQueue->ptail->next = newNode; pQueue->ptail = newNode; } //出队列 void Pop_Queue(Queue* pQueue) { assert(pQueue); if (pQueue->phead == NULL) { printf("当前队列为空,无法出队...\n"); return; } //如果只有一个节点 if (pQueue->phead == pQueue->ptail) { free(pQueue->phead); pQueue->phead = pQueue->ptail = NULL; } //phead phaed->next //delet phead else { QueueNode* delet = pQueue->phead; pQueue->phead = pQueue->phead->next; free(delet); delet = NULL; } } //取队头元素 Elemtype Get_first_elem(Queue* pQueue) { assert(pQueue); return pQueue->phead->data; } //取队尾元素 Elemtype Get_tail_elem(Queue* pQueue) { assert(pQueue); return pQueue->ptail->data; } //计算队列中有效的元素个数 int Size_Queue(Queue* pQueue) { assert(pQueue); int size = 0; QueueNode* pcur = pQueue->phead; while (pcur) { size++; pcur = pcur->next; } return size; } void Destory_Queue(Queue* pQueue) { assert(pQueue); QueueNode* pcur = pQueue->phead; while (pcur) { QueueNode* delet = pcur; pcur = pcur->next; free(delet); delet = NULL; } pQueue->phead = pQueue->ptail = NULL; } //现在是打印队列 void my_printf(Queue* pQueue) { assert(pQueue); if (pQueue->phead == NULL) { printf("当前队列为空,无法打印...\n"); return; } else { QueueNode* pcur = pQueue->phead; while (pcur) { printf("%d ", pcur->data); pcur = pcur->next; } } } //现在是打印菜单 void printf_menu() { printf("=========================================\n"); printf("1.入队 2.出队\n"); printf("3.取队头元素 4.取队尾元素\n"); printf("5.计算队列元素个数\n"); printf("=========================================\n"); printf("\n"); } int main() { Queue L; Queue* pQueue = &L; Init_Queue(pQueue); int choose; do { system("cls"); printf_menu(); printf("当前的队列为:\n"); my_printf(pQueue); printf("\n"); printf("请输入你的选择:\n"); scanf("%d", &choose); switch (choose) { case 1: { printf("请输入你想输入的元素个数:\n"); int num = 0; scanf("%d", &num); Elemtype data = 0; printf("请输入你想输入的元素:\n"); for (int i = 0; i < num; i++) { scanf("%d", &data); Push_Queue(pQueue, data); } printf("正在输入...\n"); Sleep(1000); printf("输入成功~\n"); Sleep(2000); break; } case 2: { printf("正在出队...\n"); Sleep(1000); Pop_Queue(pQueue); printf("出队成功~\n"); Sleep(2000); break; } case 3: { Elemtype elem = Get_first_elem(pQueue); printf("正在取出对队头元素...\n"); Sleep(1000); printf("队头元素为: %d", elem); Sleep(2000); break; } case 4: { Elemtype elem = Get_tail_elem(pQueue); printf("正在取出对队尾元素...\n"); Sleep(1000); printf("队尾元素为: %d", elem); Sleep(2000); break; } case 5: { printf("正在计算队列大小...\n"); int num = Size_Queue(pQueue); Sleep(1000); printf("队列的大小为: %d", num); Sleep(1000); break; } case -1: { printf("正在退出程序...\n"); Sleep(1000); printf("退出成功~\n"); Sleep(500); } } } while (choose != -1); Destory_Queue(pQueue); return 0; }以上就是我对队列基本知识的分享了，感谢大家的阅读~~~
文章是自己写的哈，有什么描述不对的、不恰当的地方，恳请大佬指正，看到后会第一时间修改，感谢您的阅读。
