數據結構詳解：順序棧與鏈棧的原理、實現及應用
1. 引言：棧的核心概念
棧（Stack）是一種重要的線性數據結構，它遵循后進先出（Last In First Out, LIFO）的原則。這意味著最后一個被添加到棧中的元素將是第一個被移除的元素。棧的這種特性使其在多種計算場景中非常有用，例如函數調用、表達式求值和括號匹配等。
棧的基本操作包括：
- Push（入棧）：在棧頂添加一個元素
- Pop（出棧）：移除棧頂元素并返回其值
- Peek/Top（查看棧頂）：返回棧頂元素但不移除它
- isEmpty（判空）：檢查棧是否為空
在這篇技術文章中，我們將詳細探討棧的兩種主要實現方式：順序棧（基于數組）和鏈棧（基于鏈表），分析它們的優缺點，并提供實際代碼示例和應用場景。
2. 順序棧：數組實現
2.1 順序棧的結構與特點
順序棧使用數組作為底層存儲結構，這意味著它需要一塊連續的內存空間。順序棧通常包含兩個主要部分：一個用于存儲元素的數組和一個用于跟蹤棧頂位置的整型變量（通常稱為"top"或"棧頂指針"）。
順序棧的主要特點：
- 內存連續，訪問速度快
- 需要預先指定棧的最大容量
- 當棧滿時無法再添加新元素（除非動態擴容）
- 操作時間復雜度為O(1)
2.2 順序棧的實現代碼（C語言）
#include <stdio.h>
#include <stdlib.h>#define MAX_SIZE 100 // 定義棧的最大容量typedef struct {int data[MAX_SIZE]; // 存儲棧元素的數組int top; // 棧頂指針
} SeqStack;// 初始化棧
void InitStack(SeqStack *S) {S->top = -1; // 初始化為-1表示空棧
}// 判斷棧是否為空
int IsEmpty(SeqStack *S) {return (S->top == -1);
}// 判斷棧是否已滿
int IsFull(SeqStack *S) {return (S->top == MAX_SIZE - 1);
}// 入棧操作
int Push(SeqStack *S, int value) {if (IsFull(S)) {printf("Stack is full! Push operation failed.\n");return 0;}S->data[++(S->top)] = value; // 棧頂指針先加1，再將元素放入棧頂位置return 1;
}// 出棧操作
int Pop(SeqStack *S, int *value) {if (IsEmpty(S)) {printf("Stack is empty! Pop operation failed.\n");return 0;}*value = S->data[(S->top)--]; // 先取出棧頂元素，再將棧頂指針減1return 1;
}// 獲取棧頂元素（但不刪除）
int GetTop(SeqStack *S, int *value) {if (IsEmpty(S)) {printf("Stack is empty!\n");return 0;}*value = S->data[S->top];return 1;
}// 打印棧中的所有元素
void PrintStack(SeqStack *S) {if (IsEmpty(S)) {printf("Stack is empty!\n");return;}printf("Stack elements (from bottom to top): ");for (int i = 0; i <= S->top; i++) {printf("%d ", S->data[i]);}printf("\n");
}
2.3 順序棧的優缺點分析
優點：
- 訪問速度快：由于內存連續，CPU緩存友好，訪問效率高
- 實現簡單：代碼邏輯直接，易于理解和實現
- 內存開銷小：只需要一個數組和一個整型變量，無需額外指針開銷
缺點： - 固定容量：需要預先定義棧的大小，可能導致空間浪費或棧溢出
- 擴容困難：當棧滿時，擴容需要創建新數組并復制所有元素，時間復雜度為O(n)
- 不靈活：難以適應動態變化的數據規模
3. 鏈棧：鏈表實現
3.1 鏈棧的結構與特點
鏈棧使用鏈表作為底層存儲結構，每個元素包含數據部分和指向下一個節點的指針。鏈棧通常將鏈表的頭部作為棧頂，這樣入棧和出棧操作可以直接在鏈表頭部進行，時間復雜度為O(1)。
鏈棧的主要特點：
- 使用離散的內存空間，通過指針連接
- 無需預先指定容量，可以動態增長
- 只有當內存耗盡時才會出現"棧滿"情況
- 每個元素需要額外空間存儲指針
3.2 鏈棧的實現代碼（C語言）
#include <stdio.h>
#include <stdlib.h>// 定義棧節點結構
typedef struct StackNode {int data; // 數據域struct StackNode *next; // 指針域
} StackNode;// 定義鏈棧結構
typedef struct {StackNode *top; // 棧頂指針
} LinkStack;// 初始化棧
void InitLinkStack(LinkStack *S) {S->top = NULL;
}// 判斷棧是否為空
int IsEmpty(LinkStack *S) {return (S->top == NULL);
}// 入棧操作
void Push(LinkStack *S, int value) {// 創建新節點StackNode *newNode = (StackNode *)malloc(sizeof(StackNode));if (newNode == NULL) {printf("Memory allocation failed! Push operation failed.\n");return;}newNode->data = value;newNode->next = S->top; // 新節點指向原棧頂S->top = newNode; // 更新棧頂指針為新節點
}// 出棧操作
int Pop(LinkStack *S, int *value) {if (IsEmpty(S)) {printf("Stack is empty! Pop operation failed.\n");return 0;}StackNode *temp = S->top; // 臨時保存棧頂節點*value = temp->data;S->top = S->top->next; // 更新棧頂指針為下一個節點free(temp); // 釋放原棧頂節點的內存return 1;
}// 獲取棧頂元素（但不刪除）
int GetTop(LinkStack *S, int *value) {if (IsEmpty(S)) {printf("Stack is empty!\n");return 0;}*value = S->top->data;return 1;
}// 打印棧中的所有元素
void PrintStack(LinkStack *S) {if (IsEmpty(S)) {printf("Stack is empty!\n");return;}printf("Stack elements (from top to bottom): ");StackNode *current = S->top;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}// 銷毀棧，釋放所有節點內存
void DestroyStack(LinkStack *S) {StackNode *current = S->top;while (current != NULL) {StackNode *temp = current;current = current->next;free(temp);}S->top = NULL;
}
3.3 鏈棧的優缺點分析
優點：
- 動態大小：無需預先指定棧的大小，可以隨需求動態增長
- 內存高效：只分配實際需要的空間，沒有容量浪費
- 靈活性：適合數據規模動態變化較大的場景
缺點： - 額外內存開銷：每個節點需要額外空間存儲指針
- 訪問速度稍慢：由于內存不連續，CPU緩存不友好
- 內存管理復雜：需要手動管理內存分配和釋放，容易導致內存泄漏如果處理不當
4. 順序棧與鏈棧的對比
為了更清晰地理解兩種實現的差異，下表列出了順序棧和鏈棧的主要特性對比：
| 特性 | 順序棧 | 鏈棧 |
|---|---|---|
| 存儲方式 | 連續的內存空間（數組） | 離散的內存空間（鏈表） |
| 容量 | 固定，需預先定義 | 動態增長，受限于可用內存 |
| 空間效率 | 可能有浪費（數組固定大小） | 無浪費（按需分配） |
| 時間效率 | 所有操作 O(1) | 所有操作 O(1) |
| 內存管理 | 簡單，系統自動回收 | 需手動管理節點內存的申請和釋放 |
| 適用場景 | 數據規模已知或變化不大的場景 | 數據規模動態變化較大的場景 |
選擇建議：
- 如果數據規模已知且變化不大，或者對性能要求極高，優先選擇順序棧
- 如果數據規模變化較大或無法預估最大容量，優先選擇鏈棧
5. 棧的應用實例
| 例題名稱 | 核心知識點 | 難度 |
|---|---|---|
| 括號匹配 | 棧的基本操作、LIFO特性 | ? |
| 表達式求值 | 棧管理運算符優先級、后綴表達式 | ?? |
| 模擬瀏覽器前進后退 | 雙棧協作、狀態管理 | ?? |
| 遞歸的非遞歸實現 | 棧模擬函數調用棧 | ?? |
| 行編輯程序（含退格） | 棧處理輸入、刪除邏輯 | ?? |
📝 5.1 括號匹配問題
問題描述：檢查一個字符串中的括號是否正確匹配，有效的字符串需滿足：左括號必須用相同類型的右括號閉合，且左括號必須以正確的順序閉合。
解決思路：遍歷字符串，遇到左括號就入棧；遇到右括號時，檢查棧頂的左括號是否與之匹配。匹配則彈出棧頂，否則無效。最后棧應為空。
代碼實現（C語言，順序棧）：
#include <stdio.h>
#include <stdbool.h>#define MAX_SIZE 100typedef struct {char data[MAX_SIZE];int top;
} SeqStack;void initStack(SeqStack *s) { s->top = -1; }
bool isEmpty(SeqStack *s) { return s->top == -1; }
bool isFull(SeqStack *s) { return s->top == MAX_SIZE - 1; }bool push(SeqStack *s, char c) {if (isFull(s)) return false;s->data[++(s->top)] = c;return true;
}bool pop(SeqStack *s, char *c) {if (isEmpty(s)) return false;*c = s->data[(s->top)--];return true;
}bool peek(SeqStack *s, char *c) {if (isEmpty(s)) return false;*c = s->data[s->top];return true;
}bool isValid(char* s) {SeqStack stack;initStack(&stack);char topChar;for (int i = 0; s[i] != '\0'; i++) {if (s[i] == '(' || s[i] == '[' || s[i] == '{') {push(&stack, s[i]);} else if (s[i] == ')' || s[i] == ']' || s[i] == '}') {if (!peek(&stack, &topChar)) return false; // 棧空，有右括號無左括號匹配if ((s[i] == ')' && topChar == '(') ||(s[i] == ']' && topChar == '[') ||(s[i] == '}' && topChar == '{')) {pop(&stack, &topChar);} else {return false; // 括號類型不匹配}}}return isEmpty(&stack); // 檢查是否所有左括號都被匹配
}int main() {char expr[] = "({[]})";printf("%s is %s\n", expr, isValid(expr) ? "valid" : "invalid");return 0;
}
🧮 5.2 表達式求值
問題描述：計算算術表達式的值，例如 4 + 2 * 3 - 10 / (7 - 5)。
解決思路：使用兩個棧，一個存放操作數，一個存放運算符。根據運算符的優先級決定計算順序。
代碼概要（C語言）：
// 此處假設已定義順序棧結構 SeqStack 及其基本操作int getPriority(char op) {switch(op) {case '+': case '-': return 1;case '*': case '/': return 2;default: return 0;}
}int calculate(int a, int b, char op) {switch(op) {case '+': return a + b;case '-': return a - b;case '*': return a * b;case '/': return a / b; // 注意除零錯誤default: return 0;}
}int evalExpression(char* expr) {SeqStack opnd; // 操作數棧SeqStack optr; // 運算符棧initStack(&opnd);initStack(&optr);push(&optr, '#'); // 預設一個起始符int i = 0;char ch, topOp, arithmeticOp;int num, a, b;while (expr[i] != '\0' || !isEmpty(&optr)) {ch = expr[i];if (ch == ' ') { i++; continue; } // 跳過空格if (ch >= '0' && ch <= '9') { // 處理數字num = 0;while (expr[i] >= '0' && expr[i] <= '9') {num = num * 10 + (expr[i] - '0');i++;}push(&opnd, num);} else if (ch == '(') {push(&optr, '(');i++;} else if (ch == ')') {peek(&optr, &topOp);while (topOp != '(') {pop(&optr, &arithmeticOp);pop(&opnd, &b); pop(&opnd, &a);push(&opnd, calculate(a, b, arithmeticOp));peek(&optr, &topOp);}pop(&optr, &topOp); // 彈出左括號i++;} else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {peek(&optr, &topOp);while (getPriority(topOp) >= getPriority(ch)) {pop(&optr, &arithmeticOp);pop(&opnd, &b); pop(&opnd, &a);push(&opnd, calculate(a, b, arithmeticOp));peek(&optr, &topOp);}push(&optr, ch);i++;} else {i++; // 處理其他字符或結束}}pop(&opnd, &num); // 最終結果return num;
}
// 主函數中測試
int main() {char expr[] = "4 + 2 * 3 - 10 / (7 - 5)";printf("Result of %s is %d\n", expr, evalExpression(expr));return 0;
}
🌐 5.3 模擬瀏覽器前進后退功能
問題描述：使用兩個棧模擬瀏覽器的前進后退功能。
解決思路：使用兩個棧，backStack 存放后退的頁面，forwardStack 存放前進的頁面。訪問新頁面時壓入 backStack 并清空 forwardStack；后退時從 backStack 彈出并壓入 forwardStack；前進時從 forwardStack 彈出并壓入 backStack。
代碼概要（C語言，鏈棧）：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct PageNode {char url[100];struct PageNode* next;
} PageNode;typedef struct {PageNode* top;
} LinkStack;void initStack(LinkStack* s) { s->top = NULL; }
bool isEmpty(LinkStack* s) { return s->top == NULL; }void push(LinkStack* s, const char* url) {PageNode* newNode = (PageNode*)malloc(sizeof(PageNode));strcpy(newNode->url, url);newNode->next = s->top;s->top = newNode;
}bool pop(LinkStack* s, char* url) {if (isEmpty(s)) return false;PageNode* temp = s->top;strcpy(url, temp->url);s->top = s->top->next;free(temp);return true;
}bool peek(LinkStack* s, char* url) {if (isEmpty(s)) return false;strcpy(url, s->top->url);return true;
}// 模擬瀏覽器
LinkStack backStack, forwardStack;
void initBrowser() {initStack(&backStack);initStack(&forwardStack);
}void visitUrl(const char* url) {push(&backStack, url);// 訪問新頁面時清空前進棧char tempUrl[100];while (pop(&forwardStack, tempUrl)) { /* 只是清空 */ }printf("Visited: %s\n", url);
}void goBack() {char currentUrl[100], backUrl[100];if (pop(&backStack, currentUrl) && peek(&backStack, backUrl)) {push(&forwardStack, currentUrl);printf("Back to: %s\n", backUrl);} else {printf("Cannot go back.\n");}
}void goForward() {char forwardUrl[100];if (pop(&forwardStack, forwardUrl)) {push(&backStack, forwardUrl);printf("Forward to: %s\n", forwardUrl);} else {printf("Cannot go forward.\n");}
}int main() {initBrowser();visitUrl("www.homepage.com");visitUrl("www.news.com");visitUrl("www.mail.com");goBack(); // 回到 www.news.comgoBack(); // 回到 www.homepage.comgoForward(); // 前進到 www.news.comvisitUrl("www.search.com"); // 此時前進棧被清空return 0;
}
🔄 5.4 遞歸的非遞歸實現
問題描述：使用棧模擬遞歸過程，例如計算階乘。
解決思路：遞歸的本質是函數調用棧，我們可以用顯式棧來模擬。
代碼實現（C語言，順序棧實現階乘）：
#include <stdio.h>long factorialIterative(int n) {SeqStack stack; // 假設使用之前的順序棧，存儲類型為intinitStack(&stack);long result = 1;if (n == 0 || n == 1) return 1;while (n > 1) {push(&stack, n);n--;}int current;while (!isEmpty(&stack)) {pop(&stack, ¤t);result *= current;}return result;
}int main() {int n = 5;printf("Iterative %d! = %ld\n", n, factorialIterative(n));return 0;
}
?? 5.5 行編輯程序
問題描述：輸入若干串字符，遇到換行符 \n 則輸出本行當前處理結果。輸入以 # 結束。輸入 @ 表示回退到本行行首，輸入 `` 表示回退一格。
解決思路：使用棧存儲當前行的字符。遇到普通字符入棧；遇到 `` 則出棧（相當于退格）；遇到 @ 則清空棧（相當于清空當前行）。
代碼概要（C語言，順序棧）：
#include <stdio.h>void lineEditor() {SeqStack s;initStack(&s);char ch, temp;printf("Enter your text (end with #, use @ to clear line, use to backspace):\n");while ((ch = getchar()) != '#') {if (ch == '\n') {// 輸出當前行printf("\nLine output: ");// 逆序輸出棧內容較為復雜，可以先用一個臨時棧反轉SeqStack tempStack;initStack(&tempStack);while (!isEmpty(&s)) {pop(&s, &temp);push(&tempStack, temp);}while (!isEmpty(&tempStack)) {pop(&tempStack, &temp);putchar(temp);}printf("\n");initStack(&s); // 清空棧準備下一行} else if (ch == '@') {initStack(&s); // 清空棧（回退到行首）} else if (ch == '') {pop(&s, &temp); // 出棧（回退一格）} else {if (!isFull(&s)) {push(&s, ch); // 普通字符入棧} else {printf("Stack is full!\n");}}}
}int main() {lineEditor();return 0;
}
5.1 括號匹配問題
問題描述：給定一個只包括 '(', ')', '{', '}', '[', ']' 的字符串，判斷字符串中的括號是否匹配正確。
解決方案：使用棧來檢查括號匹配
- 遇到左括號時，將其壓入棧中
- 遇到右括號時，檢查棧頂的左括號是否與之匹配
- 最后檢查棧是否為空
代碼實現：
int isValid(char* s) {SeqStack stack;InitStack(&stack);int i = 0;char ch;while (s[i] != '\0') {if (s[i] == '(' || s[i] == '[' || s[i] == '{') {Push(&stack, s[i]); // 遇到左括號，入棧} else {if (IsEmpty(&stack)) { // 遇到右括號但棧已空，不匹配return 0;}GetTop(&stack, &ch); // 獲取棧頂元素if ((s[i] == ')' && ch == '(') ||(s[i] == ']' && ch == '[') ||(s[i] == '}' && ch == '{')) {Pop(&stack, &ch); // 匹配成功，彈出棧頂元素} else {return 0; // 不匹配}}i++;}return IsEmpty(&stack); // 最后棧空則有效，非空則無效
}
6. 總結與展望
通過本文的詳細講解，我們了解了：
- 棧是一種后進先出（LIFO）的線性數據結構
- 棧有兩種主要實現方式：順序棧（基于數組）和鏈棧（基于鏈表）
- 順序棧和鏈棧各有優缺點，適用于不同場景
- 棧在計算機科學中有廣泛的應用，如括號匹配、表達式求值和函數調用等
(中))
