目錄
- 棧和隊列
- 棧
- 棧的基本概念
- 棧的順序存儲實現
- 棧的定義與初始化
- 入棧操作
- 出棧操作
- 讀取棧頂元素
- 判空和判滿操作
- 棧的銷毀操作
- 操作集合
棧和隊列
棧
棧的基本概念
棧的定義：
- 棧（Stack） 是一種線性表，它限定了數據元素的插入和刪除操作只能在表的一端進行。
- 允許操作的一端稱為 棧頂（Top），另一端稱為 棧底（Bottom）。
所以，棧就是 “先進后出（FILO, First In Last Out）” 的數據結構。
棧的特點：
- 受限性：只能在棧頂進行插入（push）和刪除（pop）。
- 線性結構：元素有先后次序。
- FILO 特性：最先入棧的元素最后出棧。
形象理解：就像一摞盤子，先放進去的盤子在最下面，拿的時候只能從最上面一個個拿走。
棧的基本操作：
- Push（入棧）：在棧頂插入一個新元素。
- Pop（出棧）：刪除棧頂元素，并返回該元素。
- GetTop（讀棧頂元素）：僅僅讀取棧頂元素，不刪除。
- InitStack（初始化棧）：建立一個空棧。
- StackEmpty（判空）：檢查棧是否為空。
- StackFull（判滿，順序棧時需要）：判斷棧是否已滿。
棧的存儲結構：
- 順序棧：
- 用數組存儲棧元素。
- 優點：實現簡單，存取快。
- 缺點：容量固定，可能溢出（上溢/下溢）。
- 鏈式棧
- 用鏈表存儲，棧頂一般在鏈表的表頭。
- 優點：容量不受限制。
- 缺點：需要額外指針，操作相對慢。
棧的順序存儲實現
棧的定義與初始化
順序棧是棧的一種順序存儲結構，用數組（連續內存）來存放數據元素。特點：
- 棧頂指針（top）指向棧頂元素的位置（或空元素的下一個位置）。
- 棧容量固定（靜態）或可擴展（動態）。
- 支持的基本操作：
- 初始化棧
InitStack - 入棧
Push - 出棧
Pop - 判空
IsEmpty - 獲取棧頂元素
GetTop
- 初始化棧
順序棧top 指針的指向在不同教材中有差異：
- top 指向棧頂元素（經典寫法，大部分算法書和面試中用的）
top是數組下標- 空棧時：
top = -1 - 入棧：先
top++，再存元素 - 出棧：取
data[top]，再top-- - 特點：top 總是指向有效元素的位置
- top 指向棧頂下一個空位（部分教材/視頻中用）
top是指針- 空棧時：
top = 0 - 入棧：直接存到
data[top]，然后top++ - 出棧：先
top--，再取data[top] - 特點：top 表示棧中元素數量，也就是下一個可用位置
兩種方法邏輯不同，但功能一樣，只是 top 的含義不同。
靜態順序棧：
- 定義：
#define MAXSIZE 100 typedef int SElemType; // 假設存儲 int 類型typedef struct {SElemType *base; // 棧底指針，指向數組首地址SElemType *top; // 棧頂指針，指向棧頂元素的下一個位置int stacksize; // 棧容量 } SqStack; - 初始化：
特點：// 初始化 void InitStack(SqStack *S) {S->base = data; // base 指向數組首地址S->top = S->base; // 空棧，top 指向第一個空位S->stacksize = MAXSIZE; }- 容量固定，無法擴容
- top 指向棧頂元素的下一個位置
- 入棧/出棧時用
*(S->top++) = e/*e = *(--S->top)
動態順序棧： 動態順序棧可以在棧滿時自動擴容。
- 定義：
typedef int SElemType;typedef struct {SElemType *base; // 棧底指針SElemType *top; // 棧頂指針，指向棧頂元素的下一個位置int stacksize; // 當前容量 } SqStack; - 初始化：
// 初始化 int InitStack(SqStack *S, int initSize) {S->base = (SElemType *)malloc(initSize * sizeof(SElemType));if (!S->base) return 0; // 分配失敗S->top = S->base; // 空棧S->stacksize = initSize;return 1; }
動態順序棧可以在
Push時判斷容量是否夠，如果不夠就 realloc 擴容。#include <stdio.h> #include <stdlib.h>typedef int SElemType; // 統一元素類型typedef struct {SElemType *base; // 棧底指針SElemType *top; // 棧頂指針（指向棧頂元素的下一個位置）int stacksize; // 當前容量 } SqStack;// 初始化棧 int InitStack(SqStack *S, int initSize) {S->base = (SElemType *)malloc(initSize * sizeof(SElemType));if (!S->base) return 0; // 分配失敗S->top = S->base; // 空棧：棧頂=棧底S->stacksize = initSize;return 1; }// 入棧 int Push(SqStack *S, SElemType x) {// 判斷棧滿，需要擴容if (S->top - S->base >= S->stacksize) {int newSize = S->stacksize * 2;SElemType *newBase = (SElemType *)realloc(S->base, newSize * sizeof(SElemType));if (!newBase) return 0; // 擴容失敗// 更新指針和容量S->top = newBase + (S->top - S->base); // 調整棧頂指針（原偏移量不變）S->base = newBase;S->stacksize = newSize;printf("棧擴容到 %d\n", newSize);}*(S->top++) = x; // 先賦值，再移動棧頂指針return 1; }// 出棧（將棧頂元素存入e，成功返回1，失敗返回0） int Pop(SqStack *S, SElemType *e) {if (S->top == S->base) return 0; // 空棧*e = *(--S->top); // 先移動棧頂指針，再取值return 1; }int main() {SqStack S;if (!InitStack(&S, 3)) { // 初始容量3printf("棧初始化失敗\n");return 1;}// 入棧10個元素（測試擴容）for (int i = 1; i <= 10; i++) {if (Push(&S, i)) {printf("入棧: %d, 當前元素數: %d\n", i, S.top - S.base);} else {printf("入棧 %d 失敗\n", i);}}// 出棧所有元素SElemType e;printf("\n出棧順序：\n");while (Pop(&S, &e)) {printf("出棧: %d\n", e);}free(S.base); // 釋放堆內存return 0; }
入棧操作
入棧（Push） 就是把一個新元素壓入棧頂的操作。
核心邏輯：
- 判斷棧是否已滿（靜態棧）或是否需要擴容（動態棧）。
- 棧頂指針
top上移（或計算位置）。 - 將元素放到棧頂位置。
- 更新
top（或數組索引）。
棧遵循 后進先出（LIFO） 原則，所以新元素總是放在棧頂。
靜態順序棧入棧：
void Push(SqStack *S, int e) {// 判斷是否棧滿if (S->top - S->base >= S->stacksize) {return 0; // 入棧失敗}*(S->top) = e; // 把元素放到 top 指向的位置S->top++; // top 后移，指向下一個空位return 1; // 入棧成功
}
- 空棧時：
top == base。 - 入棧成功后：
top始終指向“棧頂元素的下一個位置”。 - 棧滿條件：
top - base == stacksize。 - 棧頂元素：
*(top - 1)。
動態順序棧入棧：
// 入棧
void Push(SqStack *S, int e) {if (S->top - S->base >= S->stacksize) { // 棧滿，需要擴容S->base = (ElemType *)realloc(S->base, (S->stacksize + STACKINCREMENT) * sizeof(ElemType));if (!S->base) exit(0); // 內存不足S->top = S->base + S->stacksize; // 重新定位 topS->stacksize += STACKINCREMENT; // 更新容量}*(S->top) = e; // 把元素放到棧頂S->top++; // top 指針上移
}
動態順序棧入棧圖示：
初始棧（容量=3） 入棧擴容后（容量=6）
+----+----+----+ +----+----+----+----+----+----+
| 10 | 20 | 30 | | 10 | 20 | 30 | 40 | | |
+----+----+----+ +----+----+----+----+----+----+↑ ↑top top
出棧操作
// 出棧操作：將棧頂元素彈出并返回給 e
int Pop(SqStack *S, int *e) {if (S->top == S->base) return 0; // 棧空S->top--; // 指針下移*e = *(S->top); // 取出元素return 1;
}
S->top--; 和 *e = *(S->top); 可以合并為 *e = *(--S->top);
有道例題：寫出下列程序段的輸出結果
void main(){Stack S;InitStack(S);x='c'; y='k';Push(S,x); Push(S,'a'); Push(S,y);Pop(S,x); Push(S,'t'); Push(S,x);Pop(S,x); Push(S,'s');While(!StackEmpty(S)) {Pop(S,y); printf(y);}printf(x);
}
Pop 會將出棧的數據返回，在這題中的重點是 Pop 操作會改變原來 x 中的數據
讀取棧頂元素
核心思想：
- 棧頂元素位于
top的前一個位置（因為top指向棧頂元素的下一個空位）。 - 不改變
top指針的值，只是返回棧頂元素。
// 取棧頂元素，不出棧
int GetTop(SqStack S, int *e) {if (S.top == S.base) return ERROR; // 空棧*e = *(S.top - 1); // 棧頂元素return 1;
}
top指向棧頂元素的下一個位置；- 棧頂元素是
*(top - 1)； GetTop不改變棧結構，只返回棧頂元素；
判空和判滿操作
- 判空操作：
核心思想：棧空時，top == base，因為沒有元素，棧頂指針就在棧底。// 判空 int StackEmpty(SqStack S) {if (S.top == S.base) return 1; // 棧空else return 0; // 棧非空 } - 判滿操作
核心思想：棧滿時，top - base == stacksize，因為棧頂指針指向下一個空位，減去棧底得到元素個數等于容量。// 判滿 int StackFull(SqStack S) {if (S.top - S.base == S.stacksize)return 1; // 棧滿elsereturn 0; // 棧未滿 }
棧的銷毀操作
核心思想：
- 棧底指針
base是動態分配的，所以只需要free(base)。 - 銷毀后，將
base和top置為NULL，stacksize置為 0，防止野指針。
Status DestroyStack(SqStack *S) {if (S->base) {free(S->base); // 釋放動態分配的內存S->base = NULL;S->top = NULL;S->stacksize = 0;return OK;}return ERROR; // 棧本身為空或未初始化
}
- 棧使用
malloc分配內存后，必須用free釋放，否則會 內存泄漏。 - 銷毀后把
base和top置為NULL，stacksize置 0，避免野指針。 - 對靜態順序棧（數組固定分配）則不需要銷毀操作，因為數組在棧上分配，程序結束自動釋放。
操作集合
#include <stdio.h>
#include <stdlib.h>#define MAXSIZE 100
#define OK 1
#define ERROR 0typedef int Status;
typedef int SElemType;// 順序棧定義（老師寫法）
typedef struct {SElemType *base; // 棧底指針SElemType *top; // 棧頂指針（指向下一個空位）int stacksize; // 棧容量
} SqStack;// 初始化棧
Status InitStack(SqStack *S) {S->base = (SElemType *)malloc(MAXSIZE * sizeof(SElemType));if (!S->base) return ERROR;S->top = S->base;S->stacksize = MAXSIZE;return OK;
}// 入棧
Status Push(SqStack *S, SElemType e) {if (S->top - S->base == S->stacksize) return ERROR; // 棧滿*(S->top) = e;S->top++;return OK;
}// 出棧
Status Pop(SqStack *S, SElemType *e) {if (S->top == S->base) return ERROR; // 空棧S->top--;*e = *(S->top);return OK;
}// 取棧頂元素（不出棧）
Status GetTop(SqStack S, SElemType *e) {if (S.top == S.base) return ERROR; // 空棧*e = *(S.top - 1);return OK;
}// 判空
Status StackEmpty(SqStack S) {return S.top == S.base ? 1 : 0;
}// 判滿
Status StackFull(SqStack S) {return (S.top - S.base == S.stacksize) ? 1 : 0;
}// 銷毀棧
Status DestroyStack(SqStack *S) {if (S->base) {free(S->base);S->base = NULL;S->top = NULL;S->stacksize = 0;return OK;}return ERROR;
}// 打印棧內元素（從棧底到棧頂）
void PrintStack(SqStack S) {SElemType *p = S.base;while (p < S.top) {printf("%d ", *p);p++;}printf("\n");
}// 測試順序棧操作
int main() {SqStack S;if (InitStack(&S) == ERROR) {printf("棧初始化失敗！\n");return 0;}printf("棧是否為空: %d\n", StackEmpty(S));// 入棧for (int i = 1; i <= 5; i++) {Push(&S, i);printf("入棧: %d, 棧頂元素: %d\n", i, *(S.top - 1));}printf("當前棧: ");PrintStack(S);printf("棧是否已滿: %d\n", StackFull(S));// 取棧頂元素SElemType e;if (GetTop(S, &e) == OK) {printf("棧頂元素: %d\n", e);}// 出棧while (!StackEmpty(S)) {Pop(&S, &e);printf("出棧元素: %d\n", e);}printf("棧是否為空: %d\n", StackEmpty(S));// 銷毀棧DestroyStack(&S);printf("銷毀棧后, 棧容量: %d, base指針: %p\n", S.stacksize, S.base);return 0;
}
程序運行結果如下：
)
 核心概念、重要指令)
)
