棧
什么是棧？棧是一種特殊的線性表，它只能在在表尾進行插入和刪除操作。
棧的底部稱為棧底，頂部稱為棧頂，所有的操作只能在棧頂進行，也就是說，被壓在下方的元素，只能等待其上方的元素出棧之后才能取出，就像我們往箱子里里面放的書一樣，因為只有一個口取出里面的物品，所以被壓在下面的書只能等上面的書被拿出來之后才能取出，這就是棧的思想，它是一種先進后出的數據結構。
使用C語言實現棧
一般使用棧這樣的機構，常用的兩個操作就是入棧和出棧
pop：出棧操作，將棧頂的元素取出，并刪除push：入棧操作，將新元素置入棧頂
定義數據結構
我們在棧的底層使用數組進行存儲，所以結構中將儲存一個數組的指針，和數組的容量（方便初始化和申請內存）；另外棧只能操作棧頂的元素，所以結構中還存著一個變量top，表示棧頂的元素。
typedef int E;struct Stack
{E * array; // 一個數組的指針int capacity; // 數組的容量int top; // 棧頂的元素
};typedef struct Stack * stack;
再給棧結構的指針起一個別名，便于后續對棧進行操作。
定義初始化方法
接著我們定義一個初始化棧的方法,在初始化方法中，我們默認初始化時，底層數組的最大容量是10個內存單位，也就是40字節（因為E是int類型），接著我們定義，剛初始化完棧之后是一個空棧，則棧頂的指針默認為-1。
top變量是為后續的入棧出棧操作做鋪墊的，它可以當作數組的索引，也可以用來當作是否是空棧的標識。
int initStack(stack stack)
{stack->array = malloc(sizeof(E) * 10); // 申請一個40字節的內存if (stack->array == NULL) return 0;stack->capacity = 10; // 記錄底層數組的容量stack->top = -1; // 棧沒有元素默認為-1return 1;
}
在main函數中，實例化一個Stack類型，接著使用initStack函數就完成了棧的初始化：
int main()
{struct Stack stack;initStack(&stack);return 0;
}
實現入棧操作
入棧操作，就是把一個元素放到棧的最上方，也就是棧頂上，所以實現該操作的函數只需要有兩個參數就可以了：
- 棧的指針
- 需要入棧的元素
另外，底層數組的默認容量是10，如果入棧超過10個元素的話，內存就會造成泄露，所以對底層數組進行擴容操作也是必不可少的。
int pushStack(stack stack,E element)
{if (stack->top == stack->capacity - 1) // 擴容{int newCapacity = stack->capacity * 2;E* newArray = realloc(stack->array,newCapacity * sizeof(E));if (newArray == NULL) return 0;stack->array = newArray;stack->capacity = newCapacity;}stack->top++;stack->array[stack->top] = element;return 1;
}
在擴容操作中，我們使用realloc函數將原數組拷貝到一個新的大小的內存中，這個內存地址我們使用newArray來接收，最后將原棧中的array指向newArray,將原棧中的capacity 指向newCapacity。
簡單編寫一個打印棧元素的函數，用于測試棧：
void printStack(stack stack)
{printf("|");for (int i = 0;i<=stack->top;i++){printf("%d, ",stack->array[i]);}printf("\n");
}int main()
{struct Stack stack;initStack(&stack);for(int i = 1;i<=10;i++){pushStack(&stack,i);}printStack(&stack);return 0;
}
控制臺輸出：
|1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
入棧操作成功實現~
實現出棧操作
出棧操作就是把棧頂的元素取出，然后把top執行自減操作，如果不自減元素出棧之后棧頂的元素還會是原來的元素。
E popStack(stack stack)
{if (stack->top == -1){printf("棧為空，不能出棧\n");return -1;}E element = stack->array[stack->top];stack->top--;return element;
}
我們接著測試一下：
void printStack(stack stack)
{printf("|");for (int i = 0;i<=stack->top;i++){printf("%d, ",stack->array[i]);}printf("\n");
}int main()
{struct Stack stack;initStack(&stack);for(int i = 1;i<=20;i++){pushStack(&stack,i);}printStack(&stack);printf("出棧的元素順序：");while (1){printf("%d, ",stack.array[stack.top]);popStack(&stack);if (stack.top == -1) break;}return 0;
}
會發現控制臺輸出的信息為：
|1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
出棧的元素順序：20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
出棧的順序是從20到1的，說明元素是從棧頂依次出去的，至此出棧操作也實現好了。
總結
使用C語言手動把棧的結構和各種操作實現一遍是很重要的，它能夠加深學習者對計算機底層的認識，也能夠為后續的算法題的解題提供一種新的思路。
本篇博文所有代碼：
#include "stdio.h"
#include "stdlib.h"typedef int E;struct Stack
{E * array; // 一個數組的指針int capacity; // 數組的容量int top; // 棧頂的元素
};typedef struct Stack * stack;int initStack(stack stack)
{stack->array = malloc(sizeof(E) * 10); // 申請一個40字節的內存if (stack->array == NULL) return 0;stack->capacity = 10; // 記錄底層數組的容量stack->top = -1; // 棧沒有元素默認為-1return 1;
}int pushStack(stack stack,E element)
{if (stack->top == stack->capacity - 1) // 擴容{int newCapacity = stack->capacity * 2;E* newArray = realloc(stack->array,newCapacity * sizeof(E));if (newArray == NULL) return 0;stack->array = newArray;stack->capacity = newCapacity;}stack->top++;stack->array[stack->top] = element;return 1;
}E popStack(stack stack)
{if (stack->top == -1){printf("棧為空，不能出棧\n");return -1;}E element = stack->array[stack->top];stack->top--;return element;
}void printStack(stack stack)
{printf("|");for (int i = 0;i<=stack->top;i++){printf("%d, ",stack->array[i]);}printf("\n");
}int main()
{struct Stack stack;initStack(&stack);for(int i = 1;i<=20;i++){pushStack(&stack,i);}printStack(&stack);printf("出棧的元素順序：");while (1){printf("%d, ",stack.array[stack.top]);popStack(&stack);if (stack.top == -1) break;}return 0;
}
】)
