數據結構（C語言篇）：（八）棧

前言

????????棧作為一種基礎且強大的線性數據結構，在計算機科學領域扮演著至關重要的角色。其"后進先出"（LIFO）的核心特性，使其成為處理函數調用、表達式求值、括號匹配等場景的理想選擇。從程序執行時系統棧的管理，到日常開發中撤銷操作、瀏覽歷史等功能的實現，棧的應用無處不在。本文將深入探討棧的工作原理、實現方式以及典型應用場景，幫助讀者全面理解這一數據結構的精髓及其在實際工程中的價值。下面就讓我們正式開始吧！

一、概念與結構

? ? ? ? 棧：是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素等操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。

????????壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。

? ? ? ? 出棧：棧的刪除操作叫做出棧。出數據也在棧頂。

? ? ? ? 壓棧和出棧的示意圖如下：

? ? ? ? 棧的底層結構選型：

? ? ? ? 棧的實現我們一般可以使用數組或者鏈表來實現，相對而言數組的結構更優一些。因為數組在尾上插入數據的代價是比較小的。

? ? ? ? 如果使用數組來實現：

? ? ? ? 此時入棧和出棧的時間復雜度都是 $O(1)$ 。

? ? ? ? 如果使用鏈表來實現：

? ? ? ? 此時出棧和入棧的時間復雜度也同樣都是 $O(1)$ 。

二、棧的實現

2.1? 頭文件的準備

? ? ? ? 我們將棧的結構和一系列棧相關的函數在頭文件Stack.h中聲明如下：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>//定義棧的結構
typedef int STDataType;
typedef struct Stack {STDataType* arr;int top; //指向棧頂的位置---剛好就是棧中有效數據個數int capacity;//棧的空間大小
}ST;//初始化
void STInit(ST* ps);
//銷毀
void STDesTroy(ST* ps);//入棧——棧頂
void STPush(ST* ps, STDataType x);
//出棧———棧頂
void STPop(ST* ps);
//取棧頂元素
STDataType STTop(ST* ps);//棧是否為空
bool STEmpty(ST* ps);
//獲取棧中有效元素個數
int STSize(ST* ps);

2.2? 函數的實現

2.2.1? STInit( )函數（初始化）

? ? ? ? 函數的實現邏輯如下：

? ? ? ??1.? 初始化數組指針：先將棧的數組指針arr置為NULL，此時表示棧沒有分配任何內存空間。

ps->arr = NULL;

????????2.? 初始化棧頂指針和容量：

ps->top = 0：將棧頂指針設置為0，表示空棧
ps->capacity = 0：將棧的容量設置為0，表示當前沒有分配空間

ps->top = ps->capacity = 0;

? ? ? ? 完整代碼如下：

//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;}

2.2.2? STDestroy( )函數（銷毀）

? ? ? ? 函數實現邏輯如下：

????????1.? 釋放動態數組內存：

檢查?ps->arr?是否為?NULL（是否分配了內存）
如果分配了內存，使用?free()?釋放數組內存
避免對?NULL?指針調用?free()

if(ps->arr)free(ps->arr);

????????2.? 重置指針和狀態：

ps->arr = NULL：將數組指針設置為?NULL，避免野指針
ps->top = 0：將棧頂指針重置為0，表示空棧
ps->capacity = 0：將容量重置為0，表示沒有分配空間

ps->arr = NULL;
ps->top = ps->capacity = 0;

? ? ? ? 完整代碼如下：

//銷毀
void STDesTroy(ST* ps)
{if(ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}

? ? ? ? 使用示例如下：

ST stack;
STInit(&stack);      // 初始化棧// 使用棧進行各種操作
STPush(&stack, 10);
STPush(&stack, 20);
// ...STDesTroy(&stack);   // 銷毀棧，釋放資源
// 現在stack可以被重新初始化或丟棄

2.2.3? STPush( )函數（入棧）

? ? ? ? 首先畫圖分析：

? ? ? ? 函數實現邏輯如下：

????????1.? 參數驗證：確保棧指針?ps?不為?NULL。

assert(ps);

????????2.? 檢查空間是否足夠：如果棧頂指針等于容量，說明棧已滿，需要擴容。

if (ps->top == ps->capacity)

????????3.? 動態擴容機制：首次分配時，如果容量為0（初始狀態），先分配四個元素的空間；后續擴容時，如果已有容量，就將容量擴大為原來的2倍。（使用?realloc?重新分配內存，可以保留原有數據）

int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));

????????4.? 錯誤處理：檢查內存分配是否成功，如果失敗就輸出錯誤信息，并退出程序。

if (tmp == NULL)
{perror("realloc fail！");exit(1);
}

????????5.? 更新指針和容量：首先更新數組指針指向新分配的內存，然后更新容量為新分配的大小。

ps->arr = tmp;
ps->capacity = newCapacity;

????????6.? 壓入元素：將元素?x?放入棧頂位置?ps->arr[ps->top]，然后棧頂指針?ps->top?自增1。

ps->arr[ps->top++] = x;

? ? ? ? 完整代碼如下所示：

//入棧——棧頂
void STPush(ST* ps, STDataType x)
{assert(ps);//判斷空間是否足夠if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail！");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空間足夠ps->arr[ps->top++] = x;
}

? ? ? ? 使用示例如下：

ST stack;
STInit(&stack);STPush(&stack, 10);  // 分配4個空間，壓入10
STPush(&stack, 20);  // 壓入20
STPush(&stack, 30);  // 壓入30  
STPush(&stack, 40);  // 壓入40，棧滿
STPush(&stack, 50);  // 擴容到8個空間，壓入50

2.2.4? STPop( )函數（出棧）

? ? ? ? 要想實現出棧函數，我們需要先實現一個STEmpty （判空）函數，如下所示：

//棧是否為空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

? ? ? ?畫圖分析如下：

? ? ? ? STPop的實現邏輯如下：

? ? ? ? 1.? 前置條件檢查：首先使用用?STEmpty?函數檢查棧是否為空，如果棧為空，則斷言失敗，不能執行彈出操作。同時需要確保棧中至少有一個元素可彈出。

????????2.? 執行彈出操作：首先將棧頂指針?top?減1，這樣原來的棧頂元素就不再屬于棧的有效范圍，但實際上并沒有刪除數據，只是改變了棧的邊界。

ps->top--;

? ? ? ? 完整代碼如下所示：

//出棧———棧頂
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}

? ? ? ? 使用示例如下：

ST stack;
STInit(&stack);STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);
// 棧: [10, 20, 30], top=3STPop(&stack);  // 彈出30
// 棧: [10, 20], top=2STPop(&stack);  // 彈出20  
// 棧: [10], top=1STPop(&stack);  // 彈出10
// 棧: 空, top=0

2.2.5? STTop( )函數（取棧頂元素）

? ? ? ? 畫圖分析如下：

? ? ? ? 函數的實現邏輯如下：

????????1.? 前置條件檢查：首先使用?STEmpty?函數檢查棧是否為空，如果棧為空，則斷言失敗，不能獲取棧頂元素。需要確保棧中至少有一個元素。

assert(!STEmpty(ps));

? ? ? ? 2.? 返回棧頂元素：

ps->top?指向下一個空位置（棧頂的下一個位置）
ps->top - 1?就是當前棧頂元素的位置
返回該位置的元素值

return ps->arr[ps->top - 1];

????????完整代碼如下：

//取棧頂元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}

? ? ? ? 使用示例：

ST stack;
STInit(&stack);STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);
// 棧: [10, 20, 30], top=3STDataType topValue = STTop(&stack);  // 獲取棧頂值30
printf("棧頂元素: %d\n", topValue);   // 輸出: 棧頂元素: 30// 棧仍然保持: [10, 20, 30], top=3

2.2.6? STSize( )函數（獲取棧中元素個數）

? ? ? ? 函數實現邏輯如下：

????????1.? 參數驗證：確保棧指針?ps?不為?NULL。

assert(ps);

????????2.? 返回元素數量：直接返回棧頂指針?top?的值。因為?top?既指向下一個空位置，又表示當前元素數量。

return ps->top;

? ? ? ? 完整代碼如下：

//獲取棧中有效元素個數
int STSize(ST* ps)
{assert(ps);return ps->top;
}

? ? ? ? 使用示例如下：

ST stack;
STInit(&stack);printf("初始棧大小: %d\n", STSize(&stack));  // 輸出: 0STPush(&stack, 10);
STPush(&stack, 20);
STPush(&stack, 30);printf("當前棧大小: %d\n", STSize(&stack));  // 輸出: 3STPop(&stack);
printf("彈出后棧大小: %d\n", STSize(&stack));  // 輸出: 2