數據結構day4—

一、棧的核心概念

什么是棧？

棧的核心特性

二、棧的基本操作

三、C 語言實現棧的兩種方式

1. 順序棧（基于數組實現）

實現代碼

順序棧的優缺點

2. 鏈式棧（基于鏈表實現）

實現代碼

鏈式棧的優缺點

四、棧的典型應用場景

五、總結

棧（Stack）作為一種經典的線性數據結構，因其 "后進先出"（LIFO）的特性，在編程領域有著廣泛的應用。無論是表達式求值、函數調用，還是括號匹配等場景，都能看到棧的身影。本文將帶你用 C 語言從零實現棧，深入理解其工作原理與實際應用。

一、棧的核心概念

什么是棧？

棧是一種限定僅在表尾進行插入和刪除操作的線性表。這里的 "表尾" 被稱為棧頂（Top），另一端則稱為棧底（Bottom）。

棧的核心特性

棧最顯著的特點是后進先出（Last In First Out，LIFO）：

最后進入棧的元素，最先被取出
最先進入棧的元素，最后被取出

生活中的棧示例：

疊放的書本，只能從最上方取書
瀏覽器的歷史記錄，"后退" 功能總是返回上一個訪問的頁面
手機應用的任務棧，最近打開的應用最先被關閉

二、棧的基本操作

棧的操作圍繞棧頂進行，主要包括以下幾種：

操作名稱	功能描述	時間復雜度
`initStack`	初始化棧	O(1)
`push`	向棧頂插入元素（入棧）	O(1)
`pop`	從棧頂移除元素（出棧）	O(1)
`peek`	獲取棧頂元素（不刪除）	O(1)
`isEmpty`	判斷棧是否為空	O(1)
`isFull`	判斷棧是否已滿	O(1)
`size`	獲取棧中元素個數	O(1)

三、C 語言實現棧的兩種方式

在 C 語言中，棧通常有兩種實現方式：基于數組的順序棧和基于鏈表的鏈式棧。

1. 順序棧（基于數組實現）

順序棧使用固定大小的數組作為底層存儲，實現簡單且訪問高效。

實現代碼

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 100  // 棧的最大容量// 棧的結構體定義
typedef struct {int data[MAX_SIZE];  // 存儲棧元素的數組int top;             // 棧頂指針（-1表示空棧）
} Stack;// 初始化棧
void initStack(Stack *stack) {stack->top = -1;  // 空棧狀態
}// 判斷棧是否為空
bool isEmpty(Stack *stack) {return stack->top == -1;
}// 判斷棧是否已滿
bool isFull(Stack *stack) {return stack->top == MAX_SIZE - 1;
}// 入棧操作
bool push(Stack *stack, int value) {if (isFull(stack)) {printf("棧已滿，無法入棧！\n");return false;}stack->data[++stack->top] = value;  // 先移動棧頂指針，再存入數據return true;
}// 出棧操作
bool pop(Stack *stack, int *value) {if (isEmpty(stack)) {printf("棧為空，無法出棧！\n");return false;}*value = stack->data[stack->top--];  // 先取出數據，再移動棧頂指針return true;
}// 獲取棧頂元素
bool peek(Stack *stack, int *value) {if (isEmpty(stack)) {printf("棧為空，無法獲取棧頂元素！\n");return false;}*value = stack->data[stack->top];return true;
}// 獲取棧的大小
int size(Stack *stack) {return stack->top + 1;  // 棧頂索引+1即為元素個數
}// 打印棧中所有元素
void printStack(Stack *stack) {if (isEmpty(stack)) {printf("棧為空！\n");return;}printf("棧元素（從棧底到棧頂）：");for (int i = 0; i <= stack->top; i++) {printf("%d ", stack->data[i]);}printf("\n");
}// 主函數示例
int main() {Stack stack;initStack(&stack);int value;// 測試入棧push(&stack, 10);push(&stack, 20);push(&stack, 30);printStack(&stack);  // 輸出：10 20 30// 測試獲取棧頂元素if (peek(&stack, &value)) {printf("棧頂元素：%d\n", value);  // 輸出：30}// 測試出棧if (pop(&stack, &value)) {printf("出棧元素：%d\n", value);  // 輸出：30}printStack(&stack);  // 輸出：10 20printf("棧的大小：%d\n", size(&stack));  // 輸出：2printf("棧是否為空：%s\n", isEmpty(&stack) ? "是" : "否");  // 輸出：否return 0;
}

順序棧的優缺點

優點：實現簡單，元素訪問速度快（數組隨機訪問特性）
缺點：
- 容量固定，無法動態擴容（可能溢出）
- 內存利用率不高（可能浪費空間）

2. 鏈式棧（基于鏈表實現）

鏈式棧使用鏈表節點存儲元素，可動態調整大小，內存利用率更高。

實現代碼

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>// 鏈表節點結構體
typedef struct Node {int data;               // 節點數據struct Node *next;      // 指向下一個節點的指針
} Node;// 棧的結構體（鏈式棧）
typedef struct {Node *top;  // 棧頂指針（指向鏈表頭節點）int size;   // 棧中元素個數
} LinkedStack;// 初始化棧
void initLinkedStack(LinkedStack *stack) {stack->top = NULL;stack->size = 0;
}// 判斷棧是否為空
bool isLinkedStackEmpty(LinkedStack *stack) {return stack->top == NULL;
}// 入棧操作
void pushLinkedStack(LinkedStack *stack, int value) {// 創建新節點Node *newNode = (Node *)malloc(sizeof(Node));if (newNode == NULL) {printf("內存分配失敗！\n");return;}newNode->data = value;newNode->next = stack->top;  // 新節點指向當前棧頂stack->top = newNode;        // 更新棧頂指針stack->size++;
}// 出棧操作
bool popLinkedStack(LinkedStack *stack, int *value) {if (isLinkedStackEmpty(stack)) {printf("棧為空，無法出棧！\n");return false;}Node *temp = stack->top;*value = temp->data;stack->top = stack->top->next;  // 更新棧頂指針free(temp);                     // 釋放節點內存stack->size--;return true;
}// 獲取棧頂元素
bool peekLinkedStack(LinkedStack *stack, int *value) {if (isLinkedStackEmpty(stack)) {printf("棧為空，無法獲取棧頂元素！\n");return false;}*value = stack->top->data;return true;
}// 打印棧中元素
void printLinkedStack(LinkedStack *stack) {if (isLinkedStackEmpty(stack)) {printf("棧為空！\n");return;}printf("棧元素（從棧頂到棧底）：");Node *current = stack->top;while (current != NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}// 銷毀棧（釋放所有節點內存）
void destroyLinkedStack(LinkedStack *stack) {Node *temp;while (stack->top != NULL) {temp = stack->top;stack->top = stack->top->next;free(temp);}stack->size = 0;
}// 主函數示例
int main() {LinkedStack stack;initLinkedStack(&stack);int value;// 測試入棧pushLinkedStack(&stack, 100);pushLinkedStack(&stack, 200);pushLinkedStack(&stack, 300);printLinkedStack(&stack);  // 輸出：300 200 100// 測試獲取棧頂元素if (peekLinkedStack(&stack, &value)) {printf("棧頂元素：%d\n", value);  // 輸出：300}// 測試出棧if (popLinkedStack(&stack, &value)) {printf("出棧元素：%d\n", value);  // 輸出：300}printLinkedStack(&stack);  // 輸出：200 100printf("棧的大小：%d\n", stack.size);  // 輸出：2// 銷毀棧destroyLinkedStack(&stack);return 0;
}

鏈式棧的優缺點

優點：
- 容量動態調整，無固定大小限制
- 內存利用率高（按需分配）
缺點：
- 實現相對復雜
- 每個節點需要額外存儲指針，內存開銷略大
- 訪問速度不如順序棧（鏈表順序訪問特性）

四、棧的典型應用場景

表達式求值：編譯器使用棧處理數學表達式（如后綴表達式轉換與計算）

括號匹配：檢查代碼中的括號是否正確配對（如()、[]、{}）

// 括號匹配示例函數
bool isParenthesesValid(char *str) {Stack stack;initStack(&stack);int i = 0;while (str[i] != '\0') {if (str[i] == '(' || str[i] == '[' || str[i] == '{') {push(&stack, str[i]);  // 左括號入棧} else if (str[i] == ')' || str[i] == ']' || str[i] == '}') {if (isEmpty(&stack)) return false;  // 右括號多了char top;pop(&stack, &top);// 檢查括號是否匹配if ((str[i] == ')' && top != '(') ||(str[i] == ']' && top != '[') ||(str[i] == '}' && top != '{')) {return false;}}i++;}return isEmpty(&stack);  // 左括號是否多了
}