• 35.6%

https://leetcode.com/problems/implement-queue-using-stacks/#/description

Implement the following operations of a queue using stacks.

• push(x) – Push element x to the back of queue.
• pop() – Removes the element from in front of queue.
• peek() – Get the front element.
• empty() – Return whether the queue is empty.

Notes:

• You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

##### 方法一：

1. 注意的地方，在pop()调用peek()，直接写 peek()就可以了。

2. pop调用peek得到返回的值，然后需要stack2再pop一下，不要忘了。

Oct 10th, 2017

https://discuss.leetcode.com/topic/17974/short-o-1-amortized-c-java-ruby

Short O(1) amortized, C++ / Java / Ruby

I have one input stack, onto which I push the incoming elements, and one output stack, from which I peek/pop. I move elements from input stack to output stack when needed, i.e., when I need to peek/pop but the output stack is empty. When that happens, I move all elements from input to output stack, thereby reversing the order so it’s the correct order for peek/pop.

The loop in peek does the moving from input to output stack. Each element only ever gets moved like that once, though, and only after we already spent time pushing it, so the overall amortized cost for each operation is O(1).

Java

C++

https://discuss.leetcode.com/topic/19152/0-ms-c-solution-using-one-stack-w-explanation

0 ms C++ solution using one Stack w/ explanation.

You can implement queue using just one stack by either making push process costlier or pop costlier. Since we have two functions (top() and pop()) which require the top element of the stack, well make the push() function costlier - that is, for pushing a new element, we recursively pop the stack till it is empty and push it at the bottom of the stack, and take advantage of the recursive call to push back in the popped elements once the recursive call hits the base condition and returns. This implementation makes pop() and peek() functions easier. pop() is just going to pop off the top element in stack and peek() will return the top most element.

https://discuss.leetcode.com/topic/26163/share-my-python-solution-32ms

Share my python solution (32ms)

The idea is to simulate a queue using two stacks (same as previous posts). I use python list as the underlying data structure for stack and add a “move()” method to simplify code: it moves all elements of the “inStack” to the “outStack” when the “outStack” is empty. Here is the code

https://discuss.leetcode.com/topic/17984/accepted-0ms-c-solution-with-two-std-stack-easy-understand

Accepted 0ms c++ solution with two std::stack, easy understand.