目錄

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;
}