1.棧的概念

是一種特殊的線性表，只允許數據在固定的一段進行插入、刪除元素的操作

• 我們把進行插入或刪除元素的一端成為棧頂，另一端成為棧底
• 棧中的元素遵循先進后出原則
• 入棧：在棧頂插入元素，又稱壓棧/進棧
• 出棧：刪除棧頂元素
  

2.棧的底層結構

思考：棧是一種線性表，只在一端進行插入或刪除操作，因此我們可以選擇用數組(順序表)或鏈表來作為它的底層結構，那么用哪個更優呢？

時間復雜度分析：
數組：相當于在末尾添加或刪除元素
入棧：O(1) 出棧：O(1)
鏈表：把表頭當作棧頂，相當于頭插或頭刪，需要從頭節點遍歷到尾節點
入棧：O(1) 出棧：O(1)
綜上，時間復雜度相等

空間復雜度分析：
數組：每次擴容需要開辟相應倍數數據類型大小的空間(每次擴容乘2)
鏈表：每添加一個元素需要開辟相應節點大小的空間
綜上，顯然數組的空間復雜度更低

因此，我們通常選擇數組來作為棧的底層結構

3.棧的功能

主要功能有：入棧、出棧、取棧頂元素、返回棧中有效元素個數

4.棧的實現

4.1.棧結構的定義

定義一個棧的結構體，其中的成員變量包含：數組(指針)、有效元素個數、數組容量

//棧的結構
typedef int STDataType;//棧中存儲的變量類型
typedef struct Stack{STDataType* a;//變長數組，存儲數據int top;//記錄有效元素個數int capacity;//數組容量
}ST;

4.2.棧的初始化

創建一個空數組

void STInit(ST* ps)
{ps->a = NULL;ps->capacity = ps->top = 0;
}

4.3.棧的銷毀

釋放棧中數組空間，把成員變量都置為空

void STDestroy(ST* ps)
{assert(ps);if(ps->a) free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

4.4.入棧

在棧頂，即數組末尾插入元素

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->a, newCapacity * sizeof(STDataType));//擴容失敗if(tmp == NULL){perror("Realloc Failed!\n");exit(1);}ps->a = tmp;ps->capacity = newCapacity;}//空間足夠ps->a[ps->top++] = x;
}

4.5.出棧

在棧頂，即數組末尾刪除元素
需要先判斷棧是否為空，寫一個判空函數：

bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

出棧的實現：

void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}

4.6.取棧頂元素

返回數組中top-1位置的元素值即可

STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->a[ps->top-1];
}

4.7.獲取棧中有效元素個數

返回top值即可

int STSize(ST* ps)
{assert(!STEmpty(ps));return ps->top;
}

5.完整代碼

Stack.h

//
//  Stack.h
#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* ps);
//銷毀
void STDestroy(ST* ps);//入棧
void STPush(ST* ps, STDataType x);//判空
bool STEmpty(ST* ps);//出棧
void STPop(ST* ps);//取棧頂元素
STDataType STTop(ST* ps);//有效元素個數
int STSize(ST* ps);

Stack.c

//
//  Stack.c
#include "Stack.h"void STInit(ST* ps)
{ps->a = NULL;ps->capacity = ps->top = 0;
}
void STDestroy(ST* ps)
{assert(ps);if(ps->a) free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}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->a, newCapacity * sizeof(STDataType));//擴容失敗if(tmp == NULL){perror("Realloc Failed!\n");exit(1);}ps->a = tmp;ps->capacity = newCapacity;}//空間足夠ps->a[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->a[ps->top-1];
}int STSize(ST* ps)
{assert(!STEmpty(ps));return ps->top;
}

main.c

//main.c
#include "Stack.h"void test(void)
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);printf("st size: %d\n", STSize(&st));while(!STEmpty(&st)){STDataType top = STTop(&st);STPop(&st);printf("%d ", top);}printf("\n");STDestroy(&st);
}
int main(void)
{test();return 0;
}

運行結果