[LeetCode] 225. Implement Stack using Queues－yoruru的努力日記

225. Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue's standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

1 <= x <= 9
At most 100 calls will be made to push, pop, top, and empty.
All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

SOL：

使用兩個queue q1, q2來實作stack，q1是主要queue、q2是暫存queue

對queue實做沒概念，只知道FIFO，即使看了正解也看不懂。

Implement Stack using Queues | GeeksforGeeks

在開始之前，有幾個東西需要補一下：

1. 雙向的序列 deque

[Day 23] 從零開始學Python - 資料結構模組deque：旁人來來去去像行雲流水
當我們在練習LeetCode寫題目時，
常常會需要stack(堆疊)或queue(佇列)這兩種資料結構，
前者通常使用list即可，後者則一般會使用deque。
deque是一個雙向的序列，可以從開頭或結尾傳入或取出資料。
deque作為queue使用時，主要會用popleft()跟append()來操作。

2. python中的交換可以不用temp

詳細可參考：Python Program to swap two numbers without using third variable | GeeksforGeeks