目錄:
一、棧的概念
二、棧的實現
1.棧的初始化
2.棧的銷毀
3.入棧
4.出棧
5.獲取棧頂數據
6.判斷棧是否為空
7.獲取棧的個數
三、代碼
一、棧的概念
棧是一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。
進行數據插入和刪除操作的一端
稱為棧頂，另一端稱為棧底。棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧。出數據也在棧頂。
例：比如手槍彈夾，先壓進去的子彈往往是后發射出去，也就是遵循后進先出的原則。
首先來創建一個結構體，我們是基于數組實現的棧，一個棧首先要有數組存放數據，給一個top表示個數，給一個capacity表示空間大小：
typedef int stacktype;
typedef struct Stack
{stacktype* a;//動態數組int top; //個數int capacity;//空間
}ST;二、棧的實現
1.棧的初始化
一開始，數組為空，并且top和capacity都為0，這里的top有兩種初始化方法，如果我們想讓他指向棧中的最后一個數據，那么它的值就不能是數組的起始下標0，而應該給一個無關的數，比如-1；第二種就是top表示棧頂數據的下一個位置，那我們就可以給他賦值0，這里我們使用第二種方法：
void STInit(ST* pst)//初始化
{assert(pst);pst->a = NULL;pst->top = 0;//基于size指向的是棧頂數據的下一個位置pst->capacity = 0;
}2.棧的銷毀
刪除也是很簡單，原理和順序表都差不多：
void STDestroy(ST* pst)//銷毀
{assert(pst);free(pst->a);//free掉pst->a = NULL;//置為空，防止變成野指針pst->top = 0;pst->capacity = 0;
}3.入棧
首先要明白，棧是棧頂入，棧頂出，所以所有數據都從棧頂進入，也就是top的位置，隨后top++就可以，擴容和順序表一樣，詳情可以參考：https://blog.csdn.net/xpcxpt/article/details/147466492?spm=1001.2014.3001.5501
總體代碼如下：
void STPush(ST* pst, stacktype x)//插入 入棧
{assert(pst);//擴容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;stacktype* tmp = (stacktype*)realloc(pst->a, newcapacity * sizeof(stacktype));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}4.出棧
出棧也就是刪除一個棧頂的數據，那只需要讓top--就可以了：
void STPop(ST* pst)//刪除 出棧
{assert(pst);assert(pst->top > 0);//top是非負數pst->top--;//刪除一個
}5.獲取棧頂數據
top的位置的棧頂數據的下一個位置，所以要想獲取棧頂元素，就要獲取top-1位置的元素:
stacktype STTop(ST* pst)//獲取棧頂數據
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}6.判斷棧是否為空
直接判斷棧中數據數量top是否為空，這里可以使用bool類型，不為空返回true，為空返回fulse：
?
bool STEmpty(ST* pst)//判斷棧是否為空
{assert(pst);return pst->top == 0;
}7.獲取棧的個數
這里也是非常簡單，就是獲取top的大小，幾行代碼就搞定了：
int STSize(ST* pst)//判斷棧的數據個數
{assert(pst);return pst->top;//從0開始的，所以返回size的大小-1,也就是下表從0-top-1，一共top個
}三、代碼
總體代碼如下:
test.c:
#include "stack.h"int main()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);//printf("%d ", STTop(&s));STPush(&s, 3);STPush(&s, 4);while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}STDestroy(&s);
}
stack.h:
?
#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>typedef int stacktype;
typedef struct Stack
{stacktype* a;//動態數組int top; //個數int capacity;//空間
}ST;void STInit(ST* pst);//初始化
void STDestroy(ST* pst);//銷毀
void STPush(ST* pst, stacktype x);//插入 入棧
void STPop(ST* pst);//刪除 出棧
stacktype STTop(ST* pst);//獲取棧頂數據
bool STEmpty(ST* pst);//判斷棧是否為空
int STSize(ST* pst);//判斷棧的數據個數stack.c:
?
#include "stack.h"void STInit(ST* pst)//初始化
{assert(pst);pst->a = NULL;pst->top = 0;//基于size指向的是棧頂數據的下一個位置pst->capacity = 0;
}void STDestroy(ST* pst)//銷毀
{assert(pst);free(pst->a);//free掉pst->a = NULL;//置為空，防止變成野指針pst->top = 0;pst->capacity = 0;
}void STPush(ST* pst, stacktype x)//插入 入棧
{assert(pst);//擴容if (pst->top == pst->capacity){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;stacktype* tmp = (stacktype*)realloc(pst->a, newcapacity * sizeof(stacktype));if (tmp == NULL){perror("realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}pst->a[pst->top] = x;pst->top++;
}
void STPop(ST* pst)//刪除 出棧
{assert(pst);assert(pst->top > 0);//top是非負數pst->top--;//刪除一個
}
stacktype STTop(ST* pst)//獲取棧頂數據
{assert(pst);assert(pst->top > 0);return pst->a[pst->top - 1];
}
bool STEmpty(ST* pst)//判斷棧是否為空
{assert(pst);return pst->top == 0;
}
int STSize(ST* pst)//判斷棧的數據個數
{assert(pst);return pst->top;//從0開始的，所以返回size的大小-1,也就是下表從0-top-1，一共top個
}
