DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Implement Stack using Queues

easyStack and queue

Problem statement

Build a last-in, first-out stack, MyStack, using only queues. You may only use standard queue operations: add to the back, remove from the front, look at the front, check the size and check whether it is empty.

Support these operations:

  • push(x) puts x on top of the stack.
  • pop() removes and returns the top element.
  • top() returns the top element without removing it.
  • empty() returns whether the stack is empty.

pop and top are only called on a non-empty stack.

Examples

Example 1

Input: push(2) push(9) top() pop() push(6) pop() pop() empty()

Output: 9 9 6 2 true

Explanation: The most recent push is always what comes out next.

Example 2

Input: push(11) empty() top()

Output: false 11

Hints

Approach

Use a single queue and do the reordering once, on push, so the newest element is always at the front.

  1. push(x): add x to the back, then rotate the queue size - 1 times (remove from the front and add to the back). Every older element moves behind x, so x is at the front.
  2. pop(): remove from the front. O(1).
  3. top(): look at the front. O(1).
  4. empty(): check the size.

push is O(n), but pop, top and empty are O(1), and only one queue is needed. With queue-only operations, one side has to pay O(n); this version puts the cost on the single write instead of on every read.

ComplexityTime push O(n), pop/top O(1)Space O(n)
Python
from collections import deque
class MyStack:
def __init__(self):
self.q = deque() # front of the queue = top of the stack
def push(self, x: int) -> None:
self.q.append(x)
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q.popleft()
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return not self.q

Follow-up questions

  • Which version would you pick if the workload is 95% pushes? What if it is 95% top calls?

Frequently asked questions

Not with queue operations alone. A queue only exposes its oldest element, while a stack needs the newest, so some operation must move up to n elements. The choice is which operation pays: push (one queue, cheap reads) or pop (cheap writes).

The problem checks that you can reason about ordering guarantees, the same reasoning used to decide whether a job runner, retry buffer or log shipper must process work oldest-first or newest-first, and what it costs to change that order after the fact.

Yes. Looking at the front element is the queue's peek operation. The code never touches the back of the deque except through append, so it stays within queue rules.