https://leetcode.com/problems/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, and empty() to check whether the stack is empty. You must use only standard queue operations: push to back, peek/pop from front, size, and is empty.

Example:

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

Sample Input

—

Sample Output

—

Constraints

1 <= x <= 9
At most 100 calls to push, pop, top, empty
All pop and top calls are valid

Topics

Stack&Queue

Approach: Single Queue Rotation

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

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.