//用队列实现栈
//自己的方法：
class MyStack {

       Queue<Integer>q1;
       Queue<Integer>q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }
    
    public void push(int x) {
       q1.offer(x);
       while(!q2.isEmpty())
       q1.offer(q2.poll());
       Queue<Integer>tmp=q1;
       q1=q2;
       q2=tmp;
    }
    
    public int pop() {
       if(!q2.isEmpty())
       return q2.poll();
       return -1;
    }
    
    public int top() {
       if(!q2.isEmpty())
       return q2.peek();
       return -1;
    }
    
    public boolean empty() {
       return q2.isEmpty();
    }
}

/**
 * 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();
 */
//老师的方法
class MyStackUseQueue {

    public Queue<Integer> qu1;
    public Queue<Integer> qu2;

    public MyStackUseQueue() {
        qu1 = new LinkedList<>();
        qu2 = new LinkedList<>();
    }
    
    public void push(int x) {
        if(!qu1.isEmpty()) {
            qu1.offer(x);
        }else if(!qu2.isEmpty()) {
            qu2.offer(x);
        }else {
            qu1.offer(x);
        }
    }
    
    public int pop() {
        if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            for(int i = 0;i < size-1;i++) {
                qu2.offer( qu1.poll());
            }
            return qu1.poll();
        }else  {
            int size = qu2.size();
            for(int i = 0;i < size-1;i++) {
                qu1.offer( qu2.poll());
            }
            return qu2.poll();
        }
    }
    
    public int top() {
        if(empty()) {
            return -1;
        }
        if(!qu1.isEmpty()) {
            int size = qu1.size();
            int val = 0;
            for(int i = 0;i < size;i++) {
                val = qu1.poll();
                qu2.offer(val);
            }
            return val;
        }else  {
            int size = qu2.size();
             int val = 0;
            for(int i = 0;i < size;i++) {
                val = qu2.poll();
                qu1.offer(val);
            }
            return val;
        }
    }
    
    public boolean empty() {
        return qu1.isEmpty() && qu2.isEmpty();
    }
}



 //用栈实现队列
 class MyQueue {
   Stack<Integer>s1;
   Stack<Integer>s2;
    public MyQueue() {
       s1=new Stack<>();
       s2=new Stack<>();
    }
    
    public void push(int x) {
       s1.push(x);
       
    }
    
    public int pop() {
        if(s2.isEmpty())
       while(!s1.isEmpty())
       s2.push(s1.pop());
       return s2.pop();
    }
    
    public int peek() {
        if(s2.isEmpty())
       while(!s1.isEmpty())
       s2.push(s1.pop());
       return s2.peek();
    }
    
    public boolean empty() {
    return s1.isEmpty()&&s2.isEmpty();
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */