刷題路線參考：

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 ，判斷字串是否有效，

有效字串需滿足：

左括號必須用相同型別的右括號閉合，
左括號必須以正確的順序閉合，

示例 1：

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

示例 2：

輸入：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();
    }

🚗 時間復雜度：O(n），

🏠 空間復雜度：O(n)，

LeetCode150. 逆波蘭運算式求值

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

? 難度：中等

📕 描述：

根據逆波蘭表示法，求運算式的值，

有效的算符包括 +、-、*、/ ，每個運算物件可以是整數，也可以是另一個逆波蘭運算式，

說明：

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

示例 1：

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

示例 2：

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

示例 3：

輸入：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));
    }

🚗 時間復雜度：O(n），

🏠 空間復雜度：O(n)，

LeetCode402. 移掉 K 位數字

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

? 難度：中等

📕 描述：

給你一個以字串表示的非負整數 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();
    }

總結

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

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

我是三分惡，一個能文能武的全堆疊開發，

點贊、關注不迷路，咱們下期見，

參考：

[1]. https://github.com/youngyangyang04/leetcode-master

[2]. https://github.com/chefyuan/algorithm-base

[3]. https://leetcode-cn.com/problems/remove-k-digits/solution/yi-diao-kwei-shu-zi-zhan-by-booooo_-01nh/

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/295452.html

標籤：其他

上一篇：nginx負載均衡session共享

下一篇：C++之模板初階：甩鍋編譯器

LeetCode通關：堆疊和佇列六連，匹配問題有絕招

堆疊和佇列基礎

堆疊的結構

堆疊的實作

佇列結構

佇列實作

刷題現場

劍指 Offer 09. 用兩個堆疊實作佇列

LeetCode225. 用佇列實作堆疊

LeetCode20. 有效的括號

LeetCode1047. 洗掉字串中的所有相鄰重復項

LeetCode150. 逆波蘭運算式求值

LeetCode402. 移掉 K 位數字

總結