Re: [閒聊] 每日LeetCode

[Rushia (みけねこ的鼻屎)]

232. Implement Queue using Stacks
實作只用Stack來模擬Queue的行為。

Example:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]

Explanation
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

思路：
1.就...資料結構課本裡面的東西，利用一個stack暫存頂層元素，拿到底層元素
  之後再把剩餘元素放回原stack即可。

Java Code：
----------------------------------------
class MyQueue {
    private Stack<Integer> s1;
    private Stack<Integer> s2;

    public MyQueue() {
        s1 = new Stack<>();
        s2 = new Stack<>();
    }

    public void push(int x) {
        s1.push(x);
    }

    public int pop() {
        int n = s1.size();
        for (int i = 0; i < n - 1; i++) {
            s2.push(s1.pop());
        }
        int x = s1.pop();
        for (int i = 0; i < n - 1; i++) {
            s1.push(s2.pop());
        }
        return x;
    }

    public int peek() {
        int n = s1.size();
        for (int i = 0; i < n; i++) {
            s2.push(s1.pop());
        }
        int x = s2.peek();
        for (int i = 0; i < n; i++) {
            s1.push(s2.pop());
        }
        return x;
    }

    public boolean empty() {
        return s1.size() == 0;
    }
}
----------------------------------------

--
https://i.imgur.com/sjdGOE3.jpg

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.89.30 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671154225.A.755.html
→ PyTorch: 大師
→ PyTorch: 這甚麼雞掰的題目= =
→ PyTorch: 有queue幹嘛還要用stack去模擬= =
→ Rushia: 還有要用queue模擬stackㄉ捏
推 wwndbk: 大師
推 pandix: 複雜度感覺不太對 pop和peek這樣變O(n)了
→ Rushia: O(1)那個是Follow-up不一樣ㄅ
推 pandix: 喔喔原來放在follow-up