本篇博客我要來和大家一起聊一聊資料結構中的堆疊和佇列相關知識，一種是先進后出的結構，另一種是先進先出的結構，
博客代碼已上傳至：https://gitee.com/byte-binxin/data-structure/tree/master/stack_queue

堆疊

堆疊的概念和結構

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）加粗樣式的原則，
入堆疊：從堆疊頂放入資料的操作，
出堆疊：從堆疊頂取出元素的操作，

堆疊的實作

堆疊用鏈表和順序表兩種資料結構都可以實作，我們要確定選擇哪一種更優，我們來分析一下，
鏈表堆疊：如果選擇單鏈表的話，我們應該選擇頭當堆疊頂，尾當堆疊底，不然的話，每次存取資料都要遍歷一遍鏈表，所以選雙鏈表會比較好一點，
陣列堆疊：訪問堆疊頂的時間復雜度為O(1)，相比鏈表堆疊比較優，
所以下面我們用順序表來實作堆疊的這種資料結構，
結構如下：

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	int top;
	int capcaity;
}Stack;

堆疊的介面

堆疊要實作的介面有以下幾個：

//初始化堆疊
void StackInit(Stack* ps);
//銷毀堆疊
void StackDestroy(Stack* ps);
//壓堆疊
void StackPush(Stack* ps, STDatatype x);
//出堆疊
void StackPop(Stack* ps);
//取出堆疊頂元素
STDatatype StackTop(Stack* ps);
//堆疊的大小
int StackSize(Stack* ps);
//判斷堆疊是否為空
bool StackEmpty(Stack* ps);

堆疊的初始化

初始化堆疊就是把結構體中的成員都初始化一下，方便后續的擴容等操作，
具體實作如下：

void StackInit(Stack* ps)
{
	assert(ps);
	
	ps->a = NULL;
	ps->capcaity = ps->top = 0;
}

壓堆疊

壓堆疊就是在堆疊頂插入元素，其中是肯定要考慮到擴容的問題，當ps->top == ps->capcaity時，就要考慮到擴容了，擴容也是像之前順序表那樣每次擴一倍，這樣可以一定程度地減少擴容次數，但同時是會帶來一定的空間消耗的，

具體實作如下：

void StackPush(Stack* ps, STDatatype x)
{
	assert(ps);
	if (ps->top == ps->capcaity)
	{
		ps->capcaity = ps->capcaity == 0 ? 4 : 2 * ps->capcaity;
		STDatatype* tmp = (STDatatype*)realloc(ps->a ,ps->capcaity*sizeof(STDatatype));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = tmp;
	}
	ps->a[ps->top] = x;
	ps->top++;

}

出堆疊

出堆疊就是在堆疊頂pop掉一個元素，也就是top-1指向的位置，只需要將top進行一個減1的操作即可，
與此同時，我們要確保此次堆疊不為空，所以要進行斷言的操作，防止程式崩潰，

具體實作如下：

void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	ps->top--;
}

取出堆疊頂元素

直接回傳top-1位置的元素即可，與此同時，我們要確保此次堆疊不為空，所以要進行斷言的操作，防止程式崩潰，
具體實作如下：

STDatatype StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top > 0);
	return ps->a[ps->top - 1];
}

堆疊的大小

top的大小就是堆疊的大小，所以我們直接回傳top的大小就可以了，
具體實作如下;

int StackSize(Stack* ps)
{
	return ps->top;
}

判斷堆疊是否為空

我們回傳ps->top == 0運算式的值，為真就是空，為假就是不為空，
具體實作如下：

bool StackEmpty(Stack* ps)
{
	return ps->top == 0;
}

堆疊的銷毀

為了防止記憶體泄漏，動態記憶體申請的空間一定要我們自己手動釋放，養成一個良好的習慣，

void StackDestroy(Stack* ps)
{
	assert(ps);

	free(ps->a);
	ps->capcaity = ps->top = 0;
}

到這里，堆疊的實作就聊完了，接下來我們來看一看佇列的結構和實作，

佇列

佇列的概念和結構

佇列：只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(First In First Out) 入佇列：進行插入操作的一端稱為隊尾 出佇列：進行洗掉操作的一端稱為隊頭，

佇列的結構，我們選取單鏈表來實作，秩序進行頭刪和為插的不足即可，如果選陣列，那么每一次刪頭我們都要挪動一遍資料，這種方式不優，所以我們還是選取用單鏈表來實作，
定義的結構如下：

typedef int QDataType;
//節點
typedef struct QueueNode
{
	QDataType data;
	struct QueueNode* next;
}QueueNode;
//佇列
typedef struct Queue
{
	QueueNode* head;
	QueueNode* tail;
}Queue;

佇列的實作

佇列的介面

// 初始化佇列
void QueueInit(Queue* q);
// 隊尾入佇列
void QueuePush(Queue* q, QDataType data);
// 隊頭出佇列
void QueuePop(Queue* q);
// 獲取佇列頭部元素
QDataType QueueFront(Queue* q);
// 獲取佇列隊尾元素
QDataType QueueBack(Queue* q);
// 獲取佇列中有效元素個數
int QueueSize(Queue* q);
// 檢測佇列是否為空，如果為慷訓傳非零結果，如果非慷訓傳0
int QueueEmpty(Queue* q);
// 銷毀佇列
void QueueDestroy(Queue* q);

佇列的初始化

初始化很簡單，只要將頭指標和尾指標都置空，

void QueueInit(Queue* q)
{
	assert(q);

	q->head = q->tail = NULL;
}

入隊

入隊其實就是單鏈表尾插的操作，要分鏈表為空和不為空兩種情況討論，
為空時要改變頭指標的指向，不為空就不需要了，

具體實作如下：

void QueuePush(Queue* q, QDataType x)
{
	assert(q);

	QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
	if (newNode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newNode->data = x;
	newNode->next = NULL;
	//佇列為空時
	if (q->head == NULL)
	{
		q->head = q->tail = newNode;
	}
	else
	{
		q->tail->next = newNode;
		q->tail = newNode;
	}

}

出隊

出隊就是進行單鏈表尾刪的操作，要考慮鏈表為空時不能進行洗掉，還要注意的是只有一個節點進行洗掉是要改變尾指標的指向，

具體實作如下：

void QueuePop(Queue* q)
{
	assert(q);
	assert(q->head != NULL);

	QueueNode* next = q->head->next;
	free(q->head);
	q->head = next;
	//刪最后一個節點要將tail置空
	if (q->head == NULL)
	{
		q->tail = NULL;
	}

}

獲取隊頭元素和隊尾元素

首先要確保鏈表不為空，對頭就是回傳頭節點的大小，隊尾就是回傳尾節點的大小，
具體實作如下：

// 獲取佇列頭部元素
QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(q->head != NULL);

	return q->head->data;
}
// 獲取佇列隊尾元素
QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(q->tail != NULL);

	return q->tail->data;
}

獲取佇列元素個數

遍歷一遍鏈表，同時進行計數操作，最后回傳計數結果即可，
具體實作如下：

int QueueSize(Queue* q)
{
	assert(q);
	int size = 0;
	QueueNode* cur = q->head;
	while (cur)
	{
		cur = cur->next;
		size++;
	}
	return size;
}

判斷佇列是否為空

我們可以直接回傳運算式QueueSize(q) == 0的值，空就回傳1，否則就回傳0，
具體試下如下：

int QueueEmpty(Queue* q)
{
	assert(q);
	return QueueSize(q) == 0;
}

佇列的銷毀

為了防止記憶體泄漏，動態記憶體申請的空間一定要我們自己手動釋放，養成一個良好的習慣，所以要將鏈表的空間逐個釋放，
具體實作如下：

void QueueDestroy(Queue* q)
{
	assert(q);

	QueueNode* cur = q->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}
	q->head = q->tail = NULL;
}

總結

堆疊和佇列就先聊到這，佇列里面還有一種回圈佇列，我沒有介紹，在后期博客中我會跟大家聊一聊這個話題，還有如何用兩個堆疊實作佇列，用兩個佇列實作堆疊，我在后面的博客中會給大家介紹，如果喜歡的話，歡迎點贊支持和指正~