堆疊和佇列相關面試題

前言：
上篇文章介紹了堆疊和佇列及其相關操作，本篇通過幾個面試題，來進一步掌握堆疊和佇列~

括號匹配問題

題目：在線OJ

思考：

• 創立一個堆疊，存盤字符型別
• 遍歷字串，依次取出每個字符
• 若為左括號，即：(，[，{， 則入堆疊，然后接著繼續比較
• 若為右括號，則取出堆疊頂元素，與該元素匹配
• 最后，判斷堆疊是否為空 (這一步一定不要忘)

圖解：

代碼實作：

public boolean isValid(String s) {
    //創建一個堆疊,存盤字符型別
    Stack<Character> stack = new Stack<>();
    //遍歷字串，依次取出每個字符
    for(int i = 0;i < s.length();i++){
        //使用charAt，取出每個元素
        char c = s.charAt(i);
        //如果 c 為左括號，則入堆疊
        if(c == '(' || c == '[' || c== '{'){
            stack.push(c);
            continue;
        }
        if(stack.empty()){
            return false;
        }
        //若 c 為右括號，則取出堆疊頂元素，與該元素比較
        char top = stack.pop();
        if(top == '(' && c == ')'){
            continue;
        }
        if(top == '[' && c == ']'){
            continue;
        }
        if(top == '{' && c == '}'){
            continue;
        }
        return false;
    }
    //最后判斷堆疊是否為空
    if(stack.empty()){
        return true;
    }
    return false;
}

用佇列實作堆疊

題目：在線OJ

思考：

• 創建兩個佇列 A B
• 入堆疊操作： 把新元素直接往 A 中插入即可
• 出堆疊操作： 將 A 中的元素往 B 中轉移，當剩最后一個元素的時候， 直接從 A 中出佇列即可，最后將 A B 兩佇列交換，讓 A 始終保持為入堆疊操作
• 取堆疊頂元素： 和出堆疊類似，只不過最后一個元素不洗掉
• 判定為空： 即 A 和 B 都為空，即為空

圖解：

代碼實作：

class MyStack {
    //創建兩個佇列
    private Queue<Integer> A = new LinkedList<>();
    private Queue<Integer> B = new LinkedList<>();

    //入堆疊
    public void push(int x) {
        //直接往 A 中入佇列即可
        A.offer(x);
    }
    //出堆疊
    public Integer pop() {
        //判斷是否為空
        if(empty()){
            return null;
        }
        //將 A 中的元素 轉移到 B 中
        while(A.size() > 1){
            Integer a = A.poll();
            //A 為空
            if(a == null){
                break;
            }
            //插入到B中
            B.offer(a);
        }  
        //回圈結束，A中應只有1個元素
        //將此元素出佇列即可
        int ret = A.poll();
        swapAB();
        return ret;
    }
    //交換 A B 
    public void swapAB(){
        Queue<Integer> tmp = A;
        A = B;
        B = tmp;
    }
    //取堆疊頂元素
    public Integer top() {
        //判斷是否為空
        if(empty()){
            return null;
        }
        //將 A 中的元素 轉移到 B 中
        while(A.size() > 1){
            Integer a = A.poll();
            //A 為空
            if(a == null){
                break;
            }
            //插入到B中
            B.offer(a);
        }  
        //回圈結束，A中應只有1個元素
        //將此元素出佇列即可
        int ret = A.poll();
        B.offer(ret);
        swapAB();
        return ret;
    }
    //判斷是否為空
    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

用堆疊實作佇列

題目：在線OJ

思考：

• 創建兩個堆疊 A B；A 負責入佇列，B 負責出佇列
• 入佇列： 先把 B 中元素轉移到 A 中，然后再直接往 A 中插入 (入堆疊)
• 出佇列： 先把 A 中元素轉移到 B 中，然后對 B 進行出堆疊操作
• 取隊首元素： 先把 A 中元素轉移到 B 中，然后取 B 的堆疊頂元素，即隊首元素
• 判斷是否為空： A 和 B 都為空

圖解：

代碼實作：

class MyQueue {
    //創建兩個堆疊
    private Stack<Integer> A = new Stack<>();
    private Stack<Integer> B = new Stack<>();
    //入佇列
    public void push(int x) {
        //將B中元素轉移到A中
        while(!B.isEmpty()){
            int tmp = B.pop();
            A.push(tmp);
        }
        //再把新元素 入堆疊
        A.push(x);
    }
    //出佇列
    public Integer pop() {
        //判斷是否為空
        if(empty()){
            return null;
        }
        //將A中元素轉移到B中
        while(!A.isEmpty()){
            int tmp = A.pop();
            B.push(tmp);
        }
        //再對 B 出堆疊
        return B.pop();
    }
    //取隊首元素
    public Integer peek() {
        //判斷是否為空
        if(empty()){
            return null;
        }
        //將A中元素轉移到B中
        while(!A.isEmpty()){
            int tmp = A.pop();
            B.push(tmp);
        }
        //直接取B的堆疊頂元素
        return B.peek();
    }
    //判斷是否為空
    public boolean empty() {
        return A.isEmpty() && B.isEmpty();
    }
}

實作一個最小堆疊

題目：在線OJ

思考：

即： A中進行正常的堆疊的三個操作，而B中存放當前A中最小元素

• 創建兩個堆疊A B
• 對 A 進行正常的入 / 出堆疊，取堆疊頂元素操作
• 第一個元素在 A B 中均插入
• 之后，每在 A 中插入一個元素，都與 B 中元素堆疊頂元素比較，將較小值插入 B 中
• 最后 B 的堆疊頂元素，便是堆疊中所有元素中最小的那個

圖解：

代碼實作：

class MinStack {
    //創建兩個堆疊 A B 
    private Stack<Integer> A = new Stack<>();
    private Stack<Integer> B = new Stack<>();

    //入堆疊
    public void push(int val) {
        A.push(val);
        if(B.isEmpty()){
            B.push(val);
            return;
        }
        int min = B.peek();
        if(val < min){
            min = val;
        }
        B.push(min);
    }

    //出堆疊
    public Integer pop() {
        if(A.isEmpty()){
            return null;
        }
        B.pop();
        return A.pop();
    }
    
    //取堆疊頂元素
    public Integer top() {
        if(A.isEmpty()){
            return null;
        }
        return A.peek();
    }
    
    //取最小元素
    public Integer getMin() {
        if(A.isEmpty()){
            return null;
        }
        return B.peek();
    }
}

設計一個回圈佇列

題目： 在線OJ

思考：
在介紹堆疊和佇列中，我們設計了一個回圈佇列，但在那個實作中，tail 始終就是隊尾的下一個元素，那么當佇列滿時， tail 指向的位置就是空的，即：陣列中有一個位置是浪費的，顯然那個思路不適合本題

當佇列頭或佇列尾的索引值到達陣列上限時，需要再從零開始
可以：head = (head + 1) % array.length，索引值就會自動進行回圈

代碼實作：

class MyCircularQueue {

    private int[] array = {0};
    private int head = 0;
    private int tail = -1;
    private int size = 0;

    public  MyCircularQueue(int k) {
        this.array = new int[k];
    }

    //入佇列
    public boolean enQueue(int value) {
    	//判斷是否為滿佇列
        if(isFull()){
            return false;
        }
        this.tail = (this.tail + 1) % this.array.length;
        this.array[tail] = value;
        this.size++;
        return true;
    }

    //出佇列
    public boolean deQueue() {
    	//判斷是否為空
        if(isEmpty()){
            return false;
        }
        this.head = (this.head + 1) % this.array.length;
        this.size--;
        return true;
    }

    //取隊首元素
    public int Front() {
        //判斷是否為空
        if(isEmpty()){
            return -1;
        }
        return this.array[head];
    }
    
    //取隊尾元素
    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        return this.array[tail];
    }
    //判斷是否為空
    public boolean isEmpty() {
        return this.size == 0;
    }
    //判斷是否為滿佇列
    public boolean isFull() {
        return this.size == array.length;
    }
}