一. 棧的認識

1. 棧的基本概念

棧是一種特殊的線性表，只允許在固定的一端進行插入和刪除元素的操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵循后進先出的原則。

• 壓棧： 棧的插入操作叫做進棧/壓棧/入棧，入數據的元素在棧頂。
• 出棧： 棧的出棧也叫刪除操作，出數據也在棧頂。

2.棧的基本操作

操作	描述	時間復雜度
Push(x)	將元素x壓入棧頂	O(1)
Pop()	出棧彈出元素	O(1)
Top()	返回棧頂元素不出棧	O(1)
Empty()	檢查棧是否為空	O(1)
Size()	返回棧中元素數量	O(1)

二. 棧的核心優勢

1. 高效的時間復雜度

• 入棧、出棧、取棧頂均為常數時間O(1)操作,適合高頻調用場景。
• 專注“頂部”操作，避免不必要的復雜度。
• 對比其他數據結構：
  數組：隨機訪問快O(1),但插入刪除中間元素移動數據O(n);
  鏈表：插入刪除中間元素快O(1)，但隨機訪問慢O(n);

2. 簡潔的邏輯設計

• 減少代碼的復雜度，設計更簡單。
• 通過壓棧和出棧自動維護操作順序，無需手動跟蹤索引指針。

3. 內存管理優化

• 局部性原理：棧操作集中在頂部，數據訪問具有空間局部性，利用CPU緩存命中。
• 動態擴容策略：棧實現如動態數組通過按需擴容平衡時間和空間效率。

三. 棧的代碼實現

1.棧的結構定義

typedef struct Stack
{STDataType* a; // 動態數組，存儲棧里的元素int top;       // 棧頂指針（初始為0，表示空棧）int capacity; // 棧的最大容量
}ST;

• a：用指針指向一塊內存。
• top：指向當前棧頂的元素初始為0，表示空棧
• capacity：棧的最大容量

2. 棧的初始化

//初始化
void STInit(ST* pst)
{pst->a = NULL;//top指向棧頂數據的下一個位置pst->capacity = pst->top = 0;
}

• 初始化指針賦值為NULL，capacity和top賦值為0。

3. 入棧 （動態擴容）

//入棧
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->capacity == pst->top){int newcapacity = pst->top == 0 ? 4 : 2 * pst->capacity;STDataType* newnode = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));if (newnode == NULL){perror("realloc fail");exit(-1);}pst->a = newnode;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}

• 當capacity等于top時，如果為空則開辟4個空間，不為空時開辟當前空間的二倍。
• 將插入的值先存放在top下標位置再top++。

4. 出棧

//出棧
void STPop(ST* pst)
{assert(pst && pst->top>0);pst->top--;
}

• 直接top- - 限制訪問完成出棧。

5. 取棧頂數據

//取棧頂數據
STDataType STTop(ST* pst)
{assert(pst && pst->top>0);return pst->a[pst->top - 1];
}

• top的位置是在最后一個元素的下一個位置，所以取棧頂數據直接取top減1的下標。

6. 判斷棧是否為空

//判空
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}

• 返回值是bool類型，如果top == 0則返回true。

7. 獲取棧的數據個數

//獲取數據個數
int STSize(ST* pst)
{assert(pst);return pst->top;
}

• 因為棧的位置是從0開始的，所以直接返回top就是棧內部的數據個數。

8.銷毀

//銷毀
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}

• 釋放掉開辟的空間，將開辟的空間置為NULL，把top和capacity也置為空。

9.完整代碼展示

• Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;//初始化
void STInit(ST* pst);//銷毀
void STDestroy(ST* pst);//入棧
void STPush(ST* pst, STDataType x);//出棧
void STPop(ST* pst);//取棧頂數據
STDataType STTop(ST* pst);//判空
bool STEmpty(ST* pst);//獲取數據個數
int STSize(ST* pst);

• Stack.c

#include "Stack.h"//初始化
void STInit(ST* pst)
{pst->a = NULL;//top指向棧頂數據的下一個位置pst->capacity = pst->top = 0;
}//銷毀
void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}//入棧
void STPush(ST* pst, STDataType x)
{assert(pst);if (pst->capacity == pst->top){int newcapacity = pst->top == 0 ? 4 : 2 * pst->capacity;STDataType* newnode = (STDataType*)realloc(pst->a, newcapacity * sizeof(STDataType));if (newnode == NULL){perror("realloc fail");exit(-1);}pst->a = newnode;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}//出棧
void STPop(ST* pst)
{assert(pst && pst->top>0);pst->top--;
}//取棧頂數據
STDataType STTop(ST* pst)
{assert(pst && pst->top>0);return pst->a[pst->top - 1];
}//判空  等于0就為真
bool STEmpty(ST* pst)
{assert(pst);return pst->top == 0;
}//獲取數據個數
int STSize(ST* pst)
{assert(pst);return pst->top;
}

入棧順序為：1 2 3 4 5
出棧順序為：5 4 3 2 1

總結

根據上述講解，相信大家對棧有更深層的理解了。棧是程序運行時內存管理的核心區域之一，遵循后進先出原則，由操作系統或運行時環境自動分配和釋放，無需顯式干預。其設計目標是高效管理函數調用和局部變量，但受限于固定大小，需謹慎使用以避免溢出。合理的使用棧能讓程序又快又穩，濫用則容易崩潰。本篇文章到這里就結束了，感謝大家的閱讀，你們的點贊收藏加關注就是博主最大的動力。

---

【數據結構】——順序表鏈表（超詳細解析！！！）
C語言——結構體指南(小白一看就懂！！！）
力扣（LeetCode) ——移除鏈表元素(C語言）