import java.util.Queue;
import java.util.LinkedList;

// one-queue approach
// enqueue O(n)
// dequeue O(1)
class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        int currentSize = queue.size();
        queue.offer(x);
        // Shift by the previous number of elements
        for (int i = 0; i < currentSize; i++) {
            queue.offer(queue.poll());
        }
    }
    
    public int pop() {
        return queue.poll();
    }
    
    public int top() {
        return queue.peek();
    }
    
    public boolean empty() {
        return queue.isEmpty();
    }
}

// enqueue O(1)
// dequeue O(n)
// class MyStack {
//     Queue<Integer> queue1;
//     Queue<Integer> queue2;

//     public MyStack() {
//         queue1 = new LinkedList<Integer>();
//         queue2 = new LinkedList<Integer>();
//     }
    
//     public void push(int x) {
//         queue1.offer(x);
//     }
    
//     public int pop() {
//         while (queue1.size() > 1) {
//             queue2.offer(queue1.poll());
//         }
//         int popped = queue1.poll();
//         Queue<Integer> temp = queue1;
//         queue1 = queue2;
//         queue2 = temp; 
//         return popped;
//     }
    
//     public int top() {
//         while (queue1.size() > 1) {
//             queue2.offer(queue1.poll());
//         }
//         int theTop = queue1.peek();
//         queue2.offer(queue1.poll());
//         Queue<Integer> temp = queue1;
//         queue1 = queue2;
//         queue2 = temp; 
//         return theTop;
//     }
    
//     public boolean empty() {
//         return queue1.isEmpty();
//     }
// }

// enqueue O(n)
// dequeue O(1)
// class MyStack {
//     Queue<Integer> queue1;
//     Queue<Integer> queue2;

//     public MyStack() {
//         queue1 = new LinkedList<Integer>();
//         queue2 = new LinkedList<Integer>();
//     }
    
//     public void push(int x) {
//         queue2.offer(x);
//         while (!queue1.isEmpty()) {
//             queue2.offer(queue1.poll());
//         }
//         Queue<Integer> temp = queue1;
//         queue1 = queue2;
//         queue2 = temp; 
//     }
    
//     public int pop() {
//         return queue1.poll();
//     }
    
//     public int top() {
//         return queue1.peek();
//     }
    
//     public boolean empty() {
//         return queue1.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();
 */