棧（stack）又名堆棧陨晶，它是一種運(yùn)算受限的線性表芝硬。其限制是僅允許在表的一端進(jìn)行插入和刪除運(yùn)算蚜点。這一端被稱為棧頂，相對地拌阴，把另一端稱為棧底绍绘。向一個棧插入新元素又稱作進(jìn)棧、入棾僭撸或壓棧陪拘，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素纤壁；從一個棧刪除元素又稱作出椬蠊簦或退棧，它是把棧頂元素刪除掉酌媒，使其相鄰的元素成為新的棧頂元素欠痴。
從上圖是基于數(shù)組實(shí)現(xiàn)的棧，可以看到秒咨，對棧的操作（壓棧喇辽、出棧）其實(shí)都是對棧頂元素的操作，因此壓棧和出棧的速度都比較快雨席。棧中元素按照FILO順序排序的菩咨，即先入后出的規(guī)則，先放進(jìn)去的元素最后才能被彈出來蛉威。
一糕簿、棧結(jié)構(gòu)要素
1、棧摄闸，是用來存儲數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)缨硝，可以使用數(shù)組或鏈表來實(shí)現(xiàn)棧結(jié)構(gòu)
2摩钙、棧頂，顧名思義棧最頂部的元素查辩，壓棧與出棧的對象
3胖笛、棧深度，棧中數(shù)據(jù)多少宜岛，如果棧結(jié)構(gòu)為數(shù)組长踊，當(dāng)棧長度大于等于數(shù)組長度后，會拋出異称汲或?qū)?shù)組進(jìn)行擴(kuò)容身弊，棧結(jié)構(gòu)是鏈表就沒有這個限制。
//存放數(shù)據(jù)
private Object[] data; //數(shù)據(jù)量
private int size; //棧頂
private int top; //默認(rèn)棧大小
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ù)纳厦妫瑮ｍ斨羔樛弦苿右晃淮鞫Ｎ疫@里當(dāng)棧深度等于數(shù)組長度后是直接返回false的凑术，當(dāng)然根據(jù)實(shí)際的需求，你也可以對現(xiàn)有數(shù)組進(jìn)行擴(kuò)容所意，然后將原棧中元素放入新棧中即可淮逊。如：
/**
* 壓棧，如果棧深度超出數(shù)組長度扶踊，將數(shù)組擴(kuò)大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é)構(gòu)的實(shí)現(xiàn)基本已經(jīng)講完了诈唬，棧的基本操作差不多包包含在里面了，代碼實(shí)現(xiàn)起來就是這么簡單缩麸。另外铸磅，另一種基于鏈表的棧我就不再這里說了，因?yàn)橐彩呛芎唵蔚模@是棧限定對鏈表的操作只能是操作鏈表頭部阅仔，大家如果感興趣的話可以自己嘗試用鏈表實(shí)現(xiàn)一個棧吹散，或者可以參考一下我之前寫的基于鏈表實(shí)現(xiàn)的隊(duì)列，原理是差不多的八酒，也可以參考一下jdk中的LinkedList空民。
應(yīng)用場景
1.函數(shù)的調(diào)用，比如Java中方法的調(diào)用就是方法的入棧和出棧的操作羞迷。
2.使用棧實(shí)現(xiàn)計算器的功能界轩，這個我在后續(xù)的文章中會有寫到。
3.網(wǎng)頁瀏覽記錄衔瓮。因?yàn)闂Ｏ冗M(jìn)后出的特性浊猾，所以每次打開網(wǎng)頁時就把當(dāng)前的網(wǎng)頁壓入棧中，后退時先出棧热鞍，然后跳頁面葫慎。
4.棧數(shù)據(jù)結(jié)構(gòu)喲非常多的應(yīng)用場景，這里只是列舉其中一二薇宠。
