DEV Community

Shahrouz Nikseresht
Shahrouz Nikseresht

Posted on

Day 61: Python Queue Using Two Stacks, Amortized O(1) Unbiased FIFO with Brilliant Double-Stack Flip Trick (No Deque Cheats!)

#challenge #python #algorithms #datastructures

Welcome to Day 61 of the #80DaysOfChallenges journey! This intermediate challenge implements a FIFO queue using only two plain stacks (lists in Python), with enqueue pushing to one stack and dequeue cleverly flipping to the other for amortized O(1) operations per call. It's the classic "queue via stacks" interview question (LeetCode #232 style), demonstrating how LIFO structures can perfectly simulate FIFO behavior without mutating originals or using built-ins like deque. If you're prepping for FAANG interviews, mastering data structure conversions, or building custom queues for games/algorithms, this "Python queue with two stacks" script is efficient, unbiased (no favoritism in order), and the exact amortized O(1) technique that impresses recruiters.

💡 Key Takeaways from Day 61: Queue Via Stacks Functions

This task features simple enqueue/dequeue functions using two lists as stacks, a printer for visualization, and main for interactivity. It's a brilliant flip pattern: input stack for pushes, output for pops with lazy transfer. We'll detail: enqueue as simple push, dequeue with flip on empty, and printer with main input.

1. Enqueue Function: Direct Push to Input Stack

The enqueue is straightforward:

def enqueue(stack_in, value):
    """Push value into the input stack."""
    stack_in.append(value)  # normal push operation
Enter fullscreen mode Exit fullscreen mode

Just append to input stack. O(1) always. This preserves push order until flip.

2. Dequeue Function: Lazy Flip for Amortized O(1)

The dequeue handles the magic:

def dequeue(stack_in, stack_out):
    """Remove and return front element using two-stack transfer logic."""
    if not stack_out:                           # if output stack is empty,
        while stack_in:                         # transfer all items from input
            stack_out.append(stack_in.pop())    # reversing their order

    if not stack_out:    # queue is empty
        return None

    return stack_out.pop()    # pop gives FIFO
Enter fullscreen mode Exit fullscreen mode

If output empty, flip input to output (reverses to FIFO). Pop from output. Flip O(n) but rare, amortized O(1) over m ops.

3. Printer and Main: Visualization and Interaction

The print_queue shows state:

def print_queue(stack_in, stack_out):
    """Show queue contents in FIFO order."""
    # out_stack holds front (but reversed), so reverse it + add in_stack
    items = list(reversed(stack_out)) + stack_in
    print(f"Queue (front -> back): {items}")
Enter fullscreen mode Exit fullscreen mode

Reverses output + input for front-to-back view.

Main handles input/dequeues:

raw = input("Enter queue elements (space-separated): ").strip()

stack_in = []    # stack for enqueue operations (push here)
stack_out = []   # stack for dequeue operations (pop here after transfer)

for val in raw.split():
    enqueue(stack_in, val)

k_raw = input("How many dequeues? ").strip()

k = int(k_raw)

for _ in range(k):
    removed = dequeue(stack_in, stack_out)
    if removed is None:
        print("Queue empty. Stopping.")
        break
    print(f"Dequeued: {removed}")
    print_queue(stack_in, stack_out)
Enter fullscreen mode Exit fullscreen mode

Builds queue, dequeues k times with prints. Interactive.

🎯 Summary and Reflections

This queue via stacks shows creative structure use for simulation. It reinforced:

  • Amortized analysis: Rare O(n) flips, average O(1).
  • Lazy transfer: Flip only when needed.
  • No mutation promise: Original order preserved in stacks.

Reflections: Like Spotify's true shuffle, efficient. For fun, add peek.

Advanced Alternatives: Recursive flip but risky stack overflow. Deque for cheat (but challenge forbids). Your queue trick? Share!

🚀 Next Steps and Resources

Day 61 mastered stack-to-queue. In #80DaysOfChallenges? Added size? Post!

Top comments (0)