前言：棧和隊列是計算機科學中兩種最基礎的線性數據結構，它們的獨特操作規則和廣泛的應用場景使其成為每一位開發者必須掌握的核心知識。本文將通過生活案例、代碼實現和實際應用場景，帶您深入理解這兩種數據結構的精髓。

1.棧（Stack）

基本定義

棧是一種受限的線性表，僅允許在同一端（棧頂）進行數據插入（push）和刪除（pop）操作。其核心特性遵循LIFO(后進先出)（Last In First Out）原則，即后進入的元素優先被訪問。

LIFO原則

• 后進先出（Last In First Out）：最后入棧的元素總是最先出棧

• 入棧（Push）：將新元素放入棧頂

• 出棧（Pop）：移除并返回棧頂元素

核心機制

• 單端操作：所有操作集中在棧頂完成

• 動態指針：通過棧頂指針（top）實時跟蹤最新元素位置

• 操作限制：禁止直接訪問中間元素，必須按序操作

• 空間管理：順序棧需預判容量，鏈式棧動態擴展但需額外指針空間

2.棧的實現

實現方式	優點	缺點	適用場景
動態數組	緩存友好，訪問速度快	擴容時需要拷貝數據	通用場景
鏈表	無需預分配空間	每個元素需要額外指針空間	元素數量變化劇烈
靜態數組	內存分配確定	容量固定，不夠靈活	嵌入式系統/內存受限環境

本文將以動態數組為基礎，手把手帶你用C語言實現一個智能的“自動擴容棧”。

/* 棧元素類型定義（方便修改數據類型） */
typedef int STDataType;/* 棧結構體定義arr: 動態數組首地址top: 棧頂指針（當前元素數量）capacity: 數組總容量 */
typedef struct Stack {STDataType* arr;int top;        int capacity;   
} ST;/* 功能：初始化棧結構參數：ps - 指向棧的指針關鍵點：初始狀態數組為空，容量為0 */
void STInit(ST* ps) {assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;
}/* 功能：壓入元素到棧頂參數：ps - 棧指針，x - 要入棧的元素關鍵點：自動擴容策略（4→8→16...）示例：初始容量0時首次push會擴容到4 */
void STPush(ST* ps, STDataType x) {assert(ps);// 容量檢查與擴容if (ps->capacity == ps->top) {int newcapacity = ps->capacity ? 2*ps->capacity : 4;STDataType* temp = realloc(ps->arr, newcapacity*sizeof(STDataType));if (!temp) { perror("malloc"); exit(1); }ps->arr = temp;ps->capacity = newcapacity;}ps->arr[ps->top++] = x; // 先存數據再移動指針
}/* 功能：判斷棧是否為空參數：ps - 棧指針返回：true表示空棧，false非空示例：初始化后返回true，push后返回false */
bool STEmpty(ST* ps) {assert(ps);return ps->top == 0;
}/* 功能：彈出棧頂元素參數：ps - 棧指針關鍵點：實際只移動指針，不刪除數據注意：空棧彈出會導致斷言失敗 */
void STPop(ST* ps) {assert(ps && !STEmpty(ps));ps->top--; // 邏輯刪除
}/* 功能：獲取棧元素數量參數：ps - 棧指針返回：當前元素個數示例：push三次后返回3 */
int STSize(ST* ps) {assert(ps);return ps->top; // top直接表示數量
}/* 功能：查看棧頂元素（不彈出）參數：ps - 棧指針返回：棧頂元素值關鍵點：top-1才是最后存入的位置示例：棧內[10,20]時返回20 */
STDataType STTop(ST* ps) {assert(ps && !STEmpty(ps));return ps->arr[ps->top-1];
}/* 功能：銷毀棧并釋放內存參數：ps - 棧指針關鍵點：必須調用防止內存泄漏注意：調用后棧不可再使用 */
void STDestroy(ST* ps) {assert(ps);if (ps->arr) free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}

測試用例?

int main()
{ST st;          // 聲明棧變量（未初始化狀態）STInit(&st);    // 初始化棧 → arr=NULL, capacity=0, top=0STPush(&st, 1);  // 觸發擴容（0→4）→ arr[0]=1, top=1printf("%d\n", STSize(&st)); // 輸出1（當前元素數量）STPush(&st, 2);  // arr[1]=2, top=2printf("%d\n", STSize(&st)); // 輸出2STPush(&st, 3);  // arr[2]=3, top=3printf("%d\n", STSize(&st)); // 輸出3STPush(&st, 4);  // arr[3]=4, top=4（棧滿）printf("%d\n", STSize(&st)); // 輸出4while (!STEmpty(&st)) //打印棧中所有元素{          printf("%d ", STTop(&st));  // 從棧頂開始輸出：4 3 2 1STPop(&st);           // 每次循環top減1}printf("\n%d", STSize(&st)); // 輸出0（此時棧空）STDestroy(&st);          // 必須調用！釋放動態內存return 0;
}

3.隊列（Queue）

基本定義

隊列是另一種受限線性表，遵循FIFO（First In First Out）原則。元素從隊尾（rear）插入（enqueue），從隊首（front）移除，保持嚴格的先進先出順序。

核心機制

• 雙指針系統：通過?front?和 rear 指針分別管理兩端

• 循環優化：使用模運算實現環形緩沖區解決"假溢出"問題

• 等待特性：元素按到達順序被處理，具有公平性特征

• 容量管理：動態隊列可擴展，但需考慮內存碎片問題

4.隊列的實現

實現方式	優點	缺點	適用場景
普通數組隊列	實現簡單	出隊效率低（需要搬移元素）	教學演示
循環數組隊列	高效利用內存	需處理隊空/隊滿邊界條件	固定容量生產消費場景
鏈表隊列	動態擴容靈活	內存碎片化，緩存不友好	頻繁擴容/元素大小不一
動態數組隊列	平衡性能與靈活性	擴容時產生瞬時延遲	通用場景

在本文中，會著重介紹下面三種隊列，普通數組隊列的使用并不常見，我們在這里并不過多介紹，大家可以自己嘗試著實現。首先，我們實現鏈式隊列。循環數組隊列和動態數組隊列我們作為后面習題補充會涉及到。

注意：鏈式隊列的實現與單鏈表的實現大差不差，前面單鏈表的實現非常重要，能夠完成單鏈表的實現代碼，實現鏈式隊列代碼就不成問題。

typedef int QDataType;  // 隊列元素類型別名，方便修改存儲類型// 隊列節點結構（鏈式存儲）
typedef struct QueueNode {int val;              // 存儲數據struct QueueNode* next; // 指向下一個節點
} QNode;// 隊列管理結構
typedef struct Queue {QNode* phead;  // 隊頭指針（刪除端）QNode* ptail;  // 隊尾指針（插入端）int size;       // 當前元素數量
} Queue;// 功能：初始化隊列結構
// 參數：pq - 指向隊列的指針
// 關鍵點：將指針置空，size清零
void QueueInit(Queue* pq) {assert(pq);  // 防御性編程，確保指針有效pq->phead = pq->ptail = NULL;pq->size = 0;  // 初始為空隊列
}// 功能：創建新節點
// 參數：x - 要存儲的數據
// 返回：新節點指針
// 關鍵點：內存分配與初始化
QNode* Createnode(QDataType x) {QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL) {          // 內存不足處理perror("malloc");           // 打印錯誤信息exit(1);                    // 直接終止程序}newnode->val = x;               // 存儲數據newnode->next = NULL;           // 初始化指針return newnode;
}// 功能：在隊尾插入新元素
// 參數：pq - 隊列指針，x - 要插入的數據
// 關鍵點：維護頭尾指針關系
void QueuePush(Queue* pq, QDataType x) {assert(pq);QNode* newnode = Createnode(x);  // 創建新節點if (pq->phead == NULL) {        // 空隊列情況pq->phead = pq->ptail = newnode;} else {                        // 非空隊列pq->ptail->next = newnode;  // 鏈接新節點pq->ptail = newnode;        // 更新尾指針}pq->size++;  // 元素計數增加
}// 功能：判斷隊列是否為空
// 參數：pq - 隊列指針
// 返回：true為空，false非空
// 關鍵點：只需檢查頭指針
bool QueueEmpty(Queue* pq) {assert(pq);return pq->phead == NULL;  // 頭指針為空即隊列空
}// 功能：刪除隊頭元素
// 參數：pq - 隊列指針
// 關鍵點：處理最后一個節點的特殊情況
void QueuePop(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));  // 確保隊列非空QNode* del = pq->phead;     // 保存待刪除節點pq->phead = pq->phead->next;// 頭指針后移// 處理刪除最后一個元素的情況if (pq->phead == NULL) {pq->ptail = NULL;      // 尾指針也必須置空}free(del);      // 釋放節點內存pq->size--;     // 元素計數減少
}// 功能：查看隊頭元素（不刪除）
// 參數：pq - 隊列指針
// 返回：隊頭元素值
// 注意：隊列為空時觸發斷言
QDataType QueueFront(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));  // 防御空隊列訪問return pq->phead->val;    // 直接返回頭節點值
}// 功能：查看隊尾元素（不刪除）
// 參數：pq - 隊列指針
// 返回：隊尾元素值
QDataType QueueBack(Queue* pq) {assert(pq);assert(!QueueEmpty(pq));  // 防御空隊列訪問return pq->ptail->val;    // 直接返回尾節點值
}// 功能：獲取當前元素數量
// 參數：pq - 隊列指針
// 返回：隊列元素個數
// 優勢：O(1)時間復雜度
int QueueSize(Queue* pq) {assert(pq);return pq->size;  // 直接返回計數器值
}// 功能：釋放隊列所有內存
// 參數：pq - 隊列指針
// 關鍵點：必須遍歷釋放所有節點
void QueueDestroy(Queue* pq) {assert(pq);QNode* curr = pq->phead;while (curr) {QNode* del = curr;   // 保存當前節點curr = curr->next;   // 移動到下一個節點free(del);           // 釋放當前節點}pq->phead = pq->ptail = NULL;  // 重置指針pq->size = 0;                  // 重置計數器
}

測試用例

int main() {Queue q;QueueInit(&q);  // 必須初始化QueuePush(&q, 10);QueuePush(&q, 20);printf("隊頭：%d\n", QueueFront(&q));  // 輸出10QueuePop(&q);  // 刪除10printf("當前大小：%d\n", QueueSize(&q));  // 輸出1QueueDestroy(&q);  // 必須銷毀return 0;
}

?5.棧與隊列算法題

5.1?力扣：有效的括號

?1. 核心思想

• 棧的LIFO特性：利用棧后進先出的特性，確保最近打開的括號必須最先閉合

• 匹配原則：遍歷字符串時，遇到左括號入棧，遇到右括號必須與棧頂左括號類型匹配

2. 執行流程

1. 初始化棧：創建空棧用于存儲待匹配的左括號

2. 遍歷字符：逐個處理輸入字符串的每個字符

   • 左括號處理：(/[/{?→ 壓入棧頂

   • 右括號處理：

     • 檢查棧空 → 棧空直接返回false

     • 棧非空 → 檢查棧頂是否匹配 → 匹配則彈出，不匹配返回false

3. 最終校驗：遍歷完成后檢查棧是否為空（所有左括號均已匹配）

//代碼中所用函數都是上文棧的實現中的函數
bool isValid(char* s) {ST st;STInit(&st);while(*s != '\0'){if(*s == '(' || *s == '[' || *s == '{'){STPush(&st,*s);}else{if(STEmpty(&st))return false;STDataType ch1 = STTop(&st);if((ch1 == '(' && *s == ')')|| (ch1 == '[' && *s == ']')|| (ch1 == '{' && *s == '}'))STPop(&st);else{STDestroy(&st);return false;}}s++;}if(!STEmpty(&st))return false;STDestroy(&st);return true;
}

5.2力扣：用隊列實現棧?

// 代碼中所用函數都是上文隊列的實現中的函數// 使用兩個隊列實現棧的結構定義
typedef struct {Queue q1;Queue q2;
} MyStack;// 創建棧實例并初始化兩個隊列
MyStack* myStackCreate() 
{MyStack* pst = (MyStack*)malloc(sizeof(MyStack));QueueInit(&pst->q1);QueueInit(&pst->q2);return pst;
}// 入棧操作：將元素壓入非空隊列（若都為空則選擇q1）
void myStackPush(MyStack* obj, int x) {if(!QueueEmpty(&obj->q1))QueuePush(&obj->q1, x);elseQueuePush(&obj->q2, x);
}// 出棧操作：將非空隊列的前n-1個元素轉移到空隊列，彈出最后一個元素
int myStackPop(MyStack* obj) {Queue* emptyQue = &obj->q1;Queue* nonEmptyQue = &obj->q2;// 確定空隊列和非空隊列if(QueueEmpty(nonEmptyQue)) {emptyQue = &obj->q2;nonEmptyQue = &obj->q1;}// 將非空隊列的前n-1個元素轉移到空隊列while(QueueSize(nonEmptyQue) > 1) {QDataType data = QueueFront(nonEmptyQue);QueuePop(nonEmptyQue);QueuePush(emptyQue, data);}// 彈出并返回最后一個元素QDataType ret = QueueFront(nonEmptyQue);QueuePop(nonEmptyQue);return ret;
}// 獲取棧頂元素：直接返回非空隊列的隊尾元素
int myStackTop(MyStack* obj) {if(!QueueEmpty(&obj->q1))return QueueBack(&obj->q1);elsereturn QueueBack(&obj->q2);
}// 判斷棧是否為空：當兩個隊列都為空時棧為空
bool myStackEmpty(MyStack* obj) {return QueueEmpty(&obj->q1) && QueueEmpty(&obj->q2);
}// 釋放棧內存：銷毀兩個隊列并釋放棧結構
void myStackFree(MyStack* obj) {QueueDestroy(&obj->q1);QueueDestroy(&obj->q2);free(obj);obj = NULL;
}

?5.3力扣：用棧實現隊列

?

// 代碼中所用函數都是上文棧的實現中的函數// 使用兩個棧實現隊列的結構定義
typedef struct {ST Pushst;    // 用于入隊操作的棧ST Popst;     // 用于出隊操作的棧
} MyQueue;// 創建隊列實例并初始化兩個棧
MyQueue* myQueueCreate() {MyQueue* pst = (MyQueue*)malloc(sizeof(MyQueue));STInit(&pst->Pushst);STInit(&pst->Popst);return pst;
}// 入隊操作：直接壓入Push棧
void myQueuePush(MyQueue* obj, int x) {STPush(&obj->Pushst, x);
}// 出隊操作：若Pop棧為空，則將Push棧元素全部倒入Pop棧，再彈出Pop棧頂元素
int myQueuePop(MyQueue* obj) {if(STEmpty(&obj->Popst)) {// 將Push棧的元素逆序倒入Pop棧while(!STEmpty(&obj->Pushst)) {STDataType data = STTop(&obj->Pushst);STPop(&obj->Pushst);STPush(&obj->Popst, data);}}STDataType ret = STTop(&obj->Popst);STPop(&obj->Popst);return ret;
}// 獲取隊首元素：邏輯同出隊，但不彈出元素
int myQueuePeek(MyQueue* obj) {if(STEmpty(&obj->Popst)) {while(!STEmpty(&obj->Pushst)) {STDataType data = STTop(&obj->Pushst);STPop(&obj->Pushst);STPush(&obj->Popst, data);}}return STTop(&obj->Popst);
}// 判斷隊列是否為空：當兩個棧都為空時隊列為空
bool myQueueEmpty(MyQueue* obj) {return STEmpty(&obj->Popst) && STEmpty(&obj->Pushst);
}// 釋放隊列內存：銷毀兩個棧并釋放隊列結構
void myQueueFree(MyQueue* obj) {STDestroy(&obj->Popst);STDestroy(&obj->Pushst);free(obj);obj = NULL;
}

?5.4力扣：設計循環隊列

// 使用數組實現的環形隊列結構
typedef struct {int* arr;        // 存儲隊列元素的數組int front;       // 隊頭指針：指向隊列第一個有效元素int rear;        // 隊尾指針：指向隊列最后一個元素的下一個位置int capacity;    // 隊列的最大容量（實際存儲元素個數為capacity）
} MyCircularQueue;// 創建環形隊列實例，k為隊列容量
MyCircularQueue* myCircularQueueCreate(int k) {MyCircularQueue* obj = (MyCircularQueue*)malloc(sizeof(MyCircularQueue));// 分配k+1大小的數組，浪費一個空間用于區分隊列滿和空的狀態obj->arr = (int*)malloc(sizeof(int) * (k + 1));obj->front = obj->rear = 0;    // 初始化隊頭隊尾指針obj->capacity = k;             // 設置隊列容量return obj;
}// 判斷隊列是否為空
bool myCircularQueueIsEmpty(MyCircularQueue* obj) {// 當隊頭和隊尾指針指向同一位置時，隊列為空return obj->rear == obj->front;
}// 判斷隊列是否已滿
bool myCircularQueueIsFull(MyCircularQueue* obj) {// 當隊尾指針的下一個位置是隊頭指針時，隊列已滿// 使用取模運算實現環形效果return (obj->rear + 1) % (obj->capacity + 1) == obj->front;
}// 入隊操作
bool myCircularQueueEnQueue(MyCircularQueue* obj, int value) {if (myCircularQueueIsFull(obj))return false;    // 隊列已滿，入隊失敗obj->arr[obj->rear] = value;    // 將元素放入隊尾位置obj->rear = (obj->rear + 1) % (obj->capacity + 1);    // 更新隊尾指針，循環前進return true;
}// 出隊操作
bool myCircularQueueDeQueue(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return false;    // 隊列為空，出隊失敗obj->front = (obj->front + 1) % (obj->capacity + 1);    // 更新隊頭指針，循環前進return true;
}// 獲取隊頭元素
int myCircularQueueFront(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;    // 隊列為空，返回-1表示無效值return obj->arr[obj->front];    // 返回隊頭指針指向的元素
}// 獲取隊尾元素
int myCircularQueueRear(MyCircularQueue* obj) {if (myCircularQueueIsEmpty(obj))return -1;    // 隊列為空，返回-1表示無效值// 計算隊尾元素的實際位置（隊尾指針前一個位置）int prev = (obj->rear - 1 + (obj->capacity + 1)) % (obj->capacity + 1);return obj->arr[prev];
}// 釋放隊列內存
void myCircularQueueFree(MyCircularQueue* obj) {free(obj->arr);    // 釋放存儲元素的數組free(obj);         // 釋放隊列結構體obj = NULL;        // 防止野指針
}

1. 數組大小：

   • 實際分配大小為?capacity + 1，浪費一個空間用于區分隊列滿和隊列空的狀態
   • 隊列滿條件：(rear + 1) % (capacity + 1) == front
   • 隊列空條件：rear == front

2. 指針移動：

   • 隊頭指針front：指向隊列的第一個有效元素
   • 隊尾指針rear：指向隊列最后一個元素的下一個位置
   • 使用% (capacity + 1)實現環形效果

3. 邊界處理：

   • 入隊時直接在rear位置賦值，然后rear指針后移
   • 出隊時直接將front指針后移，無需真正刪除元素
   • 獲取隊尾元素時需要計算rear的前一個位置，處理rear為 0 的情況

5.5設計動態循環列表

#include <stdlib.h>
#include <assert.h>typedef struct {int* data;       // 存儲隊列元素的動態數組int front;       // 隊頭指針，指向隊列第一個元素int rear;        // 隊尾指針，指向隊列最后一個元素的下一個位置int capacity;    // 當前隊列容量int size;        // 當前隊列元素個數
} DynamicQueue;// 創建動態隊列，初始容量為initialCapacity
DynamicQueue* createQueue(int initialCapacity) {DynamicQueue* queue = (DynamicQueue*)malloc(sizeof(DynamicQueue));assert(queue != NULL);queue->data = (int*)malloc(sizeof(int) * initialCapacity);assert(queue->data != NULL);queue->front = 0;queue->rear = 0;queue->size = 0;queue->capacity = initialCapacity;return queue;
}// 判斷隊列是否為空
bool isEmpty(DynamicQueue* queue) {return queue->size == 0;
}// 判斷隊列是否已滿（實際不會滿，會自動擴容）
bool isFull(DynamicQueue* queue) {return queue->size == queue->capacity;
}// 擴容隊列，新容量為原容量的2倍
void resizeQueue(DynamicQueue* queue) {int newCapacity = queue->capacity * 2;int* newData = (int*)malloc(sizeof(int) * newCapacity);assert(newData != NULL);// 復制原隊列元素到新數組for (int i = 0; i < queue->size; i++) {newData[i] = queue->data[(queue->front + i) % queue->capacity];}free(queue->data);queue->data = newData;queue->front = 0;queue->rear = queue->size;queue->capacity = newCapacity;
}// 入隊操作
void enqueue(DynamicQueue* queue, int value) {if (isFull(queue)) {resizeQueue(queue);}queue->data[queue->rear] = value;queue->rear = (queue->rear + 1) % queue->capacity;queue->size++;
}// 出隊操作，返回隊頭元素
int dequeue(DynamicQueue* queue) {assert(!isEmpty(queue));int value = queue->data[queue->front];queue->front = (queue->front + 1) % queue->capacity;queue->size--;return value;
}// 獲取隊頭元素
int getFront(DynamicQueue* queue) {assert(!isEmpty(queue));return queue->data[queue->front];
}// 獲取隊列大小
int getSize(DynamicQueue* queue) {return queue->size;
}// 釋放隊列內存
void freeQueue(DynamicQueue* queue) {free(queue->data);free(queue);
}

?