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

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

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

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}")

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)

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!

• Source Code for Challenge #61: scripts/queue_via_stacks.py
• Main Repository: 80-days-of-challenges
• Daily Updates: Twitter/X (@Shahrouzlogs)

Comments

[rokoss21]

Classic problem, but very cleanly explained 👍
What I like here is that you don’t just show how the trick works, you implicitly teach why amortized analysis matters in real systems.

The “lazy flip” is a great mental model: pay the cost only when the invariant actually requires it. That idea shows up everywhere — caches, batching, compaction, even distributed systems — not just interview questions.

Also nice touch calling out the FIFO guarantee explicitly. A lot of people memorize this pattern without internalizing that correctness comes from invariants + controlled reversal, not from magic.

If someone really understands this example, they’re already thinking like an engineer, not just solving LeetCode. Keep going — these fundamentals compound.

[Shahrouz Nikseresht]

Thanks, I appreciate that. 🙌🏽✨

Highlighting the “pay the cost only when the invariant requires it” mindset was exactly the goal, more than the trick itself. Glad the correctness and FIFO reasoning came through.