🍅關注博主🎗? 帶你暢游技術世界，不錯過每一次成長機會！
📙C 語言百萬年薪修煉課程 通俗易懂，深入淺出，匠心打磨，死磕細節，6年迭代，看過的人都說好。

如何在 C 語言中實現棧

在 C 語言中，棧（Stack）是一種常見的數據結構，它遵循后進先出（Last In First Out，LIFO）的原則。這意味著最后添加到棧中的元素將首先被移除。

一、棧的基本概念

棧是一種線性數據結構，具有以下特點：

1. 棧頂（Top）：棧的頂部元素，是進行插入和刪除操作的一端。
2. 棧底（Bottom）：棧的底部元素，是相對固定的一端。

二、棧的操作

常見的棧操作包括：

1. push：將元素壓入棧頂。
2. pop：彈出棧頂元素。
3. peek（或者 top）：獲取棧頂元素但不彈出。
4. isEmpty：判斷棧是否為空。

三、使用數組實現棧

以下是使用數組來實現棧的 C 語言代碼示例：

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>#define MAX_SIZE 100typedef struct {int items[MAX_SIZE];int top;
} 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;
}// 壓入元素到棧
void push(Stack *stack, int element) {if (isFull(stack)) {printf("Stack Overflow!\n");return;}stack->items[++stack->top] = element;
}// 彈出棧頂元素
int pop(Stack *stack) {if (isEmpty(stack)) {printf("Stack Underflow!\n");return -1;}int element = stack->items[stack->top];stack->top--;return element;
}// 獲取棧頂元素但不彈出
int peek(Stack *stack) {if (isEmpty(stack)) {printf("Stack is empty!\n");return -1;}return stack->items[stack->top];
}int main() {Stack stack;initStack(&stack);push(&stack, 10);push(&stack, 20);push(&stack, 30);printf("Top element: %d\n", peek(&stack));int poppedElement = pop(&stack);if (poppedElement!= -1) {printf("Popped element: %d\n", poppedElement);}printf("Top element after pop: %d\n", peek(&stack));return 0;
}

在上述代碼中：

• initStack 函數用于初始化棧，將棧頂指針設置為 -1，表示棧為空。
• isEmpty 函數通過檢查棧頂指針是否為 -1 來判斷棧是否為空。
• isFull 函數通過檢查棧頂指針是否達到數組的最大索引來判斷棧是否已滿。
• push 函數在壓入元素之前，先檢查棧是否已滿。如果未滿，將元素添加到棧頂，并更新棧頂指針。
• pop 函數在彈出元素之前，先檢查棧是否為空。如果不為空，返回棧頂元素，并更新棧頂指針。
• peek 函數返回棧頂元素，但不修改棧的狀態。

四、使用鏈表實現棧

除了使用數組，我們還可以使用鏈表來實現棧。以下是使用鏈表實現棧的 C 語言代碼示例：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef struct Node {int data;struct Node *next;
} Node;typedef struct {Node *top;
} Stack;// 初始化棧
void initStack(Stack *stack) {stack->top = NULL;
}// 判斷棧是否為空
bool isEmpty(Stack *stack) {return stack->top == NULL;
}// 壓入元素到棧
void push(Stack *stack, int element) {Node *newNode = (Node *)malloc(sizeof(Node));if (newNode == NULL) {printf("Memory allocation failed!\n");return;}newNode->data = element;newNode->next = stack->top;stack->top = newNode;
}// 彈出棧頂元素
int pop(Stack *stack) {if (isEmpty(stack)) {printf("Stack Underflow!\n");return -1;}Node *temp = stack->top;int element = temp->data;stack->top = stack->top->next;free(temp);return element;
}// 獲取棧頂元素但不彈出
int peek(Stack *stack) {if (isEmpty(stack)) {printf("Stack is empty!\n");return -1;}return stack->top->data;
}// 打印棧
void printStack(Stack *stack) {Node *current = stack->top;printf("Stack: ");while (current!= NULL) {printf("%d ", current->data);current = current->next;}printf("\n");
}int main() {Stack stack;initStack(&stack);push(&stack, 10);push(&stack, 20);push(&stack, 30);printStack(&stack);int poppedElement = pop(&stack);if (poppedElement!= -1) {printf("Popped element: %d\n", poppedElement);}printStack(&stack);printf("Top element: %d\n", peek(&stack));return 0;
}

在這個鏈表實現的棧中：

• 每個節點包含數據和指向下一個節點的指針。
• initStack 函數將棧頂指針初始化為 NULL，表示空棧。
• push 函數創建一個新節點，將其數據設置為要壓入的元素，并將其鏈接到當前棧頂節點之前，更新棧頂指針。
• pop 函數如果棧不為空，刪除棧頂節點，返回其數據，并更新棧頂指針，同時釋放已刪除節點的內存。
• peek 函數返回棧頂節點的數據。
• printStack 函數用于打印棧中的所有元素。

五、兩種實現方式的比較

（一）空間復雜度

• 數組實現：在創建棧時需要預先分配固定大小的連續內存空間。如果棧的實際使用空間小于預分配的空間，會造成一定的內存浪費；如果棧的實際使用空間超過預分配的空間，還需要進行擴容操作，可能涉及到數據的復制和內存的重新分配，增加了額外的開銷。
• 鏈表實現：每個節點在需要時動態分配內存，不會造成內存的預先浪費。但是，每個節點除了存儲數據外，還需要額外的空間來存儲指針，因此會有一些額外的內存開銷。

（二）時間復雜度

• 數組實現：
  • push 操作：在棧未滿的情況下，時間復雜度為 O(1)。
  • pop 操作：在棧不為空的情況下，時間復雜度為 O(1)。
  • 訪問棧頂元素：時間復雜度為 O(1)。
• 鏈表實現：
  • push 操作：需要創建新節點并更新指針，時間復雜度為 O(1)。
  • pop 操作：需要刪除節點并更新指針，時間復雜度為 O(1)。
  • 訪問棧頂元素：時間復雜度為 O(1)。

總體來說，兩種實現方式在常見操作的時間復雜度上是相同的。

（三）靈活性

• 數組實現：由于數組的大小是固定的，在需要動態調整棧的大小時，操作相對復雜。
• 鏈表實現：可以更靈活地添加和刪除元素，不需要考慮固定大小的限制。

（四）適用場景

• 數組實現：適用于事先知道棧的最大規模，并且對內存使用較為敏感的場景。
• 鏈表實現：適用于無法確定棧的最大規模，或者需要更靈活地管理棧的空間的場景。

六、棧的應用場景

（一）函數調用

在計算機程序中，當一個函數調用另一個函數時，系統會將當前函數的執行上下文（包括參數、局部變量、返回地址等）壓入棧中。當被調用函數執行完畢后，系統從棧中彈出之前保存的執行上下文，恢復到調用函數繼續執行。

（二）表達式求值

在對算術表達式進行求值時，可以使用棧來存儲操作數和運算符。通過按照特定的規則進行入棧和出棧操作，可以實現表達式的正確求值。

（三）括號匹配

檢查一段包含括號（如 ()、[]、{}）的文本中括號是否匹配，可以使用棧來輔助判斷。遇到左括號入棧，遇到右括號時與棧頂的左括號進行匹配，如果匹配成功則彈出棧頂元素，否則表示括號不匹配。

（四）回溯算法

在一些需要回溯的算法中，如深度優先搜索、八皇后問題等，可以使用棧來保存中間狀態，以便在需要時進行回溯。

七、總結

在 C 語言中，我們可以使用數組或鏈表來實現棧。兩種實現方式各有優缺點，應根據具體的應用場景選擇合適的實現方式。理解棧的概念和實現原理對于解決許多編程問題非常有幫助，并且在實際的開發中有著廣泛的應用。

🎉相關推薦

• 📙C 語言百萬年薪修煉課程 通俗易懂，深入淺出，匠心打磨，死磕細節，6年迭代，看過的人都說好。
• 🍅博客首頁-關注博主🎗? 帶你暢游技術世界，不錯過每一次成長機會！
• 📙CSDN專欄-C語言修煉
• 📙技術社區-墨松科技