Problem Statement

Implement a stack using only two queues. The stack should behave like a typical last-in-first-out (LIFO) stack, meaning that the last element added should be the first one to be removed.

Implement a Solution class that supports the following operations:

• Solution(): A constructor to initialize the object.
• push(int x): Adds an element x to the top of the stack.
• pop(): Removes the element from the top of the stack and returns it.
• top(): Retrieves the element on the top of the stack without removing it.
• empty(): Checks whether the stack is empty or not and returns true or false accordingly.

Note: You can only use the basic operations of a queue, such as adding an element to the back, removing an element from the front, checking the size, and verifying if the queue is empty.

Examples

Example 1

• Input:

  • ["Solution", "push", "push", "top", "pop", "empty"]
  • [[], [5], [10], [], [], []]

• Expected Output: [null, null, null, 10, 10, false]

• Explanation:

  • push(5) adds 5 to the stack.
  • push(10) adds 10 to the top of the stack.
  • top() returns 10 since it's the top element.
  • pop() removes 10 and returns it.
  • empty() returns false because 5 is still in the stack.

Example 2

• Input:
  • ["Solution", "push", "push", "push", "pop", "top", "pop", "empty"]
  • [[], [1], [2], [3], [], [], [], []]
• Expected Output: [null, null, null, null, 3, 2, 2, false]
• Explanation:
  • push(1) adds 1 to the stack.
  • push(2) adds 2 on top of 1.
  • push(3) adds 3 on top of 2.
  • pop() removes 3 and returns it.
  • top() returns 2, the new top element.
  • pop() removes 2 and returns it.
  • empty() returns false since 1 is still in the stack.

Example 3

• Input:
  • ["Solution", "push", "top", "pop", "empty"]
  • [[], [99], [], [], []]
• Expected Output: [null, null, 99, 99, true]
• Explanation:
  • push(99) adds 99 to the stack.
  • top() returns 99.
  • pop() removes 99 and returns it.
  • empty() returns true because the stack is now empty.

Constraints:

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

Solution

To solve this problem using two queues, the key idea is to simulate the behavior of a stack by manipulating the elements in the queues. The main challenge is to ensure that the pop and top operations return the most recently added element. To achieve this, we maintain two queues:

1. Main Queue: This holds the current state of the stack.
2. Helper Queue: This is used temporarily during the push operation.

The approach involves always pushing the new element into the helper queue, then transferring all elements from the main queue to the helper queue. Finally, we swap the roles of the two queues. This way, the last added element always stays at the front of the main queue, ensuring the correct behavior for pop and top. This approach works well because it maintains the order of elements correctly, making it a valid stack implementation using queues.

Step-by-Step Algorithm

1. Initialization:

   • Start by creating two empty queues named queue1 and queue2.
   • These queues will be used to simulate the behavior of a stack.
   • queue1 will hold the elements in stack order, while queue2 will be a helper queue used during the push operation.

2. Push Operation (push(int x)):

   • Step 1: Add the element x to queue2.
     • This step places the new element at the front of the queue, which will eventually become the top of the stack.
   • Step 2: Transfer all elements from queue1 to queue2.
     • This step ensures that the newly added element x stays at the front of the queue, maintaining the LIFO order of the stack.
     • Each element is removed from queue1 and added to queue2.
   • Step 3: Swap the roles of queue1 and queue2.
     • After transferring all elements, queue2 now holds the elements in the correct stack order.
     • Swapping the queues ensures that queue1 will always be the queue representing the current state of the stack, while queue2 becomes the empty helper queue for the next operation.

3. Pop Operation (pop()):

   • Step 1: Remove and return the front element from queue1.
     • Since queue1 holds the elements in the correct stack order, removing the front element effectively removes the top element of the stack.

4. Top Operation (top()):

   • Step 1: Return the front element of queue1 without removing it.
     • This operation allows you to peek at the top element of the stack without modifying the stack itself.

5. Empty Operation (empty()):

   • Step 1: Check if queue1 is empty.
     • If queue1 is empty, the stack is empty, so return true.
     • Otherwise, return false to indicate that the stack still contains elements.

Algorithm Walkthrough

Let's go through the algorithm step by step using the example:

Input:

• ["Solution", "push", "push", "top", "pop", "empty"]
• [[], [5], [10], [], [], []]

Steps:

1. Operation: Solution (Constructor)

   • Step: Initialize two empty queues, queue1 and queue2.
   • Result: Both queues are empty, ready to simulate the stack operations.

2. Operation: push(5)

   • Step 1: Add 5 to queue2.
     • queue2 now contains: [5]
   • Step 2: Transfer all elements from queue1 to queue2.
     • queue1 is empty, so no elements are transferred.
     • queue2 remains: [5]
   • Step 3: Swap the roles of queue1 and queue2.
     • After swapping, queue1 contains: [5]
     • queue2 is now empty: []

3. Operation: push(10)

   • Step 1: Add 10 to queue2.
     • queue2 now contains: [10]
   • Step 2: Transfer all elements from queue1 to queue2.
     • Move 5 from queue1 to queue2.
     • queue2 now contains: [10, 5]
     • queue1 is now empty: []
   • Step 3: Swap the roles of queue1 and queue2.
     • After swapping, queue1 contains: [10, 5]
     • queue2 is now empty: []

4. Operation: top()

   • Step 1: Return the front element of queue1 without removing it.
     • The front element of queue1 is 10, so 10 is returned as the top element of the stack.
   • Result: The returned value is 10.

5. Operation: pop()

   • Step 1: Remove and return the front element from queue1.
     • The front element of queue1 is 10, so 10 is removed and returned.
     • queue1 now contains: [5]
   • Result: The returned value is 10.

6. Operation: empty()

   • Step 1: Check if queue1 is empty.
     • queue1 contains one element (5), so the stack is not empty.
     • Return false.
   • Result: The returned value is false.

Final Output:

The operations return the following results in sequence: [null, null, null, 10, 10, false].

Code

Complexity Analysis

Time Complexity

1. push(int x):

   • The push operation adds an element to queue2 and then moves all elements from queue1 to queue2.
   • If there are n elements in the stack, this operation will take O(n) time to transfer all elements.
   • Thus, the time complexity of the push operation is O(n).

2. pop():

   • The pop operation removes the front element of queue1.
   • This operation takes constant time O(1) because it only involves removing the front element of the queue.
   • Thus, the time complexity of the pop operation is O(1).

3. top():

   • The top operation returns the front element of queue1 without removing it.
   • This operation also takes constant time O(1).
   • Thus, the time complexity of the top operation is O(1).

4. empty():

   • The empty operation checks whether queue1 is empty, which is a constant-time operation.
   • Thus, the time complexity of the empty operation is O(1).

Space Complexity

• The space complexity of the implementation is O(n) where n is the number of elements in the stack. This is because two queues are used, each of which can hold up to n elements.