Implement Stack using Queues | Problems

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support: push(x) to push element x to the top, pop() to remove and return the top element, top() to get the top element without removing it, and empty() to check whether the stack is empty. You must use only standard queue operations.

Example:

push(1), push(2), top() -> 2, pop() -> 2, empty() -> false

Sample Input

—

Sample Output

—

Constraints

1 <= x <= 9
At most 100 calls

Topics

Stack&Queue

Approach: Single Queue Rotation

Use a single queue. After pushing a new element, rotate all previous elements behind it by dequeuing and re-enqueuing n-1 elements. This ensures the most recently pushed element is always at the front for O(1) pop and top operations.

function implementStackUsingQueues() {
  const queue = [];
  return {
    push(x) {
      queue.push(x);
      for (let i = 0; i < queue.length - 1; i++) queue.push(queue.shift());
    },
    pop() { return queue.shift(); },
    top() { return queue[0]; },
    empty() { return queue.length === 0; }
  };
}

Time Complexity: O(n) push, O(1) pop/top

Space Complexity: O(n)

Saved in this browser only. Private to you.