Implement Stack using Queues

Problem Statement

In this challenge, the objective is to design a data structure that simulates a Last-In-First-Out (LIFO) stack using only two queues. The usual stack operations such as push, pop, top, and empty need to be supported by the simulated stack. This entails that the primary methods include depositing an element, removing the top element, inspecting the top element, and checking if the stack is empty.

Implementing the MyStack class:

• push(int x): Push element x to the top of the stack.
• pop(): Remove and return the top element of the stack.
• top(): Return the top element of the stack without removing it.
• empty(): Return true if the stack is empty, otherwise false.

Note: You are restricted to using only standard queue operations:

• Add to back
• Remove from front
• Peek from front
• Check size
• Check if empty

If queues are not natively available in your language, simulate them using deques or lists, but strictly follow queue behavior.

Examples

Example 1

Input:

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:

[null, null, null, 2, 2, false]

Explanation:

MyStack myStack = new MyStack();
myStack.push(1);       // stack: [1]
myStack.push(2);       // stack: [1, 2]
myStack.top();         // returns 2
myStack.pop();         // returns 2, stack becomes [1]
myStack.empty();       // returns false

Constraints

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty
• All calls to pop and top are valid (the stack will not be empty)

Approach and Intuition

A stack operates on a LIFO (Last-In-First-Out) principle, while a queue works in FIFO (First-In-First-Out) order. To simulate a stack using two queues, we must manipulate the queue behavior to reverse the order of elements when necessary.

There are two common strategies:

1. Costly push: Always enqueue the new element to an empty queue, then enqueue all previous elements behind it.
2. Costly pop/top: Keep enqueueing elements normally, and when a pop or top is needed, dequeue from one queue and transfer all but the last element to the other queue.

This ensures the most recent element behaves like the top of the stack. Carefully controlling the transfer between queues is the key to achieving the desired LIFO behavior with FIFO structures.

Solutions

// Retrieve the first element in the queue.
public int getTop() {
    return q1.peek();
}