（總結源自《大話資料結構》和極客時間“資料結構與算法之美”專欄，初學資料結構推薦此書，進階學習推薦該專欄）
目錄
棧
棧的順序存儲結構（JAVA語言實作）
入棧操作
出棧操作
棧的鍊式存儲結構（C語言實作）
入棧操作
出棧操作
兩棧共享空間
棧
棧（stack）是限定僅在表尾進行插入和删除操作的線性表
我們把允許插入和删除的一端稱為棧頂（top），另一端稱為棧底（bottom），不含任何資料元素的棧稱為空棧。
棧又稱為後進先出（Last In First Out）的線性表，簡稱LIFO結構。
也就是說“棧”是一個有限制條件的線性表，那為什麼我們不直接用數組和連結清單，而用這個功能更加受限制的資料結構呢？
當某個資料集合隻涉及在⼀端插⼊和删除資料，并且滿⾜後進先出、先進後出的特性，我們就應該⾸選“棧”這種資料結構。
出棧隻能是棧頂元素。
棧的順序存儲結構（JAVA語言實作）
既然棧隻能由一端進行插入和删除，那麼用哪一段呢？
下标為0的一端作為棧底比較好，因為首元素都存在棧底，變化最小，是以它作棧底。
// 基于數組實作的順序棧
public class ArrayStack {
private String[] items; //數組
private int count; //棧中元素個數
private int n; //棧的⼤⼩
// 初始化數組，申請⼀個⼤⼩為n的數組空間
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
//入棧操作
public boolean push(String item) {下面再寫}
//出棧操作
public String pop() {下面在寫}
} 入棧操作
進棧操作的思想就是：①将item放到下标為count的位置，②count++,指向下一個可用放入元素的位置。
// ⼊棧操作
public boolean push(String item){
//數組空間不夠了，直接傳回false，⼊棧失敗。
if(count==n) return false;
//将item放到下标為count的位置，并且count加⼀
items[count]=item;
++count;
return true;
} 出棧操作
出棧操作的思想很簡單：count--即可。因為再出棧的話，再取出資料以後往下減即可，而入棧的時候，會覆寫掉之前的資料。
//出棧操作
public String pop() {
//棧為空，則直接傳回null
if (count == 0)
return null;
//傳回下标為count-1的數組元素，并且棧中元素個數count減⼀
String tmp = items[count-1];
--count;
return tmp;
} 動态擴容的順序棧：即底層采用了一個動态擴容的數組：入棧時，若數組空間不夠，我們就重新申請⼀塊更⼤的記憶體，将原來數組中資料統統拷⻉過去。由于動态擴容這個動作不時常發生，均攤了時間成本。故時間複雜度不變，為O（1）。
棧的鍊式存儲結構（C語言實作）
我們把棧頂放在單連結清單的頭部，删去頭結點，因為棧的鍊式結構中不需要頭結點，沒有意義。
//鍊棧結構代碼如下
typedef struct StackNode
{
SElemType data;
struct StackNode *next;
}StackNode,*LinkStackPtr;
typedef struct LinkStack
{
LinkStackPtr top;
int count;
}LinkStack; 入棧操作
入棧的思路：既然棧頂指針代替了頭結點，那麼棧頂指針肯定是要發揮作用的。
開辟一個新的結點，資料域放新的資料元素，再讓它的next指向現在的棧頂指針所指的元素，随後再讓棧頂指針指向新結點即可。
Status Push(LinkStack *s,SElemType e)
{
LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode));
s->data=e;
s->next=S->top;
S->top=s;
S->count++;
return OK;
} 出棧操作
出棧思路：用一個變量p指向棧頂空間，棧頂指針下移，free掉p
//若棧不空，則删除S的棧頂元素，用e傳回其值，并傳回OK，否則傳回ERROR
Status Pop(LinkStack *S,SElemType *e)
{
LinkStackPtr P;
if(StackEmpty(*S))
return ERROR;
*e=S->top->data;
p=S->top;
S->top=S->top->next;
free(p);
S->count--;
return OK;
} 順序棧與鍊棧的進棧和出棧都是O（1）的時間複雜度，O(1)的空間複雜度。【有人可能會問：這不是用到了記憶體空間麼，怎麼會是O（1）的空間複雜度呢？ 我們說空間複雜度，是指除了原本的資料存儲空間外，算法運⾏還需要額外的存儲空間。而這裡的數組也好，連結清單也好，所占空間都是必須的，是以不能算進空間複雜度裡去。】
而順序棧長度固定，鍊棧有指針域，二者都存在記憶體空間浪費問題。
若棧的使用過程中，元素變化不可預料，時大時小，最好用鍊棧，若變化在可控範圍内，建議用順序棧。
兩棧共享空間
棧很友善，因為不存線上性表的插入和删除時需要移動元素的問題。但它同樣有缺陷，因為必須事先确定數組存儲空間的大小。對于兩個相同類型的棧，我們可以最大限度的利用開辟的存儲空間，怎麼用呢？就是我們的兩棧共享！
怎麼個共享法呢？共享共享，一定是多個對象共同使用同一個對象。我們知道，數組有兩端，而棧隻有一個棧底，那麼能不能兩端各安一個棧底，往數組之間延伸呢？這就是我們的兩棧共享。
typedef struct
{
SElemType data[MAXSIZE];
int top1; //棧1的棧頂指針
int top2; //棧2的棧頂指針
}SqDoubleStack;
ok,現在兩個棧共享一個數組空間，那插入的時候如何知道插入到哪個棧呢？是以我們需要有個小東西來執行一個職能：插入之前告訴我，你這個元素要插入到哪個棧，即stackNumber
//插入操作
Status Push(SqDoubleStack *s,SElemType e,int stackNumber)
{
if(S->top1+1==S->top2)
return ERROR; //此時棧滿
if(stackNumber==1)
S->data[++S->top1]=e; //往top1+1位置處插入元素
else if(stackNumber==2)
S->data[--S->top2]=e; //往top2-1位置處插入元素
return OK;
} //删除操作
//若棧不空，删除S的棧頂元素，用e傳回其值，并傳回OK，否則傳回ERROR
Status Pop(SqDoubleStack *S, SElemType *e,int stackNumber)
{
if(stackNumber==1)
{
if(S->top1 ==-1)
retrun ERROR;
*e=S->data[S->top1--];
}
if(stackNumber==2)
{
if(S->top2 ==MAXSIZE)
retrun ERROR;
*e=S->data[S->top2++];
}
return OK;
} 那麼有個問題來了：共享歸共享，它還是在數組裡面，數組還是固定大小的呀，那有什麼用呢？是以呀，這種資料結構一般用于兩個棧的空間需求有相反關系時，即一個增長時另一個在縮短，若兩個都在不停增長，那很快就會因為棧滿而溢出。