前言
今天学习数据结构中另一种特殊的线性表——队列。
我们平时在医院、银行等地方办理业务时，先排队在抽号机进行抽号，服务窗口会根据号码的顺序叫号，再为我们进行业务办理。
其中抽号机的工作原理就类似于是队列，先进入的数据先出（先抽号的人先服务），遵循了先来后到，确保了公平性。
一、队列
只允许在一端进行插入数据的操作，在另一端进行删除数据的操作的特殊线性表。
队列中的元素遵循先进先出（FIFO）的原则。
对队列的操作：
1.入队列：在插入数据的一端插入数据（队尾）；
2.出队列：在删除队列的一端删除数据（队头）。
二、队列应该如何实现
顺序表or链表
队列也可以数组和链表的结构实现，使用链表的结构实现更优一些。因为如果使用数组的结构，出队列在数组上进行头删数据，效率会比较低。
扩展了解
实际中我们有时还会使用一种队列叫循环队列。如操作系统中的生产者消费者模型就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现。
三、队列的实现
1.队列的声明
typedef int QueueNodeType; typedef struct QueueNode//队列节点 { QueueNodeType node;//存储数据的节点 struct QueueNode* next;//指向下一个节点 }QueueNode; typedef struct Queue//队列 { QueueNode* head;//指向头结点 QueueNode* tail;//指向尾节点 int size;//队列中的元素个数 }Queue;
2.接口（声明）
//队列的初始化 void QueueInit(Queue* ps); //出队 void QueuePop(Queue* ps); //入队 void QueuePush(Queue* ps, QueueNodeType x); //销毁队列 void QueueDistory(Queue* ps); //队头元素 QueueNodeType QueueFront(Queue* ps); //判断队列为空(空就返回1，非空就返回0) bool QueueEmpty(Queue* ps);
3.接口的实现
void QueueInit(Queue* ps) { assert(ps); ps->head = ps->tail = NULL; ps->size = 0; }
创建一个新的节点
QueueNode* QueueBuyNode(QueueNodeType x) { QueueNode* t = (QueueNode*)malloc(sizeof(QueueNode)); if (t == NULL) { perror("malloc fail"); } t->node = x; t->next = NULL; return t; }
判断队列为空
(空就返回1，非空就返回0)
bool QueueEmpty(Queue* ps) { return ps -> tail == NULL &&ps -> head == NULL; }
队头元素
QueueNodeType QueueFront(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); return ps->head->node; }
入队
void QueuePush(Queue* ps, QueueNodeType x) { QueueNode* newnode = QueueBuyNode(x); if (ps->tail == NULL) { ps->head = ps->tail = newnode; } else { ps->tail->next = newnode; ps->tail = newnode; } ps->size++; }
出队
void QueuePop(Queue* ps) { assert(ps); assert(!QueueEmpty(ps)); if (ps->head->next == NULL) { free(ps->head); ps->head = ps->tail = NULL; } else { QueueNode* temp = ps->head; ps->head = ps->head->next; free(temp); temp = NULL; } ps->size--; }
销毁队列
void QueueDistory(Queue* ps) { assert(ps); QueueNode* cur = ps->head; while (cur) { QueueNode* del = cur; cur = cur->next; free(del); } ps->head = ps->tail = NULL; }
注意：
使用某些库函数时要记得包含它对应的头文件，我也给大家整理了本次所需要的头文件。
#include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h>
4.主函数（测试）
测试队列的相应功能，以下是我使用的主函数，大家也可以根据需要进行修改，测试其他的测试用例。
void test() { Queue ps; QueueInit(&ps);//初始化队列 QueuePush(&ps, 1); QueuePush(&ps, 2); QueuePush(&ps, 13); QueuePush(&ps, 14); //打印队列元素(遍历一边队列的元素，实质上就是出队列) while (!QueueEmpty(&ps)) { printf("%d ", QueueFront(&ps)); QueuePop(&ps); } QueueDistory(&ps);//销毁队列 } int main() { test(); return 0; }
四、相关习题
到这篇文章，我们已经了解了很多栈和队列的相关知识，所以我在这里同大家分享一些与栈和队列有关的概念性的选择题，以便让大家对这些知识掌握更加熟练。
大家可以先自己尝试着做一下这些选择题，我也会将它们的答案公布在下一篇博客的评论区里。
总结
以上就是今天要讲的内容，本文介绍了数据结构中的队列。对队列的概念以及它的具体实现都进行了讲解。大家感兴趣的也可以根据作者所写思路自行实现。
本文作者目前也是正在学习数据结构的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出也欢迎大家在评论区提问、交流。
最后，如果本篇文章对你有所启发的话，也希望可以多多支持作者，谢谢大家！
