目錄
文章目錄
前言
一、棧
1.1 棧的概念及結構
1.2 棧的實現
1.2.1. 支持動態增長的棧的結構
1.2.2 初始化棧
1.2.3 入棧
1.2.4 出棧
1.2.5 獲取棧頂元素
1.2.6?獲取棧中有效元素個數
1.2.7 檢查棧是否為空
1.2.8 銷毀棧
二、隊列
2.1 隊列的概念及結構
2.2 隊列的實現
2.2.1 隊列的結構
2.2.2 初始化隊列
2.2.3 入隊
2.2.4 出隊
2.2.5 獲取隊頭元素
2.2.6 獲取隊尾元素
2.2.7 獲取隊列中有效元素個數
2.2.8 檢查隊列是否為空
2.2.9 銷毀隊列
總結
一、棧
1.1 棧的概念及結構
棧（Stack）是一種線性數據結構，它可以看作是一種特殊的列表。棧只能在一端進行插入和刪除操作，這一端被稱為棧頂（Top）。棧按照后進先出（LIFO, Last In First Out）的原則進行操作，即最后一個進棧的元素最先被彈出。棧可以用數組或鏈表實現。棧的主要操作包括壓棧（進棧/入棧）（Push）和彈棧（出棧）（Pop），還有取棧頂元素（Top）和判斷棧是否為空（Empty）等。棧在編程中常用于函數調用、表達式求值、括號匹配等場景。
1.2 棧的實現
棧的實現一般可以使用數組或者鏈表實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小。所以我們這里使用數組實現棧。用數組實現也分為靜態的和動態的，靜態的實際中一般不實用，所以我們實現動態的。
1.2.1. 支持動態增長的棧的結構
這里我們聲明一個結構體，一個成員為指針a，用來存放開辟空間的首地址（即動態數組），一個成員top用來存放棧頂位置，還有一個成員capacity用來存放開辟的空間大小，方便數組擴容。
代碼如下：
typedef int StDataType;typedef struct Stack
{StDataType* a;int top; // 標識棧頂位置的int capacity;
}St;1.2.2 初始化棧
將結構體中的指針a賦值為NULL，將capacity賦值為0，將top賦值為0，表示top指向棧頂元素的下一個位置（也可以賦值為-1，表示top指向棧頂元素，這里我們使用第一種）。
代碼如下：
void StInit(St* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;//表示top指向棧頂元素的下一個位置pst->top = 0;//表示top指向棧頂元素，如果為-1，后面的代碼也要改//pst->top = -1;
}1.2.3 入棧
入棧之前要先判斷開辟的空間滿了沒，如果滿了，可以使用realloc（）函數重新分配數組大小，然后再將元素插入top所指向的位置，最后將top+1。
代碼如下：
void StPush(St* pst, StDataType x)
{assert(pst);if (pst->top == pst->capacity){int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;StDataType* tmp = (StDataType*)realloc(pst->a, newCapacity * sizeof(StDataType));if (tmp == NULL){perror("realloc fail");exit(-1);}pst->a = tmp;pst->capacity = newCapacity;}pst->a[pst->top] = x;pst->top++;
}1.2.4 出棧
先要確保棧中有元素，可以使用斷言，如果有，則只需要top-1就行。
代碼如下：
void StPop(St* pst)
{assert(pst);assert(pst->top > 0);pst->top--;
}1.2.5 獲取棧頂元素
先確保棧中有元素，然后直接返回top-1所指向位置的元素即可。
代碼如下：
StDataType StTop(St* pst)
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}1.2.6?獲取棧中有效元素個數
因為top指向棧頂元素的下一個位置，其大小剛好為元素的個數，所以直接返回top即可。
代碼如下：
int StSize(St* pst)
{assert(pst);return pst->top;
}1.2.7 檢查棧是否為空
判斷top是否為0，為0即為空。
代碼如下：
bool StEmpty(St* pst)
{assert(pst);return pst->top == 0;
}1.2.8 銷毀棧
先將動態分配的內存釋放了，再將結構體中的成員賦值為初始化棧時所賦值的值就行。
代碼如下：
void StDestroy(St* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = 0;pst->capacity = 0;
}二、隊列
2.1 隊列的概念及結構
隊列（Queue）是一種遵循先進先出（First In First Out，FIFO）原則的數據結構，即最先插入隊列的元素最先被取出。隊列具有兩個端點，一個是隊頭（Head），一個是隊尾（Tail），入隊操作（enqueue）在隊尾進行，出隊操作（dequeue）在隊頭進行。隊列的應用領域很廣，例如實現任務調度、消息傳遞、緩沖區等。常見隊列的實現包括：單向隊列、雙向隊列和循環隊列等。我們這里主要討論單向隊列。
2.2 隊列的實現
我們這里實現的是最基礎的單向隊列，雙向隊列和循環隊列各位讀者可另行了解。隊列也可以數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低（因為要整體把元素往前移，時間復雜度為O(n)，雖然在算法中用數組模擬實現隊列可以使用頭尾雙指針使時間復雜度變成O(1),但這樣做出隊的同時也把空間浪費了）。
2.2.1 隊列的結構
因為使用鏈表實現隊列，所以先聲明一個隊列的結點的結構體，其成員跟鏈表的聲明一致，有兩個成員，一個為數據val，另一個為next指針。然后為了后面實現的方便，再聲明一個隊列結構體，其成員包括隊頭指針phead和隊尾指針ptail以及一個記錄隊列大小的整形size。
代碼如下：
typedef int QDataType;typedef struct QueueNode
{QDataType val;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;2.2.2 初始化隊列
將隊頭指針phead和隊尾指針ptail賦值為NULL，將size賦值為0。
代碼如下：
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}2.2.3 入隊
先動態申請一個新結點，將要入隊的元素賦給新結點的val，再將新結點的next指針指向NULL。然后判斷這個隊列是否為空，如果為空，則將隊頭指針phead和隊尾指針ptail都指向新結點；如果不為空，則只要改變隊尾指針ptail就行，即先將隊尾指針ptail指向的結點的next指針指向新結點，再將隊尾指針ptail指向新結點。最后將size+1就行了。
代碼如下：
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL){perror("malloc fail");exit(-1);}newNode->val = x;newNode->next = NULL;if (pq->phead == NULL){pq->phead = pq->ptail = newNode;}else{pq->ptail->next = newNode;pq->ptail = newNode;}pq->size++;
}2.2.4 出隊
先要確保隊列中有結點，可以使用斷言。然后再判斷隊列中是否只有一個結點，如果是，則釋放這個結點后，要將隊頭指針phead和隊尾指針ptail都指向NULL；如果不是，則只需要將隊頭指針phead指向它所指向的結點的下一個結點，并將它原來所指向的結點釋放就行。最后將size-1。
代碼如下：
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else{QNode* tmp = pq->phead;pq->phead = pq->phead->next;free(tmp);}pq->size--;
}2.2.5 獲取隊頭元素
先確保隊列有結點，再返回隊頭指針phead所指向的結點的值val。
代碼如下：
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}2.2.6 獲取隊尾元素
先確保隊列有結點，再返回隊尾指針ptail所指向的結點的值val。
代碼如下：
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}2.2.7 獲取隊列中有效元素個數
直接返回size。
代碼如下：
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}2.2.8 檢查隊列是否為空
判斷隊頭指針phead是否為NULL。
代碼如下：
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}2.2.9 銷毀隊列
先遍歷釋放隊列中的每一個結點，再將隊列結構體中的成員賦值為初始化隊列時所賦值的值就行。
代碼如下：
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}總結
以上就是關于棧和隊列的基本概念和操作。通過這篇文章，希望大家能夠更好地理解關于棧和隊列的原理和實現，并在實際編程中靈活運用它們。
)
)
)
