232. Implement Queue using Stacks

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 emptyoperations 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).

Solution:

Two stacks. 

My original solution is use two stacks, input and output, when we try to push an element, we do input.push(output.pop()) and then input.push(x), then output.push(input.pop()) . In this way, output will be always in the right order, so pop and peek will be O(1) and we only need to check if output is empty in order to check if the implemented queue is empty. 

For example, if current stack is

1

2

3

we want push another 4 into the implemented queue, 

I will move all the element to input stack with push(output.pop())

3

2

1

then push 4 to the input stack 

4

3

2

1

then move all the elements back to output:

1

2

3

4

which makes output always the right order.

Later I saw a better solution:

Which is we don't have to always keep the output stack the right order, while we can make it right whenever there is a peek or pop action.

For example

we can keep the input stack always in reversed order by simply push every single element into the input stack.

4

3

2

1

when we try to pop or peek we move all the elements to output stack: 

1

2

3

4

Even later we have push actions, we can always keep  push into the input stack

Let's say we pop twice then push 5, 6

output stack:                                                input stack

3                                                                   6

4                                                                   5

The idea is output + reversed input will be the whole queue.

Code:

 class MyQueue {  
   Stack<Integer> st1;  
   Stack<Integer> st2;  
   /** Initialize your data structure here. */  
   public MyQueue() {  
     st1=new Stack<Integer>();  
     st2=new Stack<Integer>();  
   }  
   /** Push element x to the back of queue. */  
   public void push(int x) {  
     st1.push(x);  
   }  
   /** Removes the element from in front of queue and returns that element. */  
   public int pop() {  
     peek();  
     return st2.pop();      
   }  
   /** Get the front element. */  
   public int peek() {  
     if(st2.empty()){  
        while(!st1.empty()) st2.push(st1.pop());  
     }     
     return st2.peek();  
   }  
   /** Returns whether the queue is empty. */  
   public boolean empty() {  
     return st2.empty() && st1.empty();  
   }  
 }