目录
1.摘要
2.银行排队取票机的原理
3.队列的概念
4.队列的代码实现
4.1.队列结构体
4.2.头文件
4.3.接口文件
4.4.测试文件
1.摘要
本文主要介绍队列的概念以及队列的代码实现
2.银行排队取票机的原理
最近临近开学，大一的小伙伴们一定在收到录取通知书的同时，也受到了一张来自学校的学子卡吧，那大家有没有亲自去线下网点激活学子卡呢？
我一踏进银行的自动门，工作人员就让我在前面的一台机器上扫码区号了。哦，我之前还真没来过银行，第一次见这个取号机。取号机吐出来一张写有号码的单子，然后等到柜台工作人员用电子提示音叫到你的号码时，就是轮到你去办理业务了。
那我不禁在想了，为什么银行要推出这样一台排队取票机呢？
放在以前，来到银行，都是往一个柜台后面排队，等排前面的人办理完了，自然轮到了你。但大家有没有想过，比如你和你的朋友恰好都来银行办理业务，你在1号窗口排队，你的朋友比你晚到10分钟，在2号窗口排队。这时，1号窗口排在你的前面的客户出了点问题，工作人员花了半个小时才解决了问题。这时，你转头一看，你的朋友已经办完业务转身离开了，而你还在排队！
明明你比你朋友先到的啊！
于是，银行为了保证先来后到的公平，推出了排队取票机。先来的人领取到号小的票，后来的人领取到号大的票，只要柜台一有空闲，
柜员就会按按钮让当前等候的手持号最小票的客户上前办理业务。
“请xx号客户前往xx号柜台办理业务···请xx号客户前往xx号柜台办理业务···”
这就避免了业务办理速度对排队公平的影响。
3.队列的概念
谈了这么一大堆，有人不禁要问了：我们今天不是要聊队列的吗？队列在哪里啊？
唉，别急啊，队列，排队排好，先来后到，难道不是队列了吗？
让我们先给出队列的定义：队列是只允许一端进行插入数据操作，另一端进行删除数据操作的特殊线性表。
队列具有先进先出的性质(First in First out)。
数据入队列的一端叫做队尾，数据出队列的一端叫做队头。
再次想象一下银行排队的问题，我们把一个个排队的客户想象成一个个数据元素。
现在，取票机组建了一个队列。先来的客户先进入队列，后来的客户后进入队列。
当柜员叫号时，叫的永远是位于队头的客户的号码，该客户便出队列。如果又来了一个新客户，那么他取号后，便在队尾入队列。
循此以往，先来后到的准则将被严格地遵守。
先进先出！先进先出！先进先出！重要的事情说三遍！
4.队列的代码实现
4.1.队列结构体
我们想一下，队列最最重要的操作是什么呢？
对了，是入队列和出队列
入队列是在队头，需要操作头部元素。出队列是在队尾，需要操作尾部元素。
我们知道，队列是特殊的线性表。那么想一下，如果用顺序表来实现的话，头插操作的时间复杂度华为O(N)，太麻烦了。那改用链表呢？有人说，链表的尾插不也是O(N)的时间复杂度吗？对，那么，我们就在头指针的基础上，再加一个尾指针！
既有头指针，又有尾指针，那何不把头指针和尾指针封装到同一个结构体里去呢？
这样的操作带来了另外一个好处：只需传入该结构体的地址，就能修改头/尾指针以及头尾指针对应的节点的内容，避免了使用二级指针带来的不便。
于是，便有了一下的结构体的创建：
a)队列节点的结构体
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QueueNode;
b)队列头/尾指针的结构体
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
4.2.头文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QueueDataType;
typedef struct QueueNode
{
QueueDataType data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
QueueNode* head;
QueueNode* tail;
}Queue;
void QueueInit(Queue* que);
void QueueDestroy(Queue* que);
void QueuePush(Queue* que, QueueDataType x);
void QueuePop(Queue* que);
QueueDataType QueueTop(Queue* que);
int QueueEmpty(Queue* que);
size_t QueueSize(Queue* que);
4.3.接口文件
void QueueInit(Queue* que)
{
assert(que);
que->head = NULL;
que->tail = NULL;
}
void QueueDestroy(Queue* que)
{
assert(que);
QueueNode* cur = que->head;
while (cur)
{
QueueNode* next = cur->next;
free(cur);
cur = next;
}
que->tail = NULL;
}
void QueuePush(Queue* que, QueueDataType x)
{
assert(que);
if (que->head == NULL)
{
que->head = que->tail = (QueueNode*)malloc(sizeof(QueueNode));
que->head->data = x;
que->head->next = NULL;
}
else
{
que->tail->next = (QueueNode*)malloc(sizeof(QueueNode));
que->tail = que->tail->next;
que->tail->data = x;
que->tail->next = NULL;
}
}
void QueuePop(Queue* que)
{
assert(que);
assert(!QueueEmpty(que));
QueueNode* next = que->head->next;
free(que->head);
que->head = next;
}
QueueDataType QueueTop(Queue* que)
{
assert(que);
assert(!QueueEmpty(que));
return que->head->data;
}
int QueueEmpty(Queue* que)
{
return que->head == NULL;
}
size_t QueueSize(Queue* que)
{
assert(que);
QueueNode* cur = que->head;
size_t count = 0;
while(cur)
{
++count;
cur = cur->next;
}
return count;
}
4.4.测试文件
void Test1()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
printf("%d\n", QueueSize(&q));
printf("%d\n", QueueTop(&q));
QueuePop(&q);
printf("%d\n", QueueTop(&q));
QueuePop(&q);
printf("%d\n", QueueTop(&q));
QueuePop(&q);
printf("%d\n", QueueTop(&q));
QueuePop(&q);
printf("%d\n", QueueSize(&q));
QueueDestroy(&q);
}
int main()
{
Test1();
return 0;
}