??????? 一：面試經典
??????? 1. 如何設計一個括號匹配的功能？比如給你一串括號讓你判斷是否符合我們的括號原則，
???????? 棧??????? 力扣??????? 2. 如何設計一個瀏覽器的前進和后退功能？
??????? 思想：兩個棧，一個棧存放前進棧，一個存放后退棧，剛開始連續點擊三個頁面，都存放到前進棧里，當點擊后退時就出棧頂，然后放入后退棧中，以此重復。??????? 3. 簡單的四則運算：3+11*2+8-15/5，
??????? 思想：兩個棧來實現：一個放數字 一個放符號。
??????? 解決思路：我們從頭開始遍歷這個算術表達式：
??????????? 1.遇到是數字 我們就直接入棧到數字棧里面去。
??????????? 2.遇到是符號 就把符號棧的棧頂拿出來做比較。如果說他比棧頂符號的優先級高就直接入棧，如果比符號棧頂的優先級低或者相同，就從符號棧里面取棧頂進行計算（從數字棧中取棧頂的2個數），計算完的結果還要再放入到數字棧中。
??????? 二： 棧
????????
????????1.如何理解棧
????????比如我們在放盤子的時候都是從下往上一個個放，拿的時候是從上往下一個個的那，不能從中間抽，這種其實就是一個典型的棧型數據結構。后進先出即Last In First Out （LIFO）。????????2.棧如何實現
????????其實它是一個限定僅在表尾進行插入和刪除操作的線性表。這一端被稱為棧頂，相對地，把另一端稱為棧底。向一個棧插入新元素又稱作進棧、入棧或壓棧，它是把新元素放到棧頂元素的上面，使之成為新的棧頂元素；從一個棧刪除元素又稱作出棧或退棧，它是把棧頂元素刪除掉，使其相鄰的元素成為新的棧頂元素。
????????棧其實就是一個特殊的鏈表或者數組。
????????既然棧也是一個線性表，那么我們肯定會想到數組和鏈表，而且棧還有這么多限制，那為什么我們還要使用這個數據結構呢？不如直接使用數組和鏈表來的更直接么？數組和鏈表暴露太多的接口，實現上更靈活了，有些技術理解不到位的人員就可能出錯。所以在某些特定場景下最好是選擇棧這個數據結構。
??????? 三：棧的分類
3.棧的分類
（1）基于數組的棧——以數組為底層數據結構時，通常以數組頭為棧底，數組頭到數組尾為棧頂的生長方向
?
（2）基于單鏈表的棧——以鏈表為底層的數據結構時，以鏈表頭為棧頂，便于節點的插入與刪除，壓棧產生的新節點將一直出現在鏈表的頭部
????????最大的區別就是擴容，鏈表天然支持動態擴容。棧溢出。?
??????? 四：棧的實現
public interface MyStack<Item> {MyStack<Item> push(Item item); //入棧Item pop(); //出棧int size(); // 大小boolean isEmpty();
}public class ArrayStack<Item> implements MyStack<Item>{private Item [] a = (Item[]) new Object[1]; //最好就是開始的時候就設置大小private int n = 0; //大小 初始的元素個數public ArrayStack(int cap) {a = (Item[]) new Object[cap];}public MyStack<Item> push(Item item) { //入棧就完成了 //時間復雜度 O(1)judgeSize();a[n++] = item;return null;}private void judgeSize(){if(n >= a.length){ //元素個數已經超出了數組的個數resize(2 * a.length); //10*2*2=40個大小了，我出棧了20個了，只剩下20了吧。}else if(n > 0 && n < a.length / 2){resize(a.length / 2);}}private void resize(int size){ //擴容O（n）Item[] temp = (Item[]) new Object[size];for(int i = 0 ; i < n; i ++){temp[i] = a[i];}a = temp;}public Item pop() { //出棧 O(1)if(isEmpty()){return null;}//item[n--]//item[--n]Item item = a[--n]; //n不是已經--了么 --n和n-- --n是先把n減了在用，n--先用了在減a[n] = null; //為什么要這一步return item;}public int size() {return n;}public boolean isEmpty() {return n == 0;}}
??????? 注意：主要是棧入棧出的核心代碼以及擴容的說明，棧入是n++，而棧出為n--，同時還要把這個元素的空間釋放掉，n為棧存儲的元素個數。
