🎉🎉想快速入門資料結構，推薦訂閱作者的初階資料結構專欄！此專欄預計更新：順序表，鏈表，堆疊，佇列，二叉樹，排序演算法等等
🎉🎉初階資料結構我們通過c語言實作，所以此專欄也可以幫助大家鞏固大家的c語言知識
🎉🎉源代碼已上傳至我的碼云
🎉🎉博主的微信公眾號關注啦，關注我每天學習一道題，點我關注
知識引入
其實堆疊這個概念，我們早在c語言階段就了解過了，
像啥函式堆疊幀呀，壓堆疊啊啥的，我們都已經了解并掌握過了，
我們今天實作的資料結構，也叫做堆疊，特征其實是跟函式壓堆疊差不多的道理
為了形象地了解堆疊的特性，我們可以打一個比方，假設有一把槍，你在進行射擊訓練
你肯定首先是要裝子彈進彈夾的
肯定是先裝的在彈夾的底部，而后裝的在彈夾的頂部，這是顯而易見的
我們裝完了子彈，肯定要把它給打出去
這一步我們發現，子彈一定是先從頂部打出去
所以我們發現，子彈滿足后進先出的特征，即后面進入的子彈會先被打出去
這也是我們堆疊的特征，后進先出
初步了解
堆疊：本質是一種操作受限的線性表
它只能支持在某一端的插入，洗掉與訪問，與我們知識引入的子彈夾本質相同，都是后進先出
操作的一端我們叫做堆疊頂
不能操作的一端叫堆疊底
既然是線性表，我們就可以使用鏈表或者順序表實作
但筆者認為堆疊用順序表實作要好一些
理由如下
- 順序表的尾部插入與洗掉的復雜度為O(1)，我們可以選擇把尾部作為堆疊頂
- 我們不需要特意去查找順序表的尾部
相比與鏈表，既然插入洗掉的復雜度都達到了O(1),克服了順序表最大的缺點，我們就不需要使用鏈表了
堆疊的定義
頭檔案定義
既然我們要使用順序表要實作堆疊，我們就用順序表的定義方式定義堆疊就行了
沒看過順序表文章的小伙伴，點此直達
typedef int STDataType;//方便存盤各種各樣的資料
typedef struct Stack
{
STDataType* a;//順序表陣列
int top;//這里記錄堆疊頂
int capacity;//這里記錄陣列容量
}ST;
堆疊的初始化
剛開始，陣列還沒有開辟，就為NULL，capacity為0
top為0或-1都可以
為0的情況：始終指向堆疊頂的下一個元素
為-1的情況：始終指向堆疊頂
圖示
void StackInit(ST* ps)
{
assert(ps);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
作者使用top=0的方式初始化
堆疊的插入
我們在這里直接選擇在尾部進行插入，與順序表的插入方式一樣，這里不再闡述
void StackPush(ST* ps, STDataType x)
{
assert(ps);
if (ps->top == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = realloc(ps->a, sizeof(STDataType) * newcapacity);
if (!tmp)
{
printf("malloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}//以上是檢查增容
ps->a[ps->top] = x;
ps->top++;//增加元素
}
堆疊的彈出
同樣與順序表的尾刪方式一樣
但是我們要檢查，如果top=0了，就代表洗掉完了，就不能再洗掉了
void StackPop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
ps->top--;
}
回傳堆疊頂元素
因為初始化的是top=0，所以我們訪問時要把top減一，才能訪問到堆疊頂
STDataType StackTop(ST* ps)
{
assert(ps);
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
堆疊判空
我們同樣使用top來判斷，如果top=0，就代表為空
我們為了簡化代碼，可以直接使用條件運算式來判斷
bool StackEmpty(ST* ps)
{
assert(ps);
return ps->top == 0;
}
堆疊銷毀
void StackDestory(ST* ps)
{
assert(ps);
free(ps->a);
ps->a = NULL;
ps->top = ps->capacity = 0;
}
使用示例
由于堆疊的特性，我們不能直接遍歷這個順序表，只能訪問堆疊頂的元素，然后再彈出，再訪問下一個元素，以此類推，直到堆疊為空
void STTest()
{
ST st;
StackInit(&st);//定義堆疊并將其初始化
StackPush(&st, 1);
StackPush(&st, 2);
StackPush(&st, 3);
StackPush(&st, 4);
StackPush(&st, 5);
//插入元素
while (!StackEmpty(&st))//如果堆疊不為空，繼續訪問
{
printf("%d ", StackTop(&st));//訪問堆疊頂元素
StackPop(&st);//訪問完后彈出，方便訪問下一個元素
}
StackDestory(&st);//使用完后將堆疊銷毀
}
運行截圖
后記
其實堆疊的實作真的不難，難的是關于堆疊的oj題！
不過沒關系，作者后續的力扣每日一題會與這篇文章夢幻聯動的，所以不妨訂閱一波哦！
力扣每日一題專欄
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/341885.html
標籤：其他