一、前言

我們在學習堆疊和佇列的內容前，我們先簡單講述一下我們計算機的記憶體劃分，下面是我們計算機記憶體的簡單圖解：

如果我們讀者對順序表和鏈表的內容不太熟悉的話，建議先對順序表和單鏈表中常見介面進行復習，因為我們堆疊和佇列的實作與介面的實作與上述兩者緊密相關

順序表講解：https://blog.csdn.net/weixin_52664715/article/details/120318125?spm=1001.2014.3001.5501

單鏈表講解：https://blog.csdn.net/weixin_52664715/article/details/120336834?spm=1001.2014.3001.5501

堆疊幀的創建與銷毀：https://blog.csdn.net/weixin_52664715/article/details/120395859?spm=1001.2014.3001.5501

二、堆疊

①堆疊的概念

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

壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，
出堆疊：堆疊的洗掉操作叫做出堆疊，出資料也在堆疊頂，

圖解：

②堆疊的實作

通過上面的講述我們知道了堆疊的結構特點是先進后出，那么相對于我們之前學習的順序表和鏈表中的增刪查改操作而言，這里我們不存在對堆疊的頭位置（即堆疊底：最開始的位置）頭插和頭刪操作；

而這個時候我們思考我們學過的順序結構：順序表和鏈表，這個時候我們再對我們這兩個結構進行分析：

1. 當我們使用鏈表時，因為我們是將先放入的元素作為首元素，那么這個元素就將進入我們堆疊幀中的堆疊底位置，也就是我們的首節點，而這個時候我們要實作想堆疊幀中插入元素或者獲得堆疊頂元素，那么我們就需要一個指標去指向我們鏈表中的尾位置，也就是我們的堆疊頂位置，這個時候我們的效率比較低效，

2.當我們使用順序表時，我們回顧我們順序表中結構體的內容，一個指標去指向我們的陣列，一個變數top去定義我們的陣列中當前順序表中元素的個數（堆疊中對應我們堆疊頂的位置），一個變數capacity去定義我們當前陣列的最大存盤容量，那么這個時候我們只需要去獲得我們當前順序表中的top，其實我們也就獲得了當前堆疊中的堆疊頂位置，我們也就可以進行我們的堆疊幀中放進元素，以及獲取堆疊頂元素等操作，所以當我們使用順序表來實作我們的堆疊時效率更高，

綜上，我們得出我們要想實作我們的堆疊幀，我們采用順序表來實作
如果對順序表的實作不太熟悉的讀者，可以看一下這篇博客
https://blog.csdn.net/weixin_52664715/article/details/120318125?spm=1001.2014.3001.5501
如果比較熟悉我們順序表的內容，那么我們在實作堆疊中的介面時，就會十分得心應手，

三、堆疊的常見介面

3.1堆疊的定義

在這里我們堆疊的結構體的定義本質上和我們的順序表相同

//舉例代碼：
typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;//我們創建指標去指向我們的動態陣列
	//如果我們想要定義靜態陣列STDatatype a[N]
	int top;//堆疊頂的位置
	int capacity;//堆疊的容量
}ST;

3.2堆疊的初始化

這里堆疊的初始化依然和我們順序表中的初始化操作相同，下面相同的步驟不在過多講述，當有不同內容是我會進行講解

//舉例代碼：
oid StackInit(ST* ps)
{
	assert(ps);

	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

3.3堆疊的銷毀

我們需要將我們的動態陣列進行空間釋放，所以我們需要手動free釋放我們的空間

//舉例代碼：
void StackDestory(ST* ps)
{
	assert(ps);
	if (ps->a)
	{
		free(ps->a);
	}
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

3.4堆疊的插入元素

這里我們的堆疊的插入元素和我們順序表中的多種位置的插入元素不同，這里我們只能在堆疊頂位置進行元素的插入，也就是我們陣列的尾位置"&a[top]"

//舉例代碼：
void StackPush(ST* ps, STDatatype x)
{
	assert(ps);
	//檢查空間是否增容
	if (ps->top == ps->capacity)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//三目運算：若我們的陣列大小為0，我們將空間大小賦值為4個空間大小；若是我們的空間已經充滿，我們將我們的空間容量擴大一倍
		STDatatype* tmp = realloc(ps->a, sizeof(STDatatype*)*newcapacity);
		if (tmp == NULL)
		{
			printf("realloc fail \n");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newcapacity;
	}
	ps->a[ps->top] = x;//在堆疊頂位置插入元素
	ps->top++; //將我們的堆疊的堆疊頂位置上移一個單位
}

3.5堆疊的洗掉元素

這里我們要想實作堆疊的元素洗掉，洗掉的位置也同樣只能是我們的堆疊頂位置，所以我們只需要將我們的堆疊頂位置下移一個單位即可

//舉例代碼：
void StackPop(ST* ps)
{
	assert(ps);
	assert(!StackEmpty(ps));
	--ps->top;//堆疊頂位置下一個單位
}

3.6堆疊的長度

我們只需要獲取我們堆疊頂的位置，即就是我們的堆疊的長度

//舉例代碼：
int StackSize(ST* ps)//個數
{
	assert(ps);
	return ps->top;//錯誤點：top是int型的資料，并非指標后移，每當增加一個元素，top就++；
}

3.7堆疊的判空

當我們標記我們堆疊頂的變數為0時，我們堆疊幀中沒有存盤任何元素，那么這個時候我們就可以判讀我們的堆疊幀為空

//舉例代碼：
bool StackEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

3.8堆疊的堆疊頂元素獲取

當我們要實作獲取我們的堆疊頂元素，只要找到我們陣列中對應堆疊頂下標的元素即可

//舉例代碼：
STDatatype StackTop(ST* ps)//取堆疊頂資料
{
	assert(ps);
	assert(!StackEmpty(ps));

	return ps->a[ps->top - 1];//這個時候因為我們的陣列下標從0開始，所以我們進行-1操作
}

四、佇列

①佇列的概念

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

佇列的使用，在我們的日常生活中是是十分常見的，比如我們在銀行排隊取號辦理手續時，就是我們佇列的具體化使用，先來的人領取一號小票，下一個人領取二號小票，一次往后，然后我們的視窗按照我們的小票順序開始叫號進行業務作業，依次往后；

后來者排隊領票辦理業務，也就相當于佇列插入一個元素，先來者視窗優先叫號處理，每當我們解決以為用戶的業務我們的隊伍就前進一個單位，也就相當于我們的佇列出一個元素，

②佇列的實作

在這里我們依然面對著我們堆疊中的問題，就是我們用什么結構來實作我們的佇列結構，在這里我們對兩種結構都進行分析

1.當我們使用順序表時，這里和我們的堆疊不一樣，堆疊中我們進行入堆疊和出堆疊操作時，我們操作的的位置都是我們的堆疊頂位置，也就是一個位置，而我們的佇列中要實作我們的佇列的入元素和出元素時，我們操作的位置是不同的，當我們進行出元素時，我們需要找到我們的首元素 ，而當我們要進行入元素時我們需要找到我們的尾元素，此時如果我們使用我們的順序表實作的話，不僅位置的查找較為麻煩，同時我們可能需要進行元素的移動覆寫，這樣我們的效率較為低下，

2.當我們使用鏈表實作是，我們此時只需要創建兩個指標始終指向我們當前佇列的首元素和尾位置即可，這樣我們就可以快捷的實作我們的入元素和出元素的操作，所以我們選擇使用鏈表來實作我們的佇列

綜上，我們得出我們要想實作我們的佇列，我們采用鏈表來實作
如果對鏈表的實作不太熟悉的讀者，可以看一下這篇博客
https://blog.csdn.net/weixin_52664715/article/details/120336834?spm=1001.2014.3001.5501
如果比較熟悉我們鏈表的內容，那么我們在實作佇列中的介面時，就會十分得心應手，

五、常見介面

5.1佇列的定義

在這里我們實作佇列的定義時，我們先回顧我們上面的分析，我們得知我們可以采用我們的鏈表來實作我們的佇列

此時我們需要創建兩個指標來指向我們佇列的收尾，但我們如果在函式介面中創建兩個指標形參，使得我們的函式介面太復雜，所以這一次我們采用將兩個指標創建一個結構體來看待，這樣我們通過對結構體指標的解應用就可以獲得我們的兩個指標，使得我們的函式介面更加簡潔

//舉例代碼：
typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType data;
}QueueNode;

//我們對佇列進行分析可知，我們在實作佇列的插入元素時，需要找到當前佇列的最后尾tail
//如果我們只用一個phead指標，顯然不夠用，所以我們要在創建一個指標tail
//這個時候我們將兩個指標包在一起

typedef struct Queue
{
	QueueNode* phead;
	QueueNode* ptail;
}Queue;

5.2佇列的初始化

這里我們對佇列的初始化和我們鏈表中的初始化執行步驟相同

//舉例代碼：
void QueueInit(Queue* pq)
{
	assert(pq);//判斷我們佇列的收尾指標是否為空
	pq->phead = pq->ptail = NULL;
}

5.3佇列的銷毀

這個時候因為我們的佇列中都是一個一個通過動態記憶體函式創建的節點，所以需要我們手動釋放空間

//舉例代碼：
void QueueDestory(Queue* pq)
{
	assert(pq);

	QueueNode* cur = pq->phead;
	while (cur)
	{
		QueueNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->phead = pq->ptail = NULL;

}

5.4佇列入資料

在我們的佇列中，我們要想入資料，根據佇列的性質我們只能在隊尾進行入資料，也就是我們ptail指標指向的節點；

同時當我進行入資料時，我們還需要創建我們新資料的節點；

//舉例代碼：
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//這里我們創建一個節點，也就是我們要插入的節點
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	//完成我們節點的創建，已經判讀是否創建成功，已經賦值

	if (pq->ptail == NULL)//這里我們判斷tail和phead都一樣
	{
		pq->ptail = pq->phead = newnode;
	}
	else
	{
		pq->ptail->next = newnode;//這里我們先獲得的是我們的tail指標，然后我們將tail指標指向的節點的指標域存盤我們新節點的地址
		pq->ptail = newnode;//同時我們將tail指標后移到新插入的節點
	}
}

5.5佇列出資料

當我們要在佇列中出資料時，也就是我們最先入佇列的元素，此時我們只能在佇列的首元素的位置，也就是我們phead指向的位置進行操作，出資料之后，我們在鏈表中我們就需要將這個節點進行洗掉，也就是我們要進行空間的釋放

//舉例代碼：
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QueueNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;
	}

}

5.6佇列的長度

在這里我們要想獲得我們佇列的長度，只需要用指標遍歷我們的鏈表即可獲取

//舉例代碼：
int QueueSize(Queue* pq)
{
	assert(pq);

	int n = 0;
	QueueNode* cur = pq->phead;
	while (cur)
	{
		n++;
		cur = cur->next;
	}
	return n;
}

5.7佇列的判空

當我們的ptail指標指向NULL時，說明此時我們的佇列中沒有元素的存在

//舉例代碼：
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->ptail == NULL;
}

5.8佇列的隊尾元素獲取

我們要獲取我們佇列的尾元素，只需要將我們ptail指標指向的元素回傳即可

//舉例代碼：
QDataType QueueBack(Queue* pq)//獲取隊尾的資料
{
	assert(pq);
	assert(!QueueEmpty(pq));//保證我們的收尾指標不指向NULL

	return pq->ptail->data;
}

5.9佇列的隊首元素獲取

我們要獲取我們佇列的尾元素，只需要將我們phead指標指向的元素回傳即可

//舉例代碼：
QDataType QueueFront(Queue* pq)//獲取隊頭的元素
{
	assert(pq);
	assert(!QueueEmpty(pq));//保證我們的收尾指標不指向NULL

	return pq->phead->data;

}

總結

關于堆疊和佇列內容的講述，我暫且講述這些，后面還有關于環形佇列以及相關的OJ練習，我們會在后面持續更新講述；在這一章節中本質上是對我們順序表和鏈表的復習與再應用，所以仍需我們對順序表和鏈表的基本操作熟練掌握，

以上就是我對堆疊和佇列的個人理解

上述內容如果有錯誤的地方，還麻煩各位大佬指教【膜拜各位了】【膜拜各位了】