1. 棧的概念

棧：一種特殊的線性表，其只允許在固定的一端進行插入和刪除元素操作。 進行數據插入和刪除操作的一端稱為棧頂，另一端稱為棧底。 棧中的數據元素遵守后進先出LIFO（Last In First Out）的原則。
壓棧：棧的插入操作叫做進棧/壓棧/入棧，入數據在棧頂。
出棧：棧的刪除操作叫做出棧，出數據也在棧頂。

遵循的原則是：后進先出。

2. 棧的分類

棧的實現有3種方式：

2.1 數組棧：棧底是數組頭，棧頂是數組尾。

2.2 鏈式棧：

1）雙向鏈表實現： 棧頂可以是尾也可以是頭

2）單向鏈表實現： 棧頂只能是頭（開銷小）

棧的實現一般可以使用以上方式實現，相對而言數組的結構實現更優一些。因為數組在尾上插入數據的代價比較小。

3. 棧的實現（數組棧）

下面將其分為3個模塊進行實現Stack.h，Stack.c，test.c

3.1 接口設計（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 CheckCapacity(ST* pst);
//棧頂插入刪除
void STPush(ST* pst, STDataType x);
void STPop(ST* pst);
//棧頂元素、空棧、大小
STDataType STTop(ST* pst);
bool STEmpty(ST* pst);
int STSize(ST* pst);

3.2 接口實現（Stack.c）

1）初始化銷毀

這里需要討論一些 top 的指向問題：

如果 top 指向棧頂元素位置，則初始化時 top = -1 ；這時要push時要先對 top ++后賦值。

如果 top 指向棧頂元素下一個位置，則初始化時 top == 0 ；這時要push時要先對 top 賦值后++。

這里采用第二種寫法。

void STInit(ST* pst)
{assert(pst);pst->a = NULL;pst->capacity = 0;這里初始化為-1，表示指向棧頂元素//pst->top = 0;//這里初始化為0，表示指向棧頂下一個元素pst->top = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}

2）棧頂插入刪除

刪除這里要判斷 top > 0 ，和結構定義一致

void STCheckCapacity(ST* pst)
{if (pst->capacity == pst->top){int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("relloc fail\n");exit(-1);}pst->a = tmp;pst->capacity = newCapacity;}
}void STPush(ST* pst, STDataType x)
{assert(pst);STCheckCapacity(pst);pst->a[pst->top++] = x;
}void STPop(ST* pst)
{assert(pst);//不為空assert(pst->top > 0);pst->top--;
}

3）棧頂元素、空棧、大小

在判斷空棧有個小技巧：即直接返回判斷語句即可，因為他們的結果也是對或錯

STDataType STTop(ST* pst)
{assert(pst);//不為空assert(pst->top > 0);return pst->a[pst->top - 1];
}bool STEmpty(ST* pst)
{assert(pst);1//if (pst->top == 0)//{//	return true;//}//else//{//	return false;//}2//return pst->top == 0 ? true : false;//3return pst->top == 0;
}int STSize(ST* pst)
{assert(pst);return pst->top;
}

3.3 完整代碼

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 STCheckCapacity(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)
{assert(pst);pst->a = NULL;pst->capacity = 0;這里初始化為-1，表示指向棧頂元素//pst->top = 0;//這里初始化為0，表示指向棧頂下一個元素pst->top = 0;
}void STDestroy(ST* pst)
{assert(pst);free(pst->a);pst->a = NULL;pst->top = pst->capacity = 0;
}void STCheckCapacity(ST* pst)
{if (pst->capacity == pst->top){int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDataType* tmp = (STDataType*)realloc(pst->a, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("relloc fail\n");exit(-1);}pst->a = tmp;pst->capacity = newCapacity;}
}//棧進棧出
void STPush(ST* pst, STDataType x)
{assert(pst);STCheckCapacity(pst);pst->a[pst->top++] = x;
}void STPop(ST* pst)
{assert(pst);//不為空assert(pst->top > 0);pst->top--;
}//棧頂元素、空棧、大小
STDataType STTop(ST* pst)
{assert(pst);//不為空assert(pst->top > 0);return pst->a[pst->top - 1];
}bool STEmpty(ST* pst)
{assert(pst);1//if (pst->top == 0)//{//	return true;//}//else//{//	return false;//}2//return pst->top == 0 ? true : false;//3return pst->top == 0;
}int STSize(ST* pst)
{assert(pst);return pst->top;
}

test.c

#include "Stack.h"void STTest()
{ST s;STInit(&s);STPush(&s, 1);STPush(&s, 2);STPush(&s, 3);STPush(&s, 4);STPush(&s, 5);STPush(&s, 6);STPush(&s, 7);STPush(&s, 8);STPush(&s, 9);printf("棧頂元素是 %d, 棧個數為 %d\n", STTop(&s), STSize(&s));//訪問棧只能先打印棧頂，然后出棧，然后繼續訪問//入棧順序和出棧順序是一對多的關系printf("打印棧全部元素: \n");while (!STEmpty(&s)){printf("%d ", STTop(&s));STPop(&s);}printf("\n");printf("銷毀棧\n");STDestroy(&s);
}int main()
{STTest();return 0;
}

注意：

1）訪問棧只能先打印棧頂，然后出棧，然后繼續訪問，訪問完成棧也就為空了
2）入棧順序和出棧順序是一對多的關系，判斷順序可以模擬過程就能判斷哪種順序是錯的

運行效果