[Leetcode]07/09 [Data Structure] Implement Stack using Queues

/* Method1: two queues Push:O(1) Pop:O(n) Top:O(n) Logic: 1. push: append new element to q1 2. pop: mov all elements in q1 other than the last one to q2 and then remove the one left in q1 Method2: push:O(n) pop:O(1) top:O(1) Logic: 1. new element always locates at the first element in q1: when push, add new element in q2 and append all elements in q1 onto q2 one by one 2. swap q1 and q2 3. first is pop and top Method3: Push:O(1) Pop:O(n) Top:O(n) 1. push: append 2. pop and top: append all elements before that last element to last element in q1 */

class MyStack {
    /*    
    Method2:
    push:O(n)
    pop:O(1)
    top:O(1)
    Logic:
    1. new element always locates at the first element in q1: 
    How? 
    - add new element in empty q2 
    - append evry single element in q1 to q2 
    - swap q1 and q2
    3. first is pop and top since it is the newest element
    
    private Queue q1 = new LinkedList();
    private Queue q2 = new LinkedList();
    
    
    // Push element x onto stack.
    public void push(int x) {
        q2.offer(x);
        while ( !q1.isEmpty() )
        {
            q2.offer(q1.poll() );
        }
        // swap
        Queue tmp = q1;
        q1 = q2;
        q2 = tmp;
        
    }

    // Removes the element on top of the stack.
    public void pop() {
        q1.poll();// the first element of q1
    }

    // Get the top element.
    public int top() {
        return q1.peek();
    }

    // Return whether the stack is empty.
    public boolean empty() {
        return q1.isEmpty();
    }
    */
    
    
    /*
    Method3:
    Push:O(1)
    Pop:O(n)
    Top:O(n)
    1. push: append new element to q
    2. pop and top: append all elements before that last element to last element in q1
    */
    private Queue q = new LinkedList();
    
    public void push( int x)
    {
        q.offer(x);   
    }
    public void pop()
    {
        // try to move the last index to the first index and use poll()
        // to remvoe it
        int size = q.size();
        // 123458   => 812345
        // 6 letter 5 times = 1 to size()-1
        
        for ( int i =1; i < size; i++ )
        {
            q.offer( q.poll() );
        }
        q.poll();
        
    }
    
    public int top()
    {
        int size = q.size();
        for ( int i =1; i < size; i++)
        {
            q.offer(q.poll());
        }
        int top = q.peek();
        q.offer(q.poll());
        return top;
    }
    public boolean empty()
    {
        return q.isEmpty();
    }
    
    
}