一、堆疊(Stack)

1.堆疊的基本概念

堆疊：一種特殊的線性表，其只允許在固定的一端進行插入和洗掉元素操作，進行資料插入和洗掉操作的一端稱為堆疊頂，另一端稱為堆疊底，堆疊中的資料元素遵守后進先出LIFO（Last In First Out）的原則，

壓堆疊：堆疊的插入操作叫做進堆疊/壓堆疊/入堆疊，入資料在堆疊頂，
出堆疊：堆疊的洗掉操作叫做出堆疊，出資料在堆疊頂，

堆疊頂指標：顧名思義，堆疊頂指標是指向堆疊頂的一個指標，但Java當中沒有指標這一說法，因此也可以當作下標來進行處理，

需要注意的是：堆疊頂指標指向的是可以存放元素的堆疊的位置，一旦有元素放入后它再加1，

Stack中的方法有：

push為壓堆疊，pop為出堆疊（回傳值為出堆疊的值），peek為堆疊頂元素，empty為判斷堆疊是否為空，search為找出某個元素在堆疊中的第幾個位置，回傳下標，

2.用順序表實作堆疊

用順序表實作的堆疊稱為順序堆疊，只是該順序表的實際操作也是一樣要遵循堆疊的基本操作——先進后出，

public class MyStack {
    private int[] elem ;
    private int top = 0 ;

    public MyStack() {
        this.elem = new int[3];
    }

    public void push(int item) {
        if(top==elem.length) {
            Arrays.copyOf(elem,5);
            return;
        }
        elem[top]=item;
        top++;
    }
    public int pop() {
        if(top==0) {
            throw new UnsupportedOperationException("堆疊為空");
        }
        top--;
        int ret = this.elem[top];
        return ret;
    }
    public int peek() {
        if(top==0) {
            throw new UnsupportedOperationException("堆疊為空");
        }
        return this.elem[top-1];
    }
    public int search(int item) {
        return 0;
    }
}

3.用鏈表實作堆疊

**用鏈表實作堆疊要注意一個點：因為堆疊遵循的是先進后出，因此我們在入堆疊時的操作為單鏈表的頭插法，出堆疊時的操作為洗掉單鏈表的頭結點，并使得頭結點指向下一結點，**只有這樣用單鏈表實作堆疊才能做到時間復雜度為O(1)，

class Node{
    public int val;
    public Node next;

    public Node(int val) {
        this.val = val;
    }
}
public class MyLinkedStack {
    public Node head;
    public void push(int data) {
        Node node = new Node(data);
        if(head==null) {
            head=node;
        } else {
            node.next=head;
            head=node;
        }
    }
    public int pop() {
        int ret = head.val;
        head=head.next;
        return ret;
    }
    public void display() {
        Node cur = head;
        while(cur!=null) {
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }
}

4.有關堆疊的相關面試題

例一：不可能的輸出序列

題目：一個堆疊的入堆疊序列是a,b,c,d,e則堆疊的不可能的輸出序列是：（）
A edcbd B decba C dceab D abcde

解：答案為C，一定要時刻注意堆疊的特點：先進后出，分析B選項，因為第一個出堆疊為d，則直接入堆疊到d后停止，d出堆疊，還剩a,b,c；第二個出堆疊為c，則還剩a，b；第三個出堆疊為e，則我們可以令e入堆疊后再出，此時還是剩a，b；再將b，a出堆疊則為b選項，D選項則是每一個進堆疊后直接先出，

例二：中綴運算式轉后綴運算式

題目：將中綴運算式轉為后綴運算式，如中綴運算式X = a+b * c-d，則其后綴運算式為？

解：因為是一個運算式，先用括號將整體括起來(X = a+b * c-d)，又因為從左到右運算時，先運算的是乘，將b * c用括號括起來，則為(X=a+(b * c)-d)；接著是用bc的結果去加a，將a與它用括號括起來，則為(X=(a+(bc))-d)；最后再計算減d，結果為(X=((a+(b * c))-d))，再將運算子移到相應右括號的外面再將括號去掉，最終得后綴運算式為Xabc * +d-= ，

例三：有效的括號

對應leetcode題

思路：因為題目的要求是括號是否匹配，將左括號（包括左大括號、左中括號、左小括號）壓入堆疊中，如果不是左括號，則與堆疊頂的左括號進行匹配，‘(‘ 對應 ‘)’；‘[’d對應’]’；‘{’對應‘}’，否則回傳false，

此題有四種情況：
1.左括號和右括號相等的情況下，左括號與右括號出現了不匹配的情況，回傳false，
2.左括號多于右括號不可能匹配成功，現象為遍歷字串結束后堆疊中還有元素，
3.右括號多于左括號也不可能匹配成功，現象為當遍歷到右括號時堆疊中沒有元素跟其進行配對，
4.左括號與右括號都配對成功，并且遍歷完字串后堆疊中沒有元素，

例如"{[]}"字串，首先初始化一個堆疊，將‘{’壓入堆疊中，下一個為‘[’，是左括號壓入堆疊中，下一個為‘]’，與堆疊中的第一個元素進行配對，發現為‘[’，則將堆疊頂元素出堆疊，下一個為‘}’，與堆疊中的元素‘{’匹配成功，最后字串遍歷完成并堆疊中沒有元素，回傳true，

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while(i<s.length()) {
            if(s.charAt(i)=='('||s.charAt(i)=='{'||s.charAt(i)=='[') {
                stack.push(s.charAt(i));
            }else {
                char ch = s.charAt(i);
                if(ch==')') {
                    if(!stack.empty()&&stack.peek()=='(') {
                        stack.pop();
                    } else {
                        return false;
                    }
                } else if(ch=='}') {
                    if(!stack.empty()&&stack.peek()=='{') {
                        stack.pop();
                    }else {
                        return false;
                    }
                } else if(ch==']') {
                    if(!stack.empty()&&stack.peek()=='[') {
                        stack.pop();
                    }else {
                        return false;
                    }
                }
            }
            i++;
        }
        if(stack.empty()) {
            return true;
        }
        return false;
    }
}

例四：最小堆疊

對應leetcode題

思路：初始化兩個堆疊，一個為stack普通堆疊，另一個為minStack專門用來存放每次壓入堆疊stack中的最小值，
1、當一個元素要壓入stack中（push方法），則minStack是否要壓入堆疊有兩種情況：(1)當minStack為空時，直接將該元素壓入minStack中即可，(2)當minStack不為空，則需要與minStack中的堆疊頂元素進行比較，如果小于或等于minStack堆疊頂元素，則壓入minStack中；否則無需壓入minStack，
2、當一個元素要從stack中出堆疊（pop方法），則minStack對應的處理：如果stack中出堆疊的元素與minStack的堆疊頂元素相同，它們對應堆疊中的最小值，minStack中的堆疊頂元素也要出堆疊，
3、minStack中的堆疊頂元素就是stack中全部元素的最小值，

class MinStack {
    private Stack<Integer> stack ;
    private Stack<Integer> minStack;
    public MinStack() {
        stack=new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        stack.push(val);
        if(minStack.empty()) {
            minStack.push(val);
        }else {
            int top = minStack.peek();
            if(top>=val) {
                minStack.push(val);
            }
        }
    }
    
    public void pop() {
        if(stack.empty()) {
            return;
        }
        int top = stack.pop();
        if(top==minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        if(stack.empty()) {
            return -1;
        }
        return stack.peek();
    }
    
    public int getMin() {
        if(minStack.empty()) {
            return -1;
        }
        return minStack.peek();
    }
}

二、佇列(Queue)

1.佇列的基本概念

只允許在一端進行插入資料操作，在另一端進行洗掉資料操作的特殊線性表，佇列具有先進先出FIFO(First In First Out) ，入佇列：進行插入操作的一端稱為隊尾（Tail/Rear） ，出佇列：進行洗掉操作的一端稱為隊頭（Head/Front），

Queue介面中的方法：

add和offer方法沒什么大致的區別，都是入隊操作，remove為洗掉某一個元素（但是它不太符合佇列的特點，因此比較少用），poll為出隊操作，并且回傳的是出隊時的元素，element和peek都為獲得隊頭的元素，但對對頭不進行操作，

Queue

Deque(雙端佇列)其實也是用鏈表實作，操作不同

2.用鏈表實作佇列

為何不用順序表實作佇列是因為用佇列是遵循先進先出原則的，這樣的話在順序表當中很容易造成“假的”滿佇列，即佇列當中沒有任何元素并且front和rear都指向了順序表的最后一個位置就不能再放入元素，為了避免這種情況發生，順序表只能在每次模仿佇列的出隊時，表頭元素出順序表則后面的元素都要向前挪一個單位，這樣時間復雜度就達到了O(n)，

鏈表來實作佇列能做到入隊和出隊的時間復雜度為O(1)，即出隊操作：在表尾處設定last結點，當有元素入隊時last結點指向該新結點，再將last結點改為新結點處，入隊操作：在表頭處設定head結點，當有元素出隊時head指向它的下一個結點，

圖解：
1、初始鏈表

2、入隊

3、出隊

代碼：

class Node {
    public int val;
    public Node next;

    public Node(int val) {
        this.val = val;
    }
}
public class MyLinkedQueue {
    public Node first;
    public Node last;

    public void offer(int data) {
        Node node = new Node(data);
        if(first==null) {
            first=node;
            last=node;
            return;
        }
        last.next=node;
        last=node;
    }
    public int poll() {
        if(first==null) {
            throw new UnsupportedOperationException("佇列為空");
        }
        int ret = first.val;
        first=first.next;
        return ret;
    }
    public boolean isEmpty() {
        if(first==null) {
            return true;
        }
        return false;
    }
    public int remove() {
        if(first==null) {
            return -1;
        }
        int ret = first.val;
        first=first.next;
        return ret;
    }
    public int peak() {
        if(first==null) {
            throw new UnsupportedOperationException("佇列為空");
        }
        int ret = first.val;
        return ret;
    }
}

3.有關佇列的面試題

例一：用佇列實作堆疊

對應leetcode題

思路：題目給出要用兩個佇列實作堆疊，因此我們可以先初始化兩個佇列que1和que2，重點和難點是要在兩個佇列的出隊或入隊的操作中實作堆疊的先進后出原則，

1、push方法：如果是一開始兩個佇列均為空，則入隊的元素任選一個隊入隊即可；當不是第一次入隊，則入隊的元素選擇在不為空的隊當中入，則結果肯定是有一個隊有元素，而另一個隊為空隊，
2、pop方法：因為堆疊的特點是后進先出，即后入隊的要先出隊，則我們可以把有元素的隊的隊長減1個元素直接入隊到另一條隊中，還剩下的那一個元素不再入隊，直接poll即可，
3、top方法：跟pop的操作方法類似，只是將一個隊當中的全部元素入到另一個隊當中，并且回傳的是最后一個入隊的元素，
4.empty方法：如果兩個佇列均為空，則堆疊為空，回傳true，

圖解：
1、初始化兩個佇列

2、入堆疊（假設入12、33和45）

3、出堆疊（假設出45）

4、入堆疊（入67）

大概的操作就這么多，以此類推，

class MyStack {
    private Queue<Integer> que1;
    private Queue<Integer> que2;
    public MyStack() {
        que1=new LinkedList<>();
        que2=new LinkedList<>();
    }
    
    public void push(int x) {
        if(!que1.isEmpty()) {
            que1.offer(x);
        }else if(!que2.isEmpty()) {
            que2.offer(x);
        }else {
            que1.offer(x);
        }
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }else {
            if(!que1.isEmpty()) {
                int size = que1.size();
                int i=0;
                while(i<size-1) {
                    que2.offer(que1.poll());
                    i++;
                }
                return que1.poll();
            }else{
                int size = que2.size();
                int i=0;
                while(i<size-1) {
                    que1.offer(que2.poll());
                    i++;
                }
                return que2.poll();
            }
        }
    }
    
    public int top() {
        if(empty()) {
            return -1;
        }else {
            if(!que1.isEmpty()) {
                int size = que1.size();
                int i=0;
                int x=-1;
                while(i<size) {
                    x = que1.poll();
                    que2.offer(x);
                    i++;
                }
                return x;
            }else{
                int size = que2.size();
                int i=0;
                int x = -1;
                while(i<size) {
                    x=que2.poll();
                    que1.offer(x);
                    i++;
                }
                return x;
            }
        }
    }
    
    public boolean empty() {
        return que1.isEmpty()&&que2.isEmpty();
    }
}

注意：Queue是一個介面，不可以直接初始化，它的介面內部沒有size方法，但它是繼承與Collection的（Collection介面有size方法），并且此處參考的是子類LinkedList物件，則重寫了size方法，

例二：用堆疊實作佇列

對應leetcode題

思路：題目要求用兩個堆疊來實作佇列，即要用堆疊來實作先進先出原則，先初始化兩個堆疊stack1和stack2，一個堆疊只能進行push，另一個只能進行pop，

1、push方法：只能在其中一個堆疊當中入堆疊，此處令stack1只能進行入堆疊操作，則當有元素要push時直接壓入stack1中，
2、pop方法：此處令stack2只能進行出堆疊操作，如果stack1和stack2為空則無法再出堆疊，若stack1有元素而stack2為空，則將stack1中的元素全部壓入stack2中，再將stack2中的堆疊頂元素出堆疊，則能夠模仿出隊操作，若stack2已經不為空了，則直接將堆疊頂元素出堆疊即可，
3、peek方法：stack2當中的堆疊頂元素等同于佇列的隊頭元素，若stack2為空則同為pop方法的操作將stack1中的堆疊元素全部壓入stack2中，再取stack2中的堆疊頂元素，
4、empty方法：若兩個堆疊都為空，則模仿的佇列為空，回傳true，

圖解：
1、壓隊（先將12，33，45入隊）

2、出隊（將12出隊）

3、取隊頭元素：就是stack2中的堆疊頂元素，

class MyQueue {
    Stack<Integer> stack1 ;
    Stack<Integer> stack2 ;
    public MyQueue() {
        stack1=new Stack<>();
        stack2=new Stack<>();
    }
    
    public void push(int x) {
        stack1.push(x);
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(stack2.empty()){
            while(!stack1.empty()) {
                int x = stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.pop();
    }
    
    public int peek() {
        if(empty()) {
            return -1;
        }
        if(stack2.empty()){
            while(!stack1.empty()) {
                int x = stack1.pop();
                stack2.push(x);
            }
        }
        return stack2.peek();
    }
    
    public boolean empty() {
        return stack1.empty()&&stack2.empty();
    }
}

例三：設計回圈佇列

對應leetcode題

思路：佇列的底層是一個陣列,設其為elem，設計回圈佇列能夠避免佇列的"假滿"情況，我們可以設定front（指向隊頭元素）和rear（指向在隊尾可以放的元素）兩個坐標來操作回圈鏈表，

設計回圈鏈表需要的知識：
1、front和rear初始化的值都為0，代表回圈佇列為空，

2、front和rear每當有元素出隊或有元素入隊時的下一個下標為front=(front+1)%elem.length或rear=(rear+1)%elem.length，

3、front和rear開始的時候都置為0，但是會有一種情況出現，我們假設elem陣列的長度為8，則最后一個下標為7，假設沒有任何元素出隊，則front一直指向0下標，當rear指向下標為7的元素時，該元素再入隊后經公式計算得rear指向的下標為0，此時front和rear相等，那么隊滿和隊空的判斷條件就沖突了，因此我們可以浪費最后一個元素的位置來判斷隊慷訓是隊滿，

4、當我們取隊尾元素的時候，不能想當然地直接去取rear-1的元素，因為rear也有可能會在下標為0的位置出，因此只要判斷rear是否在0位置處，如果是則直接回傳的是elem.length-1的下標位置，否則就可以指向rear-1的下標的元素，

5、因為我們要浪費最后一個下標的空間來判斷回圈佇列是滿還是空，因此假設陣列的長度為k，我們只能放k-1個元素，但是leetcode中的回圈佇列要求你初始化多長的陣列就要放多少個元素，則在初始化陣列的時候加個1即可，

代碼：

class MyCircularQueue {
    private int[] elem ;
    private int front ;
    private int rear;
    public MyCircularQueue(int k) {
        elem=new int[k+1];
        front=0;
        rear=0;
    }
    
    public boolean enQueue(int value) {
        if(isFull()) {
            return false;
        }
        elem[rear]=value;
        rear=(rear+1)%elem.length;
        return true;
    }
    
    public boolean deQueue() {
        if(isEmpty()) {
            return false;
        }
        front=(front+1)%elem.length;
        return true;
    }
    
    public int Front() {
        if(isEmpty()) {
            return -1;
        }
        return elem[front];
    }
    
    public int Rear() {
        if(isEmpty()) {
            return -1;
        }
        int index = (rear==0)?elem.length-1:rear-1;
        return elem[index];
    }
    
    public boolean isEmpty() {
        if(rear==front) {
            return true;
        }
        return false;
    }
    
    public boolean isFull() {
        if((rear+1)%elem.length==front) {
            return true;
        }
        return false;
    }
}

如果覺得這篇文章對你受益匪淺，麻煩點個贊支持一下謝謝！