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

Solution:

To implement a stack using a Queue, the key point is to push the element in the head of the queue instead of tail of the queue. In order to achieve that, we offer the current x to the tail of the queue, and keep poll element and offer it to the tail until the current element becomes the head

Eg, current Q: 1, we want to push 2, we add 2 to the tail of the queue, tail->2 , 1<-head, then, we poll the head and offer it to the queue, the queue becomes tail tail-> 1, 2<-head. If we push another integer, do the same thing, tail-> 3, 1, 2<- head, => tail-> 1, 2, 3<- head. 

In this way we can use the same Q to do pop peek with constant time complexity.

The push will take O(n) 

 class MyStack {  
    LinkedList<Integer> Q;  
   /** Initialize your data structure here. */  
   public MyStack() {  
     Q=new LinkedList<Integer>();  
   }  
   /** Push element x onto stack. */  
   public void push(int x) {  
     int l=Q.size();  
     Q.offer(x);  
     for(int i=0;i<l;i++) Q.offer(Q.poll());  
   }  
   /** Removes the element on top of the stack and returns that element. */  
   public int pop() {  
     return Q.poll();  
   }  
   /** Get the top element. */  
   public int top() {  
     return Q.peek();  
   }  
   /** Returns whether the stack is empty. */  
   public boolean empty() {  
     return Q.isEmpty();   
   }  
 }