Leetcode No.225(Implement Stack using Queues) 心得
題目:
Implement the following operations of a stack using queues.
- push(x) — Push element x onto stack.
- pop() — Removes the element on top of the stack.
- top() — Get the top element.
- empty() — Return whether the stack is empty.
Notes:
- You must use only standard operations of a queue — which means only
push to back,peek/pop from front,size, andis emptyoperations are valid. - Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
- You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
想法:
Stack特性: 先進後出
Queue特性: 先進先出
我的做法就是拿兩個 Queue,去處理 pop 時候會遇到的情況,並且有個變數去記錄 top 位置。
這個方法效率是倒數的,後來參考解答,有個方法是兩個 queue 可以用 swap 方式交換內容,這樣省去 copy 動作 (概念就是交換 pointer),效率就到達 50%。
這裡還要特別注意就是一開始我用 for loop 去操作 queue 的內容,但是使用了 for (int i = 0; i < que.size()-1; i++),這是錯誤的。
因為 que.size() 是 unsigned int,如果 que.size() = 0 且 que.size()-1 會變成 overflow。
class MyStack {
public:
/** Initialize your data structure here. */
MyStack() {}
/** Push element x onto stack. */
void push(int x) {
myqueue.push(x);
topValue = x;
}/** Removes the element on top of the stack and returns that element. */
int pop() {
int result;while (myqueue.size() != 0) {
result = myqueue.front();
myqueue.pop();
if (!myqueue.empty()) {
topValue = result;
tmpqueue.push(result);
}
}myqueue.swap(tmpqueue);
return result;
}/** Get the top element. */
int top() {
return topValue;
}/** Returns whether the stack is empty. */
bool empty() {
return myqueue.empty();
}
private:
std::queue<int> myqueue;
std::queue<int> tmpqueue;
int topValue;
};
網路上解答:
有三個方法:
(1) 就是我的做法
(2) 在 push 階段就先處理 queue 裡面的順序。利用兩個 queue,把 push 的值放在另一個 queue,並把原來的 queue 的值 FIFO 到另一個 queue裡,最後再 swap。因為原本的 queue 裡面的值排列是 LIFO,把這些值依序放入另一個 queue 中順序仍是 LIFO。 Push 進來的值在另一個 queue是最先進來的,所以也是 First out。
(3) 這個做法很棒只需要用一個 queue。在 push 階段每進來一個值,就會把前面的值 pop 出去再 push進來,概念和 (2) 相同只是只需要一個 queue。
(2) & (3) 做法的好處是 top() 就是 queue.front(),不需要再額外記錄。
這裡貼上第三個做法:
private LinkedList<Integer> q1 = new LinkedList<>();
// Push element x onto stack.
public void push(int x) {
q1.add(x);
int sz = q1.size();
while (sz > 1) {
q1.add(q1.remove());
sz--;
}
}