LeetCode通關：棧和隊列六連，比對問題有絕招

刷題路線參考： https://github.com/chefyuan/algorithm-base https://github.com/youngyangyang04/leetcode-master

大家好，我是靠寫部落格督促自己刷題的老三，這一節我們對線棧和隊列。

棧和隊列基礎

在正式開刷之前，我們先了解一些棧和隊列的基礎知識。

棧的結構

棧是一種先進後出的順序表結構。

棧的結構比較簡單，就不多了。

棧的實作

因為棧是一個線性表表，是以，線性表支援棧的操作，ArrayList 和 LinkedList 都可以作為棧來使用。

可以直接使用 Stack 類來進行建立一個棧，這個繼承的是過期。

Deque<TreeNode> stack = new LinkedList<TreeNode>();//類型為TreeNode
Stack<TreeNode> stack = new Stack<TreeNode>();      

隊列結構

隊列是一種先進先出的資料結構

隊列實作

隊列也是表結構，比較常用的是由LinkedList實作。

Queue<TreeNode> queue = new LinkedList<TreeNode>();      

好了，兩種資料結構也比較簡單，開始我們的刷題之旅吧！

刷題現場

劍指 Offer 09. 用兩個棧實作隊列

☕ 題目：劍指 Offer 09. 用兩個棧實作隊列(https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)

❓ 難度：簡單

📕 描述：

用兩個棧實作一個隊列。隊列的聲明如下，請實作它的兩個函數 appendTail 和 deleteHead ，分别完成在隊列尾部插入整數和在隊列頭部删除整數的功能。(若隊列中沒有元素，deleteHead 操作傳回 -1 )

示例 1：

輸入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
輸出：[null,null,3,-1]      

示例 2：

輸入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
輸出：[null,-1,null,null,5,2]      

💡思路：

棧是先進後出，隊列是先進先出的資料結構。

那怎麼用棧模拟隊列呢？

需要兩個棧，一個作為隊頭 headStack，一個作為隊尾 tailStack。

• tailStack 作為隊尾，模拟入隊操作，當有一個元素入隊時，則将其 push 到tailStack 棧頂。
• headStack 作為隊頭，模拟出隊操作，當有一個元素出隊時，則将 headStack 棧頂的元素 pop。
• 當 headStack 中沒有元素時，将 tailStack 中所有的元素都 push 進 headStack 中。

這樣一來，就用兩個棧模拟了隊列的出入順序。

我們來看一下代碼實作：

public class CQueue {

    //定義兩個棧
    Deque<Integer> headStack, tailStack;

    public CQueue() {
        headStack = new LinkedList<>();
        tailStack = new LinkedList<>();
    }

    //入隊
    public void appendTail(int value) {
        //入隊，往tailStack中壓入值
        tailStack.push(value);
    }

    //出隊
    public int deleteHead() {
        //如果隊頭為空
        if (headStack.isEmpty()) {
            //則将 tailStack （隊尾）的元素全部出棧，再壓入headStack
            while (!tailStack.isEmpty()) {
                headStack.push(tailStack.pop());
            }
        }
        if (headStack.isEmpty()) {
            return -1;
        }
        return headStack.pop();
    }
}      

🚗 時間複雜度：入隊O(1，出隊O(n)。

🏠 空間複雜度：引入了兩個棧，是以空間複雜度O(n)。

還有一道題，

LeetCode232. 用棧實作隊列

基本是一樣的。

LeetCode225. 用隊列實作棧

☕ 題目：225. 用隊列實作棧 (https://leetcode-cn.com/problems/implement-stack-using-queues/)

請你僅使用兩個隊列實作一個後入先出（LIFO）的棧，并支援普通棧的全部四種操作（

push

、

top

pop

和

empty

）。

實作

MyStack

類：

• void push(int x) 将元素 x 壓入棧頂。
• int pop() 移除并傳回棧頂元素。
• int top() 傳回棧頂元素。
• boolean empty() 如果棧是空的，傳回 true ；否則，傳回 false 。

注意：

• 你隻能使用隊列的基本操作 —— 也就是

  push to back

  peek/pop from front

  size

  is empty

  這些操作。
• 你所使用的語言也許不支援隊列。 你可以使用 list （清單）或者 deque（雙端隊列）來模拟一個隊列 , 隻要是标準的隊列操作即可。

示例：

輸入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
輸出：
[null, null, null, 2, 2, false]

解釋：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 傳回 2
myStack.pop(); // 傳回 2
myStack.empty(); // 傳回 False      

💡 思路：

這道題，實不相瞞，乍一看，我有點想偷懶，因為如果用一個雙向隊列的話：

是不是啪一下就實作了，但是題目裡面也說了，标準隊列操作，是以我們還是用單向隊列。

那我們怎麼實作呢？

很簡單，入棧的時候，我們利用隊列先進先出的特點，每次隊列模拟入棧時，我們先将隊列之前入隊的元素都出隊，僅保留最後一個進隊的元素。

然後再重新入隊，這樣就實作了颠倒隊列中的元素，這樣就和棧中的次序是一樣的了。

代碼實作如下：

public class MyStack {
    //單向隊列
    Queue<Integer> queue;

    /**
     * Initialize your data structure here.
     */
    public MyStack() {
        queue = new LinkedList<>();
    }

    /**
     * Push element x onto stack.
     */
    public void push(int x) {
        //入隊元素
        queue.offer(x);
        //将之前的元素，出隊，重新入隊
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
    }

    /**
     * Removes the element on top of the stack and returns that element.
     */
    public int pop() {
        return queue.poll();
    }

    /**
     * Get the top element.
     */
    public int top() {
        return queue.peek();
    }

    /**
     * Returns whether the stack is empty.
     */
    public boolean empty() {
        return queue.isEmpty();
    }
}      

🚗 時間複雜度：入棧O(n），出棧O(1)。

🏠 空間複雜度：引入了隊列，空間複雜度O(n)。

LeetCode20. 有效的括号

☕ 題目：20. 有效的括号 (https://leetcode-cn.com/problems/valid-parentheses/)

給定一個隻包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字元串 s ，判斷字元串是否有效。

有效字元串需滿足：

• 左括号必須用相同類型的右括号閉合。
• 左括号必須以正确的順序閉合。

輸入：s = "()"
輸出：true      

輸入：s = "()[]{}"
輸出：true      

示例 3：

輸入：s = "(]"
輸出：false      

示例 4：

輸入：s = "([)]"
輸出：false      

示例 5：

輸入：s = "{[]}"
輸出：true      

提示：

• 1 <= s.length <= 104

• s

  僅由括号

  '()[]{}'

  組成

這是一道經典的棧的應用的題目。

思路是什麼呢？

碰到左括号把元素入棧，碰到右括号就和棧頂元素比較，如果相同就把棧頂元素出棧，不比對，就直接傳回false。

代碼如下：注意處理棧為空的情況

public boolean isValid(String s) {
        Deque<Character> stack = new LinkedList<>();
        //周遊字元串
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //遇到左括号，入棧
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            }
            //右括号比對
            if (c == ')') {
                if (stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }
            }
            if (c == ']') {
                if (stack.isEmpty() || stack.pop() != '[') {
                    return false;
                }
            }
            if (c == '}') {
                if (stack.isEmpty() || stack.pop() != '{') {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }      

🚗 時間複雜度：O(n）。

🏠 空間複雜度：O(n)。

LeetCode1047. 删除字元串中的所有相鄰重複項

給出由小寫字母組成的字元串 S，重複項删除操作會選擇兩個相鄰且相同的字母，并删除它們。

在 S 上反複執行重複項删除操作，直到無法繼續删除。

在完成所有重複項删除操作後傳回最終的字元串。答案保證唯一。

輸入："abbaca"
輸出："ca"
解釋：
例如，在 "abbaca" 中，我們可以删除 "bb" 由于兩字母相鄰且相同，這是此時唯一可以執行删除操作的重複項。之後我們得到字元串 "aaca"，其中又隻有 "aa" 可以執行重複項删除操作，是以最後的字元串為 "ca"。      

這道題是不是和上道題差不多。

周遊字元，如果字元和棧頂元素比對，就把棧頂元素出棧。

如果不比對，就把元素入棧。

這樣一來，棧裡最後剩下的都是相鄰不相同的元素。

代碼如下：最後出棧的元素需要倒轉

public String removeDuplicates(String s) {
        Deque<Character> stack = new LinkedList<>();
        //周遊字元串
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (stack.isEmpty() || stack.peek() != c) {
                //入棧
                stack.push(c);
            } else {
                //棧頂元素出棧
                stack.pop();
            }
        }
        //拼接棧中字元
        StringBuilder str = new StringBuilder();
        while (!stack.isEmpty()) {
            str.append(stack.pop());
        }
        return str.reverse().toString();
    }      

LeetCode150. 逆波蘭表達式求值

☕ 題目：150. 逆波蘭表達式求值 (https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/)

❓ 難度：中等

根據

逆波蘭表示法

，求表達式的值。

有效的算符包括

+

-

*

/

。每個運算對象可以是整數，也可以是另一個逆波蘭表達式。

說明：

• 整數除法隻保留整數部分。
• 給定逆波蘭表達式總是有效的。換句話說，表達式總會得出有效數值且不存在除數為 0 的情況。

輸入：tokens = ["2","1","+","3","*"]
輸出：9
解釋：該算式轉化為常見的中綴算術表達式為：((2 + 1) * 3) = 9      

輸入：tokens = ["4","13","5","/","+"]
輸出：6
解釋：該算式轉化為常見的中綴算術表達式為：(4 + (13 / 5)) = 6      

輸入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
輸出：22
解釋：
該算式轉化為常見的中綴算術表達式為：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22      

逆波蘭表達式：

逆波蘭表達式是一種字尾表達式，所謂字尾就是指算符寫在後面。

• 平常使用的算式則是一種中綴表達式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
• 該算式的逆波蘭表達式寫法為 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波蘭表達式主要有以下兩個優點：

• 去掉括号後表達式無歧義，上式即便寫成 1 2 + 3 4 + * 也可以依據次序計算出正确結果。
• 适合用棧操作運算：遇到數字則入棧；遇到算符則取出棧頂兩個數字進行計算，并将結果壓入棧中。

看到沒，這道題的提示裡面就給出了思路：

适合用棧操作運算：遇到數字則入棧；遇到算符則取出棧頂兩個數字進行計算，并将結果壓入棧中。

public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < tokens.length; i++) {
            String s = tokens[i];
            if (isNumber(s)) {
                stack.push(Integer.parseInt(s));
            } else {
                int num1 = stack.pop();
                int num2 = stack.pop();
                if (s.equals("+")) {
                    stack.push(num1 + num2);
                } else if (s.equals("-")) {
                    stack.push(num2 - num1);
                } else if (s.equals("*")) {
                    stack.push(num1 * num2);
                } else if (s.equals("/")) {
                    stack.push(num2 / num1);
                }
            }

        }
        return stack.pop();
    }

    boolean isNumber(String token) {
        return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));
    }      

LeetCode402. 移掉 K 位數字

給你一個以字元串表示的非負整數

num

和一個整數

k

，移除這個數中的

k

位數字，使得剩下的數字最小。請你以字元串形式傳回這個最小的數字。

示例 1 ：

輸入：num = "1432219", k = 3
輸出："1219"
解釋：移除掉三個數字 4, 3, 和 2 形成一個新的最小的數字 1219 。      

示例 2 ：

輸入：num = "10200", k = 1
輸出："200"
解釋：移掉首位的 1 剩下的數字為 200. 注意輸出不能有任何前導零。      

示例 3 ：

輸入：num = "10", k = 2
輸出："0"
解釋：從原數字移除所有的數字，剩餘為空就是 0 。      

• 周遊字元串 s，若目前棧不為空并且棧頂元素的值大于目前周遊的元素值并且移除元素的個數沒有達到要求 k，則棧頂元素出棧，count 值加 1。
• 若目前周遊的元素比棧頂元素的值要大，則直接将該元素壓棧。
• 若目前周遊的元素值為 " 0 " 并且棧為空，則直接跳過這次循環（要保證棧底的元素不能為 " 0 "，因為題目要求 num 不會包含任何前導零，就是不能用 " 0 " 來開頭）。
• 若周遊完整個字元串而 count < k（移除的元素個數沒有達到要求，示例：num = “123456”, k = 3），此時直接将棧中的前三個元素依次出棧，即 " 654 " 出棧剩下的 " 321 " 翻轉一下，即為最小值。
• 若目前棧為空（去掉一個最大的元素後，其餘元素均為 " 0 "），則直接傳回 " 0 " 即可。

代碼如下：

public String removeKdigits(String num, int k) {
        if (k == num.length()) return "0";
        //棧
        Deque<Character> stack = new LinkedList<>();
        int count = 0;
        for (int i = 0; i < num.length(); i++) {
            while (!stack.isEmpty() && stack.peek() > num.charAt(i) && count < k) {
                stack.pop();
                count++;
            }
            //棧為空，且目前位為0時，我們不需要将其入棧
            if (num.charAt(i) == '0' && stack.isEmpty()) continue;
            stack.push(num.charAt(i));
        }
        while (!stack.isEmpty() && count < k) {
            stack.pop();
            count++;
        }
        //這個是最後棧為空時，删除一位，比如我們的10，删除一位為0，
        //按上面邏輯我們會傳回""，是以我們讓其傳回"0"
        if (stack.isEmpty()) return "0";
        StringBuffer sb = new StringBuffer();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }
      

總結

大家熟悉😂的順口溜總結：

簡單的事情重複做，重複的事情認證做，認證的事情有創造性地做。——

我是三分惡，一個能文能武的全棧開發。

點贊

關注

不迷路，咱們下期見。