数据结构之队列
前言
今天学习数据结构中另一种特殊的线性表——队列。 我们平时在医院、银行等地方办理业务时，先排队在抽号机进行抽号，服务窗口会根据号码的顺序叫号，再为我们进行业务办理。 其中抽号机的工作原理就类似于是队列，先进入的数据先出（先抽号的人先服务），遵循了先来后到，确保了公平性。
一、队列
只允许在一端进行插入数据的操作，在另一端进行删除数据的操作的特殊线性表。 队列中的元素遵循先进先出（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;
}四、相关习题
到这篇文章，我们已经了解了很多栈和队列的相关知识，所以我在这里同大家分享一些与栈和队列有关的概念性的选择题，以便让大家对这些知识掌握更加熟练。 大家可以先自己尝试着做一下这些选择题，我也会将它们的答案公布在下一篇博客的评论区里。
总结
以上就是今天要讲的内容，本文介绍了数据结构中的队列。对队列的概念以及它的具体实现都进行了讲解。大家感兴趣的也可以根据作者所写思路自行实现。 本文作者目前也是正在学习数据结构的知识，如果文章中的内容有错误或者不严谨的部分，欢迎大家在评论区指出也欢迎大家在评论区提问、交流。 最后，如果本篇文章对你有所启发的话，也希望可以多多支持作者，谢谢大家！
腾讯云开发者
