棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧棧
大家好，我是沉默王二。
今天周一，又是 3 月份的第一天，所以今天必須來點(diǎn)硬核的內(nèi)容。
上次給大家圖解了霍夫曼編碼，有同學(xué)說每天早上都會(huì)看一篇二哥的文章，但因?yàn)檫@一篇星標(biāo)了；還有做律師的同學(xué)亂入，表示雖然看不懂，但感覺很厲害；當(dāng)然了，更多的同學(xué)對(duì)文中提到的知識(shí)點(diǎn)進(jìn)行了思考，有些得出了自己的結(jié)論，有些沒有，但不管有沒有結(jié)論，重要的是主動(dòng)去思考，也只有這樣，才能收獲更多！
還有很多同學(xué)直呼內(nèi)行，強(qiáng)烈要求我多更一些這方面的文章，于是就有了今天這篇——棧（stack）。有些地方喜歡稱呼它為堆棧，我就很不喜歡，很容易和 heap（堆）搞混，尤其是對(duì)于新手來說，簡直就是虐心。
棧是一種非常有用的數(shù)據(jù)結(jié)構(gòu)，它就像一摞盤子，第一個(gè)放在最下面，第二個(gè)放在第一個(gè)上面，第三個(gè)放在第二個(gè)上面，最后一個(gè)放在最上面。
對(duì)于這一摞盤子，我們可以做兩件事情：
在最上面放一個(gè)新盤子 把頂部的盤子拿走
這兩件事情做起來很容易，但如果從中間或者底部抽出來一個(gè)盤子，就很難辦到。如果我們想要拿到最下面的盤子，就必須把它上面的所有盤子都拿走，像這樣的一個(gè)操作，我們稱之為后進(jìn)先出，也就是“Last In First Out”（簡稱LIFO）——最后的一個(gè)進(jìn)的，最先出去。
對(duì)于棧這樣一個(gè)數(shù)據(jù)結(jié)構(gòu)來說，它有兩個(gè)常見的動(dòng)作：
push，中文釋義有很多種，我個(gè)人更喜歡叫它“壓入”，非常形象。當(dāng)我們要把一個(gè)元素放入棧的頂部，這個(gè)動(dòng)作就叫做push。pop，同樣的，我個(gè)人更喜歡叫它“彈出”，帶有很強(qiáng)烈的動(dòng)畫效果，有沒有？當(dāng)我們要從棧中移除一個(gè)元素時(shí)，這個(gè)動(dòng)作就叫做pop。
對(duì)于上面這幅圖來說，3 這個(gè)元素最先放進(jìn)去，卻是最先被移除的——遵循 LIFO 的原則。
明白了棧的基本操作后，我們需要去深入地思考一下，棧是如何工作的。換句話說，為了使棧這個(gè)數(shù)據(jù)結(jié)構(gòu)按照棧的方式去工作，它需要什么？
1）棧需要有一個(gè)指針，我們稱之為 TOP，用它來指向棧中最頂部的那個(gè)元素。
2）當(dāng)我們初始化一個(gè)棧的時(shí)候，我們把 TOP 的值設(shè)置為 -1，這樣我們就可以通過 TOP == -1 來判斷棧是否為空。
3）當(dāng)我們要在棧中壓入一個(gè)元素的時(shí)候，我們把 TOP 的值加 1，然后把新壓入的元素指向 TOP。
4）當(dāng)我們要從棧中彈出一個(gè)元素的時(shí)候，我們把 TOP 的值減 1，然后把保持在最頂部的那個(gè)元素指向 TOP。
5）當(dāng)我們壓入一個(gè)元素的時(shí)候，需要檢查棧是否已經(jīng)滿了。也就是說，需要有一個(gè) isFull() 的方法來判斷。
6）當(dāng)我們要彈出一個(gè)元素的時(shí)候，需要檢查棧是否已經(jīng)空了。也就是說，需要有一個(gè) isEmpty() 的方法來判斷。
空棧的時(shí)候，TOP 等于 -1；把元素 1 壓入棧中的時(shí)候，stack[0] 為 1，TOP 加 1 變?yōu)?0；把元素 2 壓入棧中的時(shí)候，stack[1] 為 2，TOP 加 1 變?yōu)?1；把元素 3 壓入棧中的時(shí)候，stack[2] 為 3，TOP 加 1 變?yōu)?2；把元素 3 從棧中彈出后，返回元素 stack[2]，TOP 減 1 變?yōu)?1。
假設(shè)棧中的元素是 int 類型，我們可以用 Java 語言來自定義一個(gè)最簡單的棧。它需要 3 個(gè)字段：
int arr[]，一個(gè) int 類型的數(shù)組，來存放數(shù)據(jù)int top，一個(gè) int 類型的標(biāo)記int capacity，一個(gè) int 類型的容量
class Stack {
private int arr[];
private int top;
private int capacity;
}
初始化棧：
Stack(int size) {
arr = new int[size];
capacity = size;
top = -1;
}
往棧中壓入元素：
public void push(int x) {
if (isFull()) {
System.out.println("溢出\n程序終止\n");
System.exit(1);
}
System.out.println("壓入 " + x);
arr[++top] = x;
}
從棧中彈出元素：
public int pop() {
if (isEmpty()) {
System.out.println("棧是空的");
System.exit(1);
}
return arr[top--];
}
返回棧的大小：
public int size() {
return top + 1;
}
檢查棧是否為空：
public Boolean isEmpty() {
return top == -1;
}
檢查棧是否已經(jīng)滿了：
public Boolean isFull() {
return top == capacity - 1;
}
來個(gè) main() 方法直接測試下：
public void printStack() {
for (int i = 0; i <= top; i++) {
System.out.println(arr[i]);
}
}
public static void main(String[] args) {
Stack stack = new Stack(5);
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.pop();
System.out.println("\n彈出元素后");
stack.printStack();
}
打印結(jié)果如下所示：
壓入 1
壓入 2
壓入 3
壓入 4
彈出元素后
1
2
3
由于我們是通過數(shù)組來實(shí)現(xiàn)的棧，所以 push 和 pop 的時(shí)間復(fù)雜度就是 O(1)。
盡管棧是一種非常簡單的數(shù)據(jù)結(jié)構(gòu)，通過上面的代碼大家應(yīng)該也能感受得出來，輕而易舉地就實(shí)現(xiàn)了，但是棧卻是一種非常強(qiáng)有力的數(shù)據(jù)結(jié)構(gòu)，可以在很多場景中使用，比如說：
1）反轉(zhuǎn)一串字符：由于棧是 LIFO 的，所以反轉(zhuǎn)一串字符很容易，按照正常的順序把字符壓入棧中，然后再彈出來就行了。
2）用于計(jì)算器：記得我實(shí)習(xí)的時(shí)候，公司就給我們新人安排了我們一個(gè)小項(xiàng)目——模仿一個(gè) Win 7 的計(jì)算機(jī)，用來考察我們是不是真材實(shí)料，要想計(jì)算一個(gè)復(fù)雜的表達(dá)式，比如說 2 + 5 / 3 * (6 - 2)，就需要一個(gè)棧來容納這些數(shù)字和運(yùn)算符，然后按照優(yōu)先級(jí)彈出后進(jìn)行計(jì)算。
嗯，這個(gè)計(jì)算要比想象中復(fù)雜一些，新手同學(xué)可以私底下實(shí)現(xiàn)一下，不僅能夠提高對(duì)棧這種數(shù)據(jù)結(jié)構(gòu)的理解，還能對(duì)運(yùn)算符的一個(gè)優(yōu)先級(jí)進(jìn)行思考。
很顯然，棧，給我贏得了一次實(shí)習(xí)的機(jī)會(huì)，避免了被刷下去的危機(jī)。
3）用于瀏覽器：瀏覽器的后退按鈕會(huì)把我們?cè)L問的 URL 壓入一個(gè)棧中，每次我們?cè)L問一個(gè)新的頁面，新的 URL 就壓入了棧的頂部，當(dāng)我們點(diǎn)了后退按鈕，最新的那個(gè) URL 就從棧中移除，之前的那個(gè) URL 就被訪問到了。
好了，下課，今天的棧就到此為止吧。
多 BB 一句。上次，很多好心的同學(xué)為了使我吃上香噴噴的辣條，硬是不想學(xué)會(huì)霍夫曼編碼，結(jié)果我真吃了——結(jié)果的結(jié)果——臉上長痘痘了，我想說的是，同學(xué)，能不能不要這么貼心，這次學(xué)會(huì)學(xué)不會(huì)我都不吃了，哼。