😘個人主頁：@Cx330?
👀個人簡介：一個正在努力奮斗逆天改命的二本覺悟生
📖個人專欄：《C語言》《LeetCode刷題集》《數據結構-初階》
前言：在之前幾篇博客中，我們學習了順序表和鏈表，接下來我們將學習棧的相關知識，希望大家繼續堅持下去🌹🌹🌹
目錄
一、棧的概念與結構
二、棧的初始化和銷毀
注意事項：
三、、入棧
四、出棧
五、取棧頂元素
注意事項：
測試結果：
六、獲取棧中元素個數
七、全部代碼實現
Stack.h：
Stack.c：
test.c：
一、棧的概念與結構
棧：?種特殊的線性表，其只允許在固定的一端進行插?和刪除元素操作。進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據也在棧頂
棧戰：棧的刪除操作叫做出棧。出數據也在棧頂
例子：我們可以將棧想象為水杯，水杯的地步就是棧底，開口的地方就是棧頂，在水杯里面放石頭，直到放滿為止，先放進杯子的石頭是最后才能拿出來的。
注意：棧的實現一般可以用數組或者鏈表來實現，但是相對而言數組的結構實現更優一些，將數組的尾部作為棧頂，數組的頭部作為棧頂，插入刪除數據的時間復雜度都為O(1)，但是鏈表使用頭部也可以進行插入刪除，時間復雜度也為O(1)，但是每次插入都會申請一個節點大小的空間，在空間上相對而言，數組的結構更加優秀
棧的結構：
//定義棧的結構
typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//指向棧頂的位置--剛好就是棧中有效數據個數int capacity;//棧的空間大小
}ST;二、棧的初始化和銷毀
初始化：
//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->capacity = ps->top = 0;
}銷毀：
//銷毀
void STDesTroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}注意事項：
這里的結構和順序表幾乎是一樣的，但是為了區分size，這里我們使用top作為棧頂
三、、入棧
//入棧--棧頂
void STPush(ST* ps, STDataType x)
{assert(ps);//判斷空間是否足夠if (ps->capacity == ps->top){//增容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;
}相信大家看到這些代碼的時候并不陌生，這里的邏輯和順序表幾乎一模一樣，當在棧中插入數據時，由于棧頂插入，所以要先判斷棧的空間是否足夠，若不夠先增容，足夠的話就將x賦給ps->arr[ps->top++]就可以了
四、出棧
在出棧之前首先要判斷棧是否為空，若不為空才可以進行出棧操作，所以這里封裝一個判空的接口
//棧是否為空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;//棧頂為0，棧就為空
}出棧：
//出棧--棧頂
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}棧不為空，直接讓ps->top--就可以了，非常簡單
五、取棧頂元素
//取棧頂元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top-1];//易錯top是空的，top-1才是棧頂元素
}注意事項：
這里要注意的是，top是棧頂，而top-1才是棧頂元素
test.c:
#include"stack.h"void test1()
{ST ps;STInit(&ps);//入棧STPush(&ps, 1);STPush(&ps, 2);STPush(&ps, 3);STPush(&ps, 4);while (!STEmpty(&ps)){//取棧頂元素，打印STDataType top = STTop(&ps);printf("%d ", top);//出棧STPop(&ps);}printf("\n");//銷毀STDestory(&ps);
}int main()
{test1();
}測試結果：
六、獲取棧中元素個數
//獲取棧中有效數據個數
int STSize(ST* ps)
{assert(ps);return ps->top;
}實現起來也是非常簡單了，直接返回ps->top剛好就是有效元素個數?
七、全部代碼實現
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);
//棧是否為空
bool STEmpty(ST* ps);
//出棧--棧頂
void STPop(ST* ps);
//取棧頂元素
STDataType STTop(ST* ps);Stack.c：
#include"stack.h"
//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->capacity = ps->top = 0;
}
//銷毀
void STDesTroy(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->capacity = ps->top = 0;
}//入棧--棧頂
void STPush(ST* ps, STDataType x)
{assert(ps);//判斷空間是否足夠if (ps->capacity == ps->top){//增容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;
}//棧是否為空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出棧--棧頂
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}//取棧頂元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top-1];//易錯top是空的，top-1才是棧頂元素
}//獲取棧中有效數據個數
int STSize(ST* ps)
{assert(ps);return ps->top;
}test.c：
#include"stack.h"
void test01()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);printf("size:%d\n", STSize(&st));while (!STEmpty(&st)){//取棧頂STDataType top = STTop(&st);printf("%d ", top);//出棧STPop(&st);}printf("\n");STDesTroy(&st);
}
int main()
{test01();return 0;
}往期回顧：
【數據結構初階】--雙向鏈表（一）
【數據結構初階】--雙向鏈表（二）
總結：這篇博客帶著給大家實現了棧的全部接口了，其實可以看出來棧的結構很簡單，但是大家不能眼高手低，下去一定要自己畫圖操作，那么下篇博客將帶著大家實現隊列，大家敬請期待！如果文章對你有幫助的話，歡迎評論，點贊，收藏加關注，感謝大家的支持🌹🌹🌹
