Computer Science
Updated 4 days ago | GitHub

Implement Stack Using Queue

Problem Highlights

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • Could pop() or top() be called on an empty stack?
    • “You may assume pop and top are only called when the stack is non-empty.”
  • Which queue operations are we allowed to use?
    • “Only standard queue operations: push to the back, peek/pop from the front, size, and is_empty. You may use a deque (or Queue) as the underlying queue.”
  • Are we allowed to use more than one queue?
    • “Yes — the canonical solutions use either one or two queues. Either is acceptable as long as only queue operations are used.”
HAPPY CASE
s = MyStack()
s.push(1) -> No Return
s.push(2) -> No Return
s.top()   -> 2
s.pop()   -> 2
s.empty() -> False
s.pop()   -> 1

EDGE CASE
s = MyStack()
s.empty() -> True

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

This problem does not follow a strict, standard pattern. However, students should think about the fundamental differences between Stacks and Queues:

  • Order of Data
    • A stack is LIFO (last-in, first-out) while a queue is FIFO (first-in, first-out). Reversing the queue’s natural order is what lets us emulate a stack.
  • Cost of Reversing Order
    • We can reverse order eagerly (on every push) so that pop/top are O(1), or lazily (on pop) so that push is O(1). LeetCode 225 accepts either trade-off.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a single queue and make push do the work. After enqueuing the new element, rotate every previously-enqueued element to the back of the queue. The newly pushed value is then at the front of the queue, so pop and top can read the queue’s front directly — matching LIFO behavior.

Constructor
1) Create a single queue (e.g. a deque used as a queue)

Push(x)
1) Enqueue x at the back of the queue
2) For i in [0, queue.size() - 1):
       dequeue from the front and enqueue at the back
   (After this loop the queue's front is x.)

Pop
1) Dequeue from the front of the queue and return that value

Top
1) Return (without removing) the value at the front of the queue

Empty
1) Return True if the queue has no elements, else False

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

class MyStack:

    def __init__(self):
        # A single queue is sufficient when push does the rotation work.
        self.q = deque()

    def push(self, x: int) -> None:
        # Enqueue x, then rotate every prior element behind it so x is at the front.
        self.q.append(x)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        # Front of the queue is the most recently pushed element.
        return self.q.popleft()

    def top(self) -> int:
        # Peek at the front without removing it.
        return self.q[0]

    def empty(self) -> bool:
        return not self.q

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.

Trace push(1); push(2); top(); pop() with the single-queue approach (front shown leftmost):

push(1)
  append 1                      -> q: [1]
  rotate 0 elements             -> q: [1]
push(2)
  append 2                      -> q: [1, 2]
  rotate 1 element (1 to back)  -> q: [2, 1]
top()
  return q[0]                   -> 2
pop()
  popleft                       -> 2, q: [1]

After the trace q == [1], so a subsequent pop() correctly returns 1 and empty() becomes True.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of elements currently on the stack.

  • Time Complexity:
    • push: O(N) — the rotation loop touches every prior element once.
    • pop, top, empty: O(1).
  • Space Complexity: O(N) for the underlying queue holding the N elements.

A two-queue variant can shift the cost so that push is O(1) and pop is O(N) instead; the trade-off is symmetric. The single-queue approach above is preferred for its simplicity.