棧（stack）又名堆棧，它是一種運算受限的線性表。其限制是僅允許在表的一端進行插入和刪除運算。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出?；蛲藯?，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
從上圖是基于數(shù)組實現(xiàn)的棧，可以看到，對棧的操作（壓棧、出棧）其實都是對棧頂元素的操作，因此壓棧和出棧的速度都比較快。棧中元素按照FILO順序排序的，即先入后出的規(guī)則，先放進去的元素最后才能被彈出來。
一、棧結(jié)構要素
1、棧，是用來存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構，可以使用數(shù)組或鏈表來實現(xiàn)棧結(jié)構
2、棧頂，顧名思義棧最頂部的元素，壓棧與出棧的對象
3、棧深度，棧中數(shù)據(jù)多少，如果棧結(jié)構為數(shù)組，當棧長度大于等于數(shù)組長度后，會拋出異?；?qū)?shù)組進行擴容，棧結(jié)構是鏈表就沒有這個限制。
//存放數(shù)據(jù)
private Object[] data; //數(shù)據(jù)量
private int size; //棧頂
private int top; //默認棧大小
private static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //最大容量
private int maxCapacity;
二、壓棧
/**
* 向棧中放數(shù)據(jù)
* @param obj
* @return */
public boolean push(Object obj){
if (size >= maxCapacity)
return false;
data[++top] = obj;
size++; return true;
}
壓棧操作比較簡單，將新元素放在原棧頂?shù)纳厦妫瑮ｍ斨羔樛弦苿右晃?。我這里當棧深度等于數(shù)組長度后是直接返回false的，當然根據(jù)實際的需求，你也可以對現(xiàn)有數(shù)組進行擴容，然后將原棧中元素放入新棧中即可。如：
/**
* 壓棧，如果棧深度超出數(shù)組長度，將數(shù)組擴大1.5倍
* @param obj
* @return */
public boolean push1(Object obj){
if (size >= maxCapacity){
maxCapacity = maxCapacity * 3 / 2;
Object[] newStack = new Object[maxCapacity];
System.arraycopy(data,0,newStack,0,size);
Arrays.fill(data,null);
data = newStack;
}
data[++top] = obj;
size++; return true;
}
三、出棧
/**
* 從棧中彈出數(shù)據(jù)
* @return */
public Object pop(){
if (size <= 0)
return null;
size--;
Object old = data[top];
data[top--] = null; return old;
}
出棧操作將棧頂元素擲為null，然后將棧頂指針往下移動一位即可，很簡單。
四、查看棧頂
/**
* 查看數(shù)據(jù) */
public Object peek(){
if (isEmpty())
return null;
return data[top];
}
這個方法更是簡單，只是查看棧頂元素，并沒有將棧頂元素刪除。
五、清空棧
/**
* 清空棧數(shù)據(jù) */
public void clear(){
while (top > -1){
data[top--] = null;
}
size = 0;
}
棧數(shù)據(jù)結(jié)構的實現(xiàn)基本已經(jīng)講完了，棧的基本操作差不多包包含在里面了，代碼實現(xiàn)起來就是這么簡單。另外，另一種基于鏈表的棧我就不再這里說了，因為也是很簡單的，這是棧限定對鏈表的操作只能是操作鏈表頭部，大家如果感興趣的話可以自己嘗試用鏈表實現(xiàn)一個棧，或者可以參考一下我之前寫的基于鏈表實現(xiàn)的隊列，原理是差不多的，也可以參考一下jdk中的LinkedList。
應用場景
1.函數(shù)的調(diào)用，比如Java中方法的調(diào)用就是方法的入棧和出棧的操作。
2.使用棧實現(xiàn)計算器的功能，這個我在后續(xù)的文章中會有寫到。
3.網(wǎng)頁瀏覽記錄。因為棧先進后出的特性，所以每次打開網(wǎng)頁時就把當前的網(wǎng)頁壓入棧中，后退時先出棧，然后跳頁面。
4.棧數(shù)據(jù)結(jié)構喲非常多的應用場景，這里只是列舉其中一二。
