ImplementStackUsingQueues [source code]
public class ImplementStackUsingQueues {
static
/******************************************************************************/
public class MyStack {
private Queue<Integer> queue;
private Integer top;
/** Initialize your data structure here. */
public MyStack() {
queue = new LinkedList<>();
}
/** Push element x onto stack. */
public void push(int x) {
queue.offer(x);
top = x;
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
Queue<Integer> temp = new LinkedList<>();
while (queue.size() > 1) {
temp.offer(queue.poll());
}
Integer res = queue.poll();
while (temp.size() > 0) {
top = temp.poll();
queue.offer(top);
}
return res;
}
/** Get the top element. */
public int top() {
return top;
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
/******************************************************************************/
public static void main(String[] args) {
ImplementStackUsingQueues.MyStack tester = new ImplementStackUsingQueues.MyStack();
tester.push(1);
tester.push(2);
tester.push(3);
System.out.println(tester.empty());
System.out.println(tester.pop());
System.out.println(tester.pop());
System.out.println(tester.top());
}
}
刚开始想设计出来一个类似之前的QueueUsingStack类似的聪明的算法, 不过后面好像还是想不出来, 最后就用最直接的方法来做了, 速度是96ms (76%), 还算可以接受;
这个算法有一个稍微要注意的地方就是 top 要自己维护, 不然除了在 top()的时候也来一个O(N) 的操作, 你是没有可能找到 top 的;
editorial 的第一个办法跟我的差不多, 唯一不同的是他始终维护 temp, 然后真正需要 pop 的时候, pop 完了之后, input跟 output 再 swap 一下, 这个我感觉就没有什么必要了;
第一个这个方法里面其实就相当于 input 是主 queue: push 操作是 cheap 的操作, pop 是 expensive;
另外一个方案当然就是让 push expensive: 让 output 是主 queue, 每次 push 的时候, 都把 input 的 queue 清空, 反正也没有什么改善; 事实上, pop 的次数不可能超过 push 的次数, 所以让 push 变 expensive 并不聪明;
editorial 好像没有什么特别好的答案了;
discussion 里面大部分认为更好的思路应该是让push 更 expensive; 我刚开始不这样认为, 因为我认为一个 queue, 可能 push 很多次, 但是 pop 的次数不会太多(不超过 push 的次数; 另外 top 可以不用管). 但是后来我想了一下, 也不一定. 虽然我们这里描述的时候都是O(N) 的说法, 但是 N 跟 N 是不一样的, 这个就是amortized analysis需要分析的地方: 不同的 N 之间的关系; push 的时候的 N, 我们一般可以假定, 相对来说都比较小, 而 pop 的时候的 N, 很多时候都很大, 尤其是如果是一个, 像你上面所说的那样的 push 大量多于 pop 的序列, 那么最后每一次 pop 的 N 都是非常大的. 当然了, push 如果次数够多, 那么就算 N 很小, 连续 K 个 push 的时间复杂度也是O(N^2)的.
后来我想了想, 好像差不多, 如果是 N 个 push, 然后 N 个 pop. 我们如果让 push 是O(N), 那么最后的复杂度是O(N^2) + O(N). 如果让 pop 是O(N), 好像最后也是这个结果;
discussion 还真有人想出来了一个比较奇葩的O(1)的做法, 非常类似之前426的时候学习 ocaml 的时候的一些做法:
Build a recursive data structure to simulate a stack.
Each item in the queue is either a number or another queue. The first added element is deep withing this structure:
start: null
push 1: [1, null ]
push 2: [2, [1, null ] ]
push 3: [3, [2, [1, null ] ] ]
push 4: [4, [3, [2, [1, null ] ] ] ]
pop : queue.pop-front is 4, then queue.pop-front is [3, [2, [1, null ] ] ]
pop : queue.pop-front is 3, then queue.pop-front is [2, [1, null ] ]
And the code which needs a few "unsafe" operations in Java 5 Generics (the interface can still be type-safe though, because the structure is well-known and private):
class MyStack {
// push to back = add(), peek = peek(), pop from front = poll(), is empty = isEmpty()
private Queue<Object> queue = null;
public void push(int x) {
Queue deeper = queue;
queue = new LinkedList<Object>();
queue.add(x);
queue.add(deeper);
}
@SuppressWarnings("unchecked")
public void pop() {
// unused variable, just to show what's going on
int x = (Integer)queue.poll();
queue = (Queue<Object>)queue.poll();
}
public int top() {
return (Integer)queue.peek();
}
public boolean empty() {
return queue == null;
}
}
The main memory usage is still O(n) to store the int and there's one extra Queue object per item. It's actually a weird linked list implementation with a node being a queue of two items: containing data and next pointer. The recursive structure won't be a problem, because it's just pointers pointing around the heap randomly.
这个是同样的算法, 类似的另外一个人的写法:
class MyStack {
private Queue queue;
public void push(int x) {
Queue q = new LinkedList(); // could be any queue type, see note above
q.add(x);
q.add(queue);
queue = q;
}
public void pop() {
queue.remove();
queue = (Queue) queue.peek();
}
public int top() {
return (int) queue.peek();
}
public boolean empty() {
return queue == null;
}
}
这种做法还是比较逆向思维的: 以前都是谈到 recursion 想到 Stack, 结果他们这里是谈到了 Stack 想到了 recursion, 直接通过build a recursive structure来模拟 Stack;
另外好像理论上是可以正经的写出来一个O(N^(1/2))的解的, 不过很麻烦, 而且如果可以使用足够多个 queue, 最后是可以逼近O(1)的复杂度的, 不过这个就有点特别理论了:
(https://cstheory.stackexchange.com/questions/2562/one-stack-two-queues/2589#2589)
Problem Description
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, and is empty operations 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).
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and all test cases.
Difficulty:Easy
Total Accepted:74K
Total Submissions:227.2K
Contributor: LeetCode
Companies
bloomberg
Related Topics
stack design
Similar Questions
Implement Queue using Stacks
/**
- Your MyStack object will be instantiated and called as such:
- MyStack obj = new MyStack();
- obj.push(x);
- int param_2 = obj.pop();
- int param_3 = obj.top();
- boolean param_4 = obj.empty();
*/