一局雄、什么是棧？
1.后進(jìn)者先出存炮，先進(jìn)者后出炬搭，這就是典型的“棧”結(jié)構(gòu)穆桂。
2.從棧的操作特性來看宫盔，是一種“操作受限”的線性表，只允許在端插入和刪除數(shù)據(jù)享完。
二灼芭、為什么需要棧？
1.棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu)般又，其操作特性用數(shù)組和鏈表均可實(shí)現(xiàn)彼绷。
2.但，任何數(shù)據(jù)結(jié)構(gòu)都是對(duì)特定應(yīng)用場(chǎng)景的抽象茴迁，數(shù)組和鏈表雖然使用起來更加靈活寄悯，但卻暴露了幾乎所有的操作，難免會(huì)引發(fā)錯(cuò)誤操作的風(fēng)險(xiǎn)堕义。
3.所以猜旬，當(dāng)某個(gè)數(shù)據(jù)集合只涉及在某端插入和刪除數(shù)據(jù)，且滿足后進(jìn)者先出胳螟，先進(jìn)者后出的操作特性時(shí)昔馋，我們應(yīng)該首選棧這種數(shù)據(jù)結(jié)構(gòu)。
三糖耸、如何實(shí)現(xiàn)棧？
1.棧的API
public class Stack<Item> {
//壓棧
public void push(Item item){}
//彈棧
public Item pop(){}
//是否為空
public boolean isEmpty(){}
//棧中數(shù)據(jù)的數(shù)量
public int size(){}
//返回棧中最近添加的元素而不刪除它
public Item peek(){}
}
2.數(shù)組實(shí)現(xiàn)（自動(dòng)擴(kuò)容）
時(shí)間復(fù)雜度分析：根據(jù)均攤復(fù)雜度的定義丘薛，可以得數(shù)組實(shí)現(xiàn)（自動(dòng)擴(kuò)容）符合大多數(shù)情況是O(1)級(jí)別復(fù)雜度嘉竟，個(gè)別情況是O(n)級(jí)別復(fù)雜度，比如自動(dòng)擴(kuò)容時(shí)洋侨，會(huì)進(jìn)行完整數(shù)據(jù)的拷貝舍扰。
空間復(fù)雜度分析：在入棧和出棧的過程中，只需要一兩個(gè)臨時(shí)變量存儲(chǔ)空間希坚，所以O(shè)(1)級(jí)別边苹。我們說空間復(fù)雜度的時(shí)候，是指除了原本的數(shù)據(jù)存儲(chǔ)空間外裁僧，算法運(yùn)行還需要額外的存儲(chǔ)空間个束。
實(shí)現(xiàn)代碼：（棧的數(shù)組實(shí)現(xiàn)）
public class StackOfArray<Item> implements Iterable<Item>{
//存儲(chǔ)數(shù)據(jù)的數(shù)組
Item[] a = (Item[])new Object[1];
//記錄元素個(gè)數(shù)N
int N = 0;
//構(gòu)造器
public StackOfArray(){}
//添加元素
public void push(Item item){
//自動(dòng)擴(kuò)容
if (N == a.length ) resize(2*a.length );
a[N++] = item;
}
//刪除元素
public Item pop(){
Item item = a[--N];
a[N] = null;
if (N > 0 && N == a.length / 4) resize(a.length / 2);
return item;
}
//是否為空
public boolean isEmpty(){
return N == 0;
}
//元素個(gè)數(shù)
public int size(){
return N;
}
//改變數(shù)組容量
private void resize(int length) {
Item[] temp = (Item[])new Object[length];
for (int i = 0; i < N; i++) {
temp[i] = a[i];
}
a = temp;
}
//返回棧中最近添加的元素而不刪除它
public Item peek(){
return a[N-1];
}
@Override
public Iterator<Item> iterator() {
return new ArrayIterator();
}
//內(nèi)部類
class ArrayIterator implements Iterator{
//控制迭代數(shù)量
int i = N;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return a[--i];
}
}
}
3.鏈表實(shí)現(xiàn)
時(shí)間復(fù)雜度分析：壓棧和彈棧的時(shí)間復(fù)雜度均為O(1)級(jí)別慕购，因?yàn)橹恍韪膯蝹€(gè)節(jié)點(diǎn)的索引即可。
空間復(fù)雜度分析：在入棧和出棧的過程中茬底，只需要一兩個(gè)臨時(shí)變量存儲(chǔ)空間沪悲，所以O(shè)(1)級(jí)別。我們說空間復(fù)雜度的時(shí)候阱表，是指除了原本的數(shù)據(jù)存儲(chǔ)空間外殿如，算法運(yùn)行還需要額外的存儲(chǔ)空間。
實(shí)現(xiàn)代碼:
public class StackOfLinked<Item> implements Iterable<Item> {
//定義一個(gè)內(nèi)部類最爬，就可以直接使用類型參數(shù)
private class Node{
Item item;
Node next;
}
private Node first;
private int N;
//構(gòu)造器
public StackOfLinked(){}
//添加
public void push(Item item){
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
N++;
}
//刪除
public Item pop(){
Item item = first.item;
first = first.next;
N--;
return item;
}
//是否為空
public boolean isEmpty(){
return N == 0;
}
//元素?cái)?shù)量
public int size(){
return N;
}
//返回棧中最近添加的元素而不刪除它
public Item peek(){
return first.item;
}
@Override
public Iterator<Item> iterator() {
return new LinkedIterator();
}
//內(nèi)部類：迭代器
class LinkedIterator implements Iterator{
int i = N;
Node t = first;
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
Item item = (Item) t.item;
t = t.next;
i--;
return item;
}?
}
}
四涉馁、棧的應(yīng)用
1.棧在函數(shù)調(diào)用中的應(yīng)用
操作系統(tǒng)給每個(gè)線程分配了一塊獨(dú)立的內(nèi)存空間，這塊內(nèi)存被組織成“棸拢”這種結(jié)構(gòu)烤送，用來存儲(chǔ)函數(shù)調(diào)用時(shí)的臨時(shí)變量。每進(jìn)入一個(gè)函數(shù)蒜鸡，就會(huì)將其中的臨時(shí)變量作為棧幀入棧胯努，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后逢防，將這個(gè)函數(shù)對(duì)應(yīng)的棧幀出棧叶沛。
2.棧在表達(dá)式求值中的應(yīng)用（比如：34+13*9+44-12/3）
利用兩個(gè)棧，其中一個(gè)用來保存操作數(shù)忘朝，另一個(gè)用來保存運(yùn)算符灰署。我們從左向右遍歷表達(dá)式，當(dāng)遇到數(shù)字局嘁，我們就直接壓入操作數(shù)棧溉箕；當(dāng)遇到運(yùn)算符，就與運(yùn)算符棧的棧頂元素進(jìn)行比較悦昵，若比運(yùn)算符棧頂元素優(yōu)先級(jí)高肴茄，就將當(dāng)前運(yùn)算符壓入棧，若比運(yùn)算符棧頂元素的優(yōu)先級(jí)低或者相同但指，從運(yùn)算符棧中取出棧頂運(yùn)算符寡痰，從操作數(shù)棧頂取出2個(gè)操作數(shù)，然后進(jìn)行計(jì)算棋凳，把計(jì)算完的結(jié)果壓入操作數(shù)棧拦坠，繼續(xù)比較。
3.棧在括號(hào)匹配中的應(yīng)用（比如：{}{[()]()}）
用棧保存為匹配的左括號(hào)剩岳，從左到右一次掃描字符串贞滨，當(dāng)掃描到左括號(hào)時(shí)，則將其壓入棧中拍棕；當(dāng)掃描到右括號(hào)時(shí)晓铆，從棧頂取出一個(gè)左括號(hào)勺良，如果能匹配上，則繼續(xù)掃描剩下的字符串尤蒿。如果掃描過程中郑气，遇到不能配對(duì)的右括號(hào)，或者棧中沒有數(shù)據(jù)腰池，則說明為非法格式尾组。
當(dāng)所有的括號(hào)都掃描完成之后，如果棧為空示弓，則說明字符串為合法格式讳侨；否則，說明未匹配的左括號(hào)為非法格式奏属。
4.如何實(shí)現(xiàn)瀏覽器的前進(jìn)后退功能跨跨？
我們使用兩個(gè)棧X和Y，我們把首次瀏覽的頁面依次壓如棧X囱皿，當(dāng)點(diǎn)擊后退按鈕時(shí)勇婴，再依次從棧X中出棧，并將出棧的數(shù)據(jù)一次放入Y棧嘱腥。當(dāng)點(diǎn)擊前進(jìn)按鈕時(shí)耕渴，我們依次從棧Y中取出數(shù)據(jù)，放入棧X中齿兔。當(dāng)棧X中沒有數(shù)據(jù)時(shí)橱脸，說明沒有頁面可以繼續(xù)后退瀏覽了。當(dāng)Y棧沒有數(shù)據(jù)分苇，那就說明沒有頁面可以點(diǎn)擊前進(jìn)瀏覽了添诉。
五、思考
1. 我們?cè)谥v棧的應(yīng)用時(shí)医寿，講到用函數(shù)調(diào)用棧來保存臨時(shí)變量栏赴，為什么函數(shù)調(diào)用要用“棧”來保存臨時(shí)變量呢靖秩？用其他數(shù)據(jù)結(jié)構(gòu)不行嗎艾帐？
答：因?yàn)楹瘮?shù)調(diào)用的執(zhí)行順序符合后進(jìn)者先出，先進(jìn)者后出的特點(diǎn)盆偿。比如函數(shù)中的局部變量的生命周期的長(zhǎng)短是先定義的生命周期長(zhǎng)，后定義的生命周期短准浴；還有函數(shù)中調(diào)用函數(shù)也是這樣事扭，先開始執(zhí)行的函數(shù)只有等到內(nèi)部調(diào)用的其他函數(shù)執(zhí)行完畢，該函數(shù)才能執(zhí)行結(jié)束乐横。
正是由于函數(shù)調(diào)用的這些特點(diǎn)求橄，根據(jù)數(shù)據(jù)結(jié)構(gòu)是特定應(yīng)用場(chǎng)景的抽象的原則今野，我們優(yōu)先考慮棧結(jié)構(gòu)。
2.我們都知道罐农，JVM 內(nèi)存管理中有個(gè)“堆椞跛”的概念。棧內(nèi)存用來存儲(chǔ)局部變量和方法調(diào)用涵亏，堆內(nèi)存用來存儲(chǔ) Java 中的對(duì)象宰睡。那 JVM 里面的“棧”跟我們這里說的“椘睿”是不是一回事呢拆内？如果不是，那它為什么又叫作“棾枘”呢麸恍？
答：JVM里面的棧和我們這里說的是一回事，被稱為方法棧搀矫。和前面函數(shù)調(diào)用的作用是一致的抹沪，用來存儲(chǔ)方法中的局部變量。
