DSA-30 is now live!
Day 4 - Stacks and QueuesStacksPractice QuestionsQueue using Stacks

Implement Queue using Stacks easy

Description

Implement a first-in-first-out (FIFO) queue using only two stacks. The queue should support the standard operations:

  • push(x) — push x to the back of the queue
  • pop() — remove and return the element at the front
  • peek() — return the element at the front without removing
  • empty() — return whether the queue is empty

You may only use the standard stack operations: push, peek/top, pop, size, isEmpty.

Examples

q.push(1)
q.push(2)
q.peek()   # -> 1
q.pop()    # -> 1
q.empty()  # -> False

Constraints

  • All calls to pop and peek are valid (the queue is non-empty when called).
  • Aim for amortized O(1) per operation.

Intuition

A stack reverses the order things come out (LIFO). If we run something through two stacks, it gets reversed twice — back to FIFO.

Use two stacks:

  • inStack — everything we push goes here.
  • outStack — everything we pop comes from here.

When outStack is empty and we need to pop or peek, pour everything from inStack into outStack. The order gets flipped, so the oldest element (front of the queue) ends up on top of outStack. Future pops are O(1) until outStack empties again.

push 1, 2, 3:    inStack = [1, 2, 3]   outStack = []
pop (empty out)  →  pour:  inStack = []  outStack = [3, 2, 1]   ← 1 is now on top
pop  → returns 1, outStack = [3, 2]
push 4:          inStack = [4]         outStack = [3, 2]
pop  → returns 2, outStack = [3]

Code

Explanation

  • push is trivially O(1) — always lands in inStack.
  • pop / peek are usually O(1) (just hits outStack). Sometimes they trigger a “pour” — that one operation is O(n), but it spreads the work for n future O(1) pops.
  • This is amortized O(1) — the average cost over many operations.

Amortized analysis matters here: each element is moved across stacks at most twice (once into inStack on push, once into outStack on shift). So total work across n operations is O(n) → O(1) per operation on average.

Analysis

  • Time: O(1) amortized for all operations.
  • Space: O(n) — two stacks holding the queue’s elements.
Min StackNext Greater Element