一.棧的概念

棧是一種常見的數(shù)據(jù)結(jié)構(gòu)，它遵循后進先出的原則。?？梢钥醋魇且环N容器，其中的元素按照一種特定的順序進行插入和刪除操作。

壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數(shù)據(jù)在棧頂。
出棧：棧的刪除操作叫做出棧。出數(shù)據(jù)也在棧頂。

1.棧的特點

? ? 1.元素的插入和刪除操作只能在棧的一端進行，該端被稱為棧頂。

? ? 2.最后插入的元素是第一個被刪除的元素，因此稱為后進先出。

? ? 3.棧中的元素沒有編號或索引，只有棧頂指針來指示棧的當(dāng)前位置。

2.棧的優(yōu)點

1. 簡單高效：棧的操作是基于后進先出（LIFO）的原則，入棧和出棧操作都只涉及棧頂元素，因此操作的時間復(fù)雜度都是O(1)，使得棧的操作非常高效。

2. 空間效率高：棧的底層實現(xiàn)可以使用數(shù)組或鏈表，無論是使用靜態(tài)數(shù)組還是動態(tài)鏈表，都可以根據(jù)實際需要靈活分配內(nèi)存，因此在空間利用上比較高效。

3. 遞歸和回溯：棧在遞歸和回溯算法中扮演著重要的角色。遞歸函數(shù)調(diào)用時會將當(dāng)前函數(shù)的狀態(tài)（包括局部變量、返回地址等）壓入棧中，當(dāng)遞歸函數(shù)返回時，棧頂?shù)臓顟B(tài)會被彈出，恢復(fù)到上一層遞歸函數(shù)的狀態(tài)。

4. 撤銷操作：?？梢杂糜趯崿F(xiàn)撤銷操作，比如文本編輯器中的撤銷功能。每當(dāng)執(zhí)行一個操作時，將操作的狀態(tài)存儲在棧中，當(dāng)需要撤銷時，只需從棧中彈出最近的狀態(tài)。

3.棧的缺點

1. 容量限制：棧的容量是有限的，無論是基于數(shù)組還是鏈表實現(xiàn)的棧，都會受到內(nèi)存大小的限制。當(dāng)棧的元素個數(shù)超過容量時，會發(fā)生棧上溢（stack overflow）的錯誤。

2. 無隨機訪問：棧的特點是只能在棧頂進行插入和刪除操作，沒有提供隨機訪問的能力。如果需要訪問或修改棧中的其他元素，必須先將棧頂?shù)脑貜棾?#xff0c;直到達到目標(biāo)位置。

3. 不靈活：棧的特性決定了它的使用場景受到一定的限制。對于需要隨機訪問、頻繁插入和刪除的場景，?？赡懿皇亲罴堰x擇。

二.棧的功能

棧作為一種數(shù)據(jù)結(jié)構(gòu)，具有以下幾個主要的功能：

1. 入棧：將元素添加到棧的頂部（棧頂）。新元素成為棧頂，原有的棧頂元素依次向下移動。入棧操作可以用于將數(shù)據(jù)添加到棧中。

2. 出棧：從棧的頂部（棧頂）移除元素。被移除的元素是最后一個入棧的元素，即棧頂元素。出棧操作會改變棧的結(jié)構(gòu)，并返回被移除的元素。

3. 獲取棧頂元素：獲取棧頂?shù)脑?#xff0c;但不對棧進行修改。這個操作可以讓我們查看棧頂?shù)脑?#xff0c;而不改變棧的結(jié)構(gòu)。

4. 判斷棧是否為空：檢查棧是否不包含任何元素。如果棧中沒有元素，即棧為空，該函數(shù)返回真；否則，返回假。

5. 判斷棧是否已滿：檢查棧是否已達到其容量上限。對于基于數(shù)組實現(xiàn)的棧，如果數(shù)組已滿，即棧已滿，該函數(shù)返回真；否則，返回假。

三.棧的實現(xiàn)

1.創(chuàng)建棧

創(chuàng)建一個結(jié)構(gòu)體，里面的成員是數(shù)組以及指針。（在這里，為了大家能夠方便理解，用靜態(tài)的順序表來實現(xiàn)）

#include <stdio.h>
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 用于存儲棧中的元素int top; // 棧頂指針，指向棧頂元素的索引
} Stack;

2.初始化棧

將棧頂?shù)闹羔槼跏蓟癁?1，表示此棧為空。

// 初始化棧
void initStack(Stack* stack) {stack->top = -1; // 棧頂指針初始化為-1，表示棧為空
}

3.判斷棧是否為空

判斷棧是否為空。如果棧頂指針top等于-1，表示棧為空，返回1；否則，返回0。

// 判斷棧是否為空
int isEmpty(Stack* stack) {return stack->top == -1; // 棧為空時，棧頂指針為-1
}

4.?判斷是否已滿

判斷棧是否已滿。如果棧頂指針top等于數(shù)組最大索引（MAX_SIZE - 1），表示棧已滿，返回1；否則，返回0。

// 判斷棧是否已滿
int isFull(Stack* stack) {
return stack->top == MAX_SIZE - 1; // 棧滿時，棧頂指針等于數(shù)組最大索引
}

5.入棧

?入棧操作。首先使用isFull函數(shù)檢查棧是否已滿，如果已滿，則打印錯誤信息并返回；否則，將棧頂指針top加1，并將元素item放入棧頂位置data[top]。

// 入棧
void push(Stack* stack, int item) {
if (isFull(stack)) {
printf("Stack overflow!\n"); // 棧已滿，無法入棧
return;
}
stack->data[++stack->top] = item; // 棧頂指針加1，并將元素放入棧頂
}

?6.出棧

出棧操作。首先使用isEmpty函數(shù)檢查棧是否為空，如果為空，則打印錯誤信息并返回-1；否則，返回棧頂元素data[top]，并將棧頂指針top減1。

// 出棧
int pop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack underflow!\n"); // 棧為空，無法出棧
return -1;
}
return stack->data[stack->top--]; // 返回棧頂元素，并將棧頂指針減1
}

?7.獲取棧頂元素

獲取棧頂元素。首先使用isEmpty函數(shù)檢查棧是否為空，如果為空，則打印錯誤信息并返回-1；否則，返回棧頂元素data[top]，但不修改棧的結(jié)構(gòu)。

/ 獲取棧頂元素
int peek(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n"); // 棧為空，無棧頂元素
return -1;
}
return stack->data[stack->top]; // 返回棧頂元素，不修改棧的結(jié)構(gòu)
}

8.打印棧中元素

?打印棧中的元素。首先使用isEmpty函數(shù)檢查棧是否為空，如果為空，則打印提示信息；否則，使用循環(huán)從棧底到棧頂依次打印棧中的元素。

/ 打印棧中的元素（用于調(diào)試）
void printStack(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty!\n");
return;
}
printf("Stack: ");
for (int i = 0; i <= stack->top; i++) {
printf("%d ", stack->data[i]);
}
printf("\n");
}

四.棧的源碼呈現(xiàn)

?

#include <stdio.h>
#define MAX_SIZE 100typedef struct {int data[MAX_SIZE]; // 用于存儲棧中的元素int top; // 棧頂指針，指向棧頂元素的索引
} Stack;// 初始化棧
void initStack(Stack* stack) {stack->top = -1; // 棧頂指針初始化為-1，表示棧為空
}// 判斷棧是否為空
int isEmpty(Stack* stack) {return stack->top == -1; // 棧為空時，棧頂指針為-1
}// 判斷棧是否已滿
int isFull(Stack* stack) {return stack->top == MAX_SIZE - 1; // 棧滿時，棧頂指針等于數(shù)組最大索引
}// 入棧
void push(Stack* stack, int item) {if (isFull(stack)) {printf("Stack overflow!\n"); // 棧已滿，無法入棧return;}stack->data[++stack->top] = item; // 棧頂指針加1，并將元素放入棧頂
}// 出棧
int pop(Stack* stack) {if (isEmpty(stack)) {printf("Stack underflow!\n"); // 棧為空，無法出棧return -1;}return stack->data[stack->top--]; // 返回棧頂元素，并將棧頂指針減1
}// 獲取棧頂元素
int peek(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty!\n"); // 棧為空，無棧頂元素return -1;}return stack->data[stack->top]; // 返回棧頂元素，不修改棧的結(jié)構(gòu)
}// 打印棧中的元素（用于調(diào)試）
void printStack(Stack* stack) {if (isEmpty(stack)) {printf("Stack is empty!\n");return;}printf("Stack: ");for (int i = 0; i <= stack->top; i++) {printf("%d ", stack->data[i]);}printf("\n");
}// 主函數(shù)用于測試棧的功能
int main() {Stack stack;initStack(&stack); // 初始化棧push(&stack, 10);push(&stack, 20);push(&stack, 30);printStack(&stack); // 打印棧中的元素printf("Top element: %d\n", peek(&stack)); // 獲取棧頂元素while (!isEmpty(&stack)) {printf("Popped element: %d\n", pop(&stack)); // 依次出棧并輸出元素}return 0;
}