Queue Data Structure in Python – Complete Tutorial with Examples

A queue is one of the most important data structures in computer science and follows the FIFO (First In, First Out) principle. In this tutorial, you'll learn how queues work in Python, understand operations such as enqueue and dequeue, compare different implementation methods, and explore practical applications including task scheduling, BFS traversal, rate limiting, and more.

Designed for both beginners and developers preparing for technical interviews, this tutorial covers:

Core Concepts & Architecture: How queues power everything from system schedulers to API rate limiters.
Implementations: From built-in lists to collections.deque and custom data structures built from scratch.
Real-World Applications: Step-by-step implementations for real-world scenarios.
Interview Prep & Patterns: In-depth solutions for classic questions like Circular Queues, Sliding Window Maximum, and BFS Grid Traversals.

What is a Queue?
Core Operations & Complexity
Implementing a Stack in Python (3 Ways)
Real-World Practical Problems
Interview Questions
Common Patterns to Remember
Practice Roadmap

Introduction

1. What Is Queue?

A Queue is a linear data structure that follows FIFO - First In, First Out. The first element added is the first one removed.

Real-World Analogy: A line at a coffee shop. The first person to join the line is the first person served. New customers join at the back, and service happens from the front - nobody gets served out of order (no cutting in line!).

Queue operations diagram showing enqueue and dequeue actions

Real systems/software that use queues internally:

Task/job scheduling: operating systems scheduling processes, print queues.
Message queues: systems like RabbitMQ, Kafka, AWS SQS for handling async tasks between services.
Message queues: breadth-first search in trees and graphs.
Request handling: web servers processing incoming requests in order.
Buffering: streaming data (video buffering, keyboard input buffering).
Call center / customer support systems: handling requests in the order they arrive.

2. Core Operations & Complexity

Before you write a single line of code, it helps to know exactly what a queue can do - and how fast each action really is. In this section, we break down the core queue operations in Python: enqueue(), dequeue(), peek(), is_empty(), and size(), along with their time and space complexity.

Operation	Description	Time Complexity	Space Complexity
`enqueue(x)`	Add element `x` to the back	`O(1)`	`O(1)`
`dequeue()`	Remove and return the front element	`O(1)*`	`O(1)`
`peek()` / `front()`	View the front element without removing it	`O(1)`	`O(1)`
`is_empty()`	Check if the queue has no elements	`O(1)`	`O(1)`
`size()`	Return count of elements	`O(1)`	`O(1)`
Overall structure	-	-	`O(n)` for `n` elements

Important: dequeue() is only O(1) with the right underlying structure (like deque or a linked list). Using a plain Python list and removing from index 0 is O(n) - this is a common beginner mistake, explained in Method 1 below.

3. Implementation

Learn how to implement a queue in Python with three practical methods: using a list (simple but inefficient), collections.deque (fast and recommended), and a custom dictionary-based queue (great for understanding internals). This section covers enqueue, dequeue, peek, and other core operations with clear code examples, time complexity explanations, and beginner-friendly insights. Perfect for Python learners and anyone preparing for DSA interviews who wants to build a solid foundation in queue data structures.

Method A: Using Python's built-in list (works, but inefficient)

Python

                            
class QueueUsingList:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)   # add to the END - O(1)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        # pop(0) removes from the FRONT, but every remaining element
        # has to shift left by one - this makes it O(n), not O(1)!
        return self.items.pop(0)

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty queue")
        return self.items[0]

    def is_empty(self):
        return len(self.items) == 0

    def size(self):
        return len(self.items)


q = QueueUsingList()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())   # 1
print(q.peek())      # 2
print(q.size())      # 2

Step-by-Step Explanation

1. What problem does it solve?

This builds a Queue - a waiting line where whoever arrived first gets served first. Just like a line at a coffee shop: you join at the back, and the person who's been waiting longest gets served next, from the front.

2. Step-by-step walkthrough

Setting up the line

                            
                    def __init__(self):
                        self.items = []

We start with an empty list.
This list represents the whole queue - no separate "front" or "back" pointer needed, since Python lists already know their own start and end.

Joining the line - enqueue

                            
                    def enqueue(self, item):
                        self.items.append(item)

New people always join at the back of the line.
append() adds to the end of the list - this is fast, because Python just writes the new item into the next free spot.

Leaving the line - dequeue

                            
                    def dequeue(self):
                        if self.is_empty():
                            raise IndexError("dequeue from empty queue")
                        return self.items.pop(0)

First, check if the line is even empty - if it is, there's nobody to remove, so it raises an error rather than pretending it worked.
pop(0) removes whoever is at position 0 - the very front of the line - and hands them back to you.
Important detail: once that front person leaves, everyone behind them has to step forward one spot to close the gap. That's what makes this operation slower than enqueue.

Checking who's next - peek

                            
                    def peek(self):
                        if self.is_empty():
                            raise IndexError("peek from empty queue")
                        return self.items[0]

Same empty-check as dequeue, but this only looks at the front person - it doesn't remove them.

Simple line stats

                            
                    def is_empty(self):
                        return len(self.items) == 0

                    def size(self):
                        return len(self.items)

is_empty - is the line empty right now?
size - how many people are currently waiting?

3. Why a queue fits this problem

Anything that needs "first come, first served" order - checkout lines, print jobs, customer support tickets - needs exactly this behavior: always add to the back, always remove from the front, so the order people arrived in is respected.

4. Visual diagram

enqueue(1)          enqueue(2)              enqueue(3)
┌───┐               ┌───┬───┐                ┌───┬───┬───┐
│ 1 │               │ 1 │ 2 │                │ 1 │ 2 │ 3 │
└───┘               └───┴───┘                └───┴───┴───┘
FRONT  BACK         FRONT     BACK            FRONT          BACK

dequeue() - removes 1 (the front), everyone else shifts forward
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
└───┴───┴───┘
  │  (1 leaves, 2 and 3 shift left to fill the gap)
  ▼
┌───┬───┐
│ 2 │ 3 │
└───┴───┘
FRONT   BACK
returned: 1

peek() - just looks at the front, nobody leaves
┌───┬───┐
│ 2 │ 3 │   →  returns 2  (queue unchanged: [2, 3])
└───┴───┘

size() - counts how many are waiting
┌───┬───┐
│ 2 │ 3 │   →  returns 2
└───┴───┘

5. Trace through the successful run

Step	Action	What happens	Queue state after	Returned / printed
1	`q.enqueue(1)`	1 joins the back	`[1]`	-
2	`q.enqueue(2)`	2 joins the back	`[1, 2]`	-
3	`q.enqueue(3)`	3 joins the back	`[1, 2, 3]`	-
4	`q.dequeue()`	1 leaves from front; 2 and 3 shift forward	`[2, 3]`	`1`
5	`q.peek()`	Look at front, nobody removed	`[2, 3] (unchanged)`	`2`
6	`q.size()`	Count items	`[2, 3] (unchanged)`	`2`

6. Trace through the failing case

                            
                    q2 = QueueUsingList()
                    q2.dequeue()

Start: Queue is empty ([])
Check: is_empty() returns True
Result: Stops immediately - raises IndexError("dequeue from empty queue")

It fails right at the empty-check, before ever trying to touch self.items[0] - this is intentional, so you get a clear error message instead of a confusing crash.

7. Summary

New people join the back of the line and the person who's been waiting longest always leaves from the front - but because leaving from the front means everyone else has to step forward, this "line" gets a little more work every time someone's served, compared to adding a new person.

Why show this if it's inefficient?

It's the most intuitive first version, and understanding why pop(0) is slow is exactly what leads you to Method 2.

Method B: Using `collections.deque` (the recommended approach)

Python

                            
from collections import deque

# deque (double-ended queue) is implemented internally as a doubly
# linked list of blocks, giving guaranteed O(1) operations at BOTH
# ends - this fixes the O(n) problem from Method 1.
queue = deque()

queue.append(1)        # enqueue - add to the back
queue.append(2)
queue.append(3)

print(queue.popleft())   # 1 - dequeue, removes from the FRONT in O(1)
print(queue[0])           # 2 - peek at the front
print(len(queue))         # 2 - size

Step-by-Step Explanation

1. What problem does it solve?

This builds a queue using Python's built-in deque - a waiting line where whoever arrived first gets served first. Same idea as your earlier QueueUsingList, but this time using a tool specially built by Python for this job, instead of a plain list.

2. Step-by-step walkthrough

Importing deque

                                
                        from collections import deque

deque (pronounced "deck," short for double-ended queue) is a ready-made structure from Python's standard library.
Nobody had to build Node classes or write .next pointers by hand - Python already provides this.

Creating the queue

                                
                        queue = deque()

Creates an empty deque - an empty line, ready for people to join.

Adding to the queue - enqueue

                                
                        queue.append(1)        # enqueue - add to the back
                        queue.append(2)
                        queue.append(3)

append() adds each new item to the back - same idea as enqueue from before.
deque uses the same method name Python lists use for "add to the end," so it feels familiar if you've used lists.

Removing from the queue - dequeue

                                
                        print(queue.popleft())   # 1 - dequeue, removes from the FRONT

popleft() removes and returns whoever is at the front - this is the "dequeue" operation.
The name literally says what it does: "pop from the left side" (the front).

Peeking at the front

                                
                        print(queue[0])           # 2 - peek at the front

queue[0] looks at the front item without removing it - same as peek from before, just written using indexing directly instead of a separate method.

Checking size

                                
                        print(len(queue))         # 2 - size

len() works on a deque exactly like it works on a list - tells you how many items are currently in it.

3. Why deque fits this problem better than a plain list

A deque is built internally so that both ends - front and back - are fast to add to or remove from. Unlike a plain Python list (where removing from the front means shifting every other item over), a deque is designed from the ground up so nothing needs to shift, no matter which end you're working with. That's exactly what a queue needs: fast joins at the back, fast departures from the front.

4. Visual diagram - the successful run

append(1)          append(2)               append(3)
┌───┐               ┌───┬───┐                ┌───┬───┬───┐
│ 1 │               │ 1 │ 2 │                │ 1 │ 2 │ 3 │
└───┘               └───┴───┘                └───┴───┴───┘
FRONT  BACK         FRONT     BACK            FRONT          BACK

popleft() - removes 1 from the front, NOTHING else has to shift
┌───┬───┬───┐
│ 1 │ 2 │ 3 │
└───┴───┴───┘
│  (1 leaves - 2 simply becomes the new front, no shifting needed)
▼
┌───┬───┐
│ 2 │ 3 │
└───┴───┘
FRONT   BACK
returned: 1

queue[0] - just looks at the front, nobody leaves
┌───┬───┐
│ 2 │ 3 │   →  returns 2  (queue unchanged: deque([2, 3]))
└───┴───┘

len(queue) - counts how many are waiting
┌───┬───┐
│ 2 │ 3 │   →  returns 2
└───┴───┘

5. Trace table - same successful run

Step	Action	What happens	Queue state after	Returned / printed
1	`queue.append(1)`	1 joins the back	`deque([1])`	-
2	`queue.append(2)`	2 joins the back	`deque([1, 2])`	-
3	`queue.append(3)`	3 joins the back	`deque([1, 2, 3])`	-
4	`queue.popleft()`	1 leaves from front, no shifting needed	`deque([2, 3])`	`1`
5	`queue[0]`	Look at front, nobody removed	`deque([2, 3]) (unchanged)`	`2`
6	`len(queue)`	Count items	`deque([2, 3]) (unchanged)`	`2`

This matches the program's printed output exactly: 1, then 2, then 2 - same result as QueueUsingList, just reached without the shifting cost.

6. Second trace - a failing case: popleft() on an empty deque

                                
                        empty_queue = deque()
                        empty_queue.popleft()

Step	Action	Check	Result
1	`empty_queue = deque()`	-	`deque is deque([])`
2	`empty_queue.popleft()`	deque has nothing in it	stops immediately - raises `IndexError("pop from an empty deque")`

Unlike your earlier QueueUsingList, this error message comes built into Python itself - deque already handles the empty-check internally, so you don't have to write is_empty() guards by hand to get a clear failure.

7. Summary

People join the back and leave from the front, just like the earlier list-based queue - except deque is specially built so both ends are equally fast, so nobody else in line has to "shift" when someone leaves from the front.

Method 3: From Scratch Using a Dictionary (Beginner Version)

Python

                            
class DictQueue:
    def __init__(self):
        self.storage = {}   # dictionary: slot_number -> value
        self.front = 0      # points to the NEXT item to be removed
        self.rear = 0       # points to the NEXT empty slot to fill

    def enqueue(self, value):
        # Place the value in the next available slot, then move rear forward
        self.storage[self.rear] = value
        self.rear += 1

    def dequeue(self):
        if self.is_empty():
            print("Queue is empty, nothing to dequeue")
            return None

        # Grab the value at the front slot
        value = self.storage[self.front]

        # Remove it from the dictionary so memory doesn't pile up
        del self.storage[self.front]

        # Move front forward to point at the next item in line
        self.front += 1

        return value

    def peek(self):
        if self.is_empty():
            print("Queue is empty")
            return None
        return self.storage[self.front]

    def is_empty(self):
        # Empty when front has caught up to rear (no items left between them)
        return self.front == self.rear

    def size(self):
        return self.rear - self.front


# Let's try it out
q = DictQueue()

q.enqueue("A")   # storage: {0: "A"}
q.enqueue("B")   # storage: {0: "A", 1: "B"}
q.enqueue("C")   # storage: {0: "A", 1: "B", 2: "C"}

print(q.dequeue())   # A  -> slot 0 removed, front moves to 1
print(q.peek())      # B  -> next in line
print(q.dequeue())   # B  -> slot 1 removed, front moves to 2
print(q.size())      # 1  -> only C left, in slot 2

Step-by-Step Explanation

1. What problem does it solve?

This builds a queue - same FIFO waiting-line idea as before - but using a dictionary with two pointers (front and rear) instead of a list or deque. Think of it like numbered lockers in a hallway: each new person gets the next numbered locker, and whoever's at the lowest numbered occupied locker is served next - nobody physically moves lockers, we just track which numbers are still in use.

2. Step-by-step walkthrough

Constructor - setting up storage and pointers

                                
                        def __init__(self):
                            self.storage = {}
                            self.front = 0
                            self.rear = 0

storage is a dictionary - each key is a "slot number," each value is the item sitting in that slot.
front - the slot number of the next item to be removed.
rear - the slot number where the next new item will go.
Both start at 0 because the queue is empty - nobody's been placed yet.

Joining the line - enqueue

                                
                        def enqueue(self, value):
                            self.storage[self.rear] = value
                            self.rear += 1

Put the new value into slot number rear.
Then bump rear up by 1, so the next enqueue goes into the next slot - this is exactly why nothing ever needs to shift: each item gets a permanent slot number for life, and we simply move forward.

Leaving the line - dequeue

                                
                        def dequeue(self):
                            if self.is_empty():
                                print("Queue is empty, nothing to dequeue")
                                return None

                            value = self.storage[self.front]
                            del self.storage[self.front]
                            self.front += 1
                            return value

Check if the queue's empty first - if so, print a message and return None instead of crashing.
Otherwise: grab whatever's sitting in slot front - that's the item that's been waiting longest.
del self.storage[self.front] - remove that entry from the dictionary entirely, so memory doesn't quietly pile up with old, already-served slots.
Move front forward by 1, so it now points at the next item in line.
Return the value we grabbed.

Checking who's next - peek

                                
                        def peek(self):
                            if self.is_empty():
                                print("Queue is empty")
                                return None
                            return self.storage[self.front]

Same empty-check, but this just looks at slot front without deleting it or moving the pointer.

Checking empty state

                                
                        def is_empty(self):
                            return self.front == self.rear

The queue is empty exactly when front has "caught up" to rear - meaning there's no gap left between "next to remove" and "next empty slot," so nothing is waiting in between.

Queue size

                                
                        def size(self):
                            return self.rear - self.front

The number of items currently waiting is just the gap between these two pointers - no need to count anything directly.

3. Why this data structure fits

A dictionary here works like an array of numbered lockers rather than a line of people who have to physically shuffle forward. Because every item gets its own permanent slot number, removing the front item never requires moving anyone else - you just delete that one dictionary entry and nudge the front pointer. This avoids the shifting cost of the plain-list queue, without needing Python's built-in deque.

4. Visual diagram - the successful run

START
front = 0, rear = 0

      front/rear
          ↓
          0
       [empty]

enqueue("A")
front                 rear
  ↓                     ↓
  0                     1
┌─────┐
│  A  │
└─────┘

enqueue("B")
front                         rear
  ↓                             ↓
  0             1               2
┌─────┐       ┌─────┐
│  A  │       │  B  │
└─────┘       └─────┘

enqueue("C")
front                                      rear
  ↓                                          ↓
  0             1             2              3
┌─────┐       ┌─────┐       ┌─────┐
│  A  │       │  B  │       │  C  │
└─────┘       └─────┘       └─────┘

dequeue() → A
                front                       rear
                  ↓                           ↓
  0             1             2               3
┌─────┐       ┌─────┐       ┌─────┐
│empty│       │  B  │       │  C  │
└─────┘       └─────┘       └─────┘

peek() → B
                front                       rear
                  ↓                           ↓
  0             1             2               3
┌─────┐       ┌─────┐       ┌─────┐
│empty│       │  B  │       │  C  │
└─────┘       └─────┘       └─────┘
                  ↑
             only looking

dequeue() → B
                              front          rear
                                ↓              ↓
  0             1             2               3
┌─────┐       ┌─────┐       ┌─────┐
│empty│       │empty│       │  C  │
└─────┘       └─────┘       └─────┘

Remaining item: C
size = 3 - 2 = 1

5. Trace table - same successful run

Step	Action	What happens	storage after	front	rear	Returned / printed
1	`q.enqueue("A")`	"A" placed in slot 0, rear moves to 1	`{0:"A"}`	0	1	-
2	`q.enqueue("B")`	"B" placed in slot 1, rear moves to 2	`{0:"A", 1:"B"}`	0	2	-
3	`q.enqueue("C")`	"C" placed in slot 2, rear moves to 3	`{0:"A", 1:"B", 2:"C"}`	0	3	-
4	`q.dequeue()`	grab slot 0 ("A"), delete it, front moves to 1	`{1:"B", 2:"C"}`	1	3	`A`
5	`q.peek()`	look at slot 1 ("B"), nothing removed	`{1:"B", 2:"C"} (unchanged)`	1	3	`B`
6	`q.dequeue()`	grab slot 1 ("B"), delete it, front moves to 2	`{2:"C"}`	2	3	`B`
7	`q.size()`	rear - front = 3 - 2	`{2:"C"} (unchanged)`	2	3	`1`

This matches the program's printed output exactly: A, B, B, 1.

6. Second trace - a failing case: dequeue() on an empty queue

                                
                        empty_q = DictQueue()
                        empty_q.dequeue()

Step	Action	Check	Result
1	`empty_q = DictQueue()`	-	`storage={}, front=0, rear=0`
2	`empty_q.dequeue()`	`front == rear → True`	prints a message, returns `None` - no crash, no `IndexError`

7. Summary

Every item gets its own permanent numbered slot in a dictionary; enqueue hands out the next slot number and moves rear forward, while dequeue removes whatever's in the front slot and moves front forward - so nothing ever needs to shift, we just track two moving pointers instead.

This is genuinely different from Method 1 (list + shifting problem) and Method 2 (deque) - it shows a third way to think about storage entirely, using key-based lookup instead of position-based lists.

4. Real-World Practical Problems

Problem 1: Print Job / Task Scheduler

Use case:A printer processes jobs in the order they were submitted - first requested, first printed.

Python

                                
from collections import deque

class PrintQueue:
    def __init__(self):
        self.jobs = deque()

    def submit_job(self, document_name):
        self.jobs.append(document_name)
        print(f"'{document_name}' added to print queue")

    def print_next(self):
        if not self.jobs:
            print("No jobs in queue")
            return
        job = self.jobs.popleft()
        print(f"Printing: {job}")


printer = PrintQueue()
printer.submit_job("Report.pdf")
printer.submit_job("Invoice.docx")
printer.print_next()   # Printing: Report.pdf
printer.print_next()   # Printing: Invoice.docx

Step-by-Step Explanation

1. What problem does it solve?

It solves the “printer line” problem: multiple people send print jobs, but the printer should handle them first-come, first-served, like people waiting in a queue at a shop counter.

2. Step-by-step walkthrough

Import and class setup

                                    
from collections import deque

class PrintQueue:
    def __init__(self):
        self.jobs = deque()

deque (pronounced “deck”) is a double-ended queue from Python's standard library, optimized for adding/removing from both ends.
self.jobs is the internal queue that will hold document names in order.

Using deque is ideal here because we'll append at the right end and remove from the left end efficiently, which matches how a real print queue works.

Submit a job (add to the back)

                                    
def submit_job(self, document_name):
    self.jobs.append(document_name)
    print(f"'{document_name}' added to print queue")

append(document_name) adds the new document to the right end of the queue (the back of the line).
Then it prints a message confirming the job was added.

Each new print request joins the end of the line, behind any existing jobs.

Print the next job (remove from the front)

                                    
def print_next(self):
    if not self.jobs:
        print("No jobs in queue")
        return
    job = self.jobs.popleft()
    print(f"Printing: {job}")

if not self.jobs: checks whether the queue is empty.
If it's empty, it prints “No jobs in queue” and stops.
Otherwise, popleft() removes and returns the leftmost item, which is the oldest job (the one that's been waiting the longest).
It then prints which document is being printed.

This ensures jobs are printed in the exact order they were submitted.

Using the queue

                                    
printer = PrintQueue()
printer.submit_job("Report.pdf")
printer.submit_job("Invoice.docx")
printer.print_next()  # Printing: Report.pdf
printer.print_next()  # Printing: Invoice.docx

Create a PrintQueue object called printer.
Submit "Report.pdf" → queue: ["Report.pdf"].
Submit "Invoice.docx" → queue: ["Report.pdf", "Invoice.docx"].
First print_next() removes and prints "Report.pdf" (the first submitted).
Second print_next() removes and prints "Invoice.docx" (the next in line).

3. Why a queue (and deque) fits this problem

A queue is exactly right for “first-in, first-out” scenarios like print jobs, task schedulers, or message inboxes. deque is used instead of a plain list because removing from the front (popleft) is fast and efficient, while a list's pop(0) would be slower for many items.

4. Visual diagram - successful example

submit_job("Report.pdf")          submit_job("Invoice.docx")
┌─────────────┐                    ┌─────────────┬──────────────┐
│ Report.pdf  │                    │ Report.pdf  │ Invoice.docx │
└─────────────┘                    └─────────────┴──────────────┘
FRONT/BACK                         FRONT             BACK


print_next() → removes Report.pdf from the front
┌─────────────┬──────────────┐
│ Report.pdf  │ Invoice.docx │
└─────────────┴──────────────┘
    │
    ▼  (Report.pdf leaves, Invoice.docx becomes new front)
┌──────────────┐
│ Invoice.docx │
└──────────────┘
    FRONT/BACK
Printed: Report.pdf


print_next() → removes Invoice.docx, queue now empty
┌──────────────┐
│ Invoice.docx │
└──────────────┘
    │
    ▼
┌ ─ ─ ─ ─ ┐
│ (empty) │
└ ─ ─ ─ ─ ┘
Printed: Invoice.docx

5. Trace table - successful run

Step	Operation	Action taken	Resulting state (`jobs`)
1	`printer = PrintQueue()`	Create empty queue	`deque([])`
2	`printer.submit_job("Report.pdf")`	Append `"Report.pdf"` to right end	`deque(["Report.pdf"])`
3	`printer.submit_job("Invoice.docx")`	Append `"Invoice.docx"` to right end	`deque(["Report.pdf", "Invoice.docx"])`
4	`printer.print_next()`	Queue not empty; `popleft()` → `"Report.pdf"`, print it	`deque(["Invoice.docx"])`
5	`printer.print_next()`	Queue not empty; `popleft()` → `"Invoice.docx"`, print it	`deque([])`

6. Trace for a failing example (printing when empty)

Now try to print when there are no jobs.

Setup & Operation

                                    
printer = PrintQueue()
# jobs: deque([])

printer.print_next()

Step	Operation	Action taken	Resulting state / note
1	`printer = PrintQueue()`	Create empty queue	`deque([])`
2	`printer.print_next()`	`if not self.jobs` is True → print "No jobs in queue" and return	State unchanged; operation fails because queue is empty

It fails at step 2 because the queue is empty, so there's no job to print.

7. Summary

This code builds a first-come, first-served print queue using deque, so documents are added at the back and printed from the front in the exact order they were submitted.

Problem 2: Customer Support Ticket System

Use case: Support tickets get handled in the order customers submitted them, ensuring fairness (first come, first served).

Python

                                
from collections import deque

class SupportQueue:
    def __init__(self):
        self.tickets = deque()

    def new_ticket(self, customer_name, issue):
        self.tickets.append({"customer": customer_name, "issue": issue})

    def handle_next_ticket(self):
        if not self.tickets:
            print("No tickets waiting")
            return
        ticket = self.tickets.popleft()
        print(f"Helping {ticket['customer']} with: {ticket['issue']}")


support = SupportQueue()
support.new_ticket("Alice", "Can't reset password")
support.new_ticket("Bob", "App keeps crashing")
support.handle_next_ticket()   # Helping Alice with: Can't reset password
support.handle_next_ticket()   # Helping Bob with: App keeps crashing

Step-by-Step Explanation

1. What problem does it solve?

It solves the “support line” problem: many customers report issues, but the team should help them first-come, first-served, like people waiting in a single line at a help desk.

2. Step-by-step walkthrough

Import and class setup

                                    
                            from collections import deque

                            class SupportQueue:
                                def __init__(self):
                                    self.tickets = deque()

deque (pronounced “deck”) is a double-ended queue from Python's standard library, optimized for adding/removing from both ends.
self.tickets is the internal queue that will hold ticket information in order.

Using deque is ideal here because we'll append at the right end and remove from the left end efficiently, which matches how a real support queue works.

Create a new ticket (add to the back)

                                    
                            def new_ticket(self, customer_name, issue):
                                self.tickets.append({"customer": customer_name, "issue": issue})

This method takes two inputs: the customer's name and a short description of their issue.
It creates a small dictionary (a key–value pair) like {"customer": "Alice", "issue": "Can't reset password"}.
append(...) adds this dictionary to the right end of the queue (the back of the line).

Each new support request joins the end of the line, behind any existing tickets.

Handle the next ticket (remove from the front)

                                    
                            def handle_next_ticket(self):
                                if not self.tickets:
                                    print("No tickets waiting")
                                    return
                                ticket = self.tickets.popleft()
                                print(f"Helping {ticket['customer']} with: {ticket['issue']}")

if not self.tickets: checks whether the queue is empty.
If it's empty, it prints “No tickets waiting” and stops.
Otherwise, popleft() removes and returns the leftmost item, which is the oldest ticket (the one that's been waiting the longest).
It then prints which customer is being helped and what their issue is, using the dictionary's "customer" and "issue" keys.

This ensures tickets are handled in the exact order they were created.

Using the queue

                                    
                            support = SupportQueue()
                            support.new_ticket("Alice", "Can't reset password")
                            support.new_ticket("Bob", "App keeps crashing")
                            support.handle_next_ticket()   # Helping Alice with: Can't reset password
                            support.handle_next_ticket()   # Helping Bob with: App keeps crashing

Create a SupportQueue object called support.
Add Alice's ticket → queue: [{"customer": "Alice", "issue": "Can't reset password"}].
Add Bob's ticket → queue: [Alice-ticket, {"customer": "Bob", "issue": "App keeps crashing"}].
First handle_next_ticket() removes and handles Alice's ticket (the first submitted).
Second handle_next_ticket() removes and handles Bob's ticket (the next in line).

3. Why a queue (and deque) fits this problem

A queue is exactly right for “first-in, first-out” scenarios like support tickets, print jobs, or task schedulers. deque is used instead of a plain list because removing from the front (popleft) is fast and efficient, while a list's pop(0) would be slower for many items.

4. Visual diagram - successful example

new_ticket("Alice", "Can't reset password")
┌──────────────────────────────┐
│ {Alice: Can't reset password}│
└──────────────────────────────┘
        FRONT/BACK


new_ticket("Bob", "App keeps crashing")
┌──────────────────────────────┬────────────────────────────┐
│ {Alice: Can't reset password}│ {Bob: App keeps crashing}  │
└──────────────────────────────┴────────────────────────────┘
        FRONT                                 BACK


handle_next_ticket() → removes Alice's ticket from the front
┌──────────────────────────────┬────────────────────────────┐
│ {Alice: Can't reset password}│ {Bob: App keeps crashing}  │
└──────────────────────────────┴────────────────────────────┘
    │
    ▼  (Alice's ticket leaves, Bob's becomes new front)
┌────────────────────────────┐
│ {Bob: App keeps crashing}  │
└────────────────────────────┘
        FRONT/BACK
Helping Alice with: Can't reset password


handle_next_ticket() → removes Bob's ticket, queue now empty
┌────────────────────────────┐
│ {Bob: App keeps crashing}  │
└────────────────────────────┘
    │
    ▼
┌ ─ ─ ─ ─ ┐
│ (empty) │
└ ─ ─ ─ ─ ┘
Helping Bob with: App keeps crashing

5. Trace table - successful run

Step	Operation	Action taken	Resulting state (`tickets`)
1	`support = SupportQueue()`	Create empty queue	`deque([])`
2	`new_ticket("Alice", "Can't reset password")`	Append Alice's ticket dict to right end	`deque([{"customer":"Alice","issue":"Can't reset password"}])`
3	`new_ticket("Bob", "App keeps crashing")`	Append Bob's ticket dict to right end	`deque([Alice-ticket, {"customer":"Bob","issue":"App keeps crashing"}])`
4	`handle_next_ticket()`	Queue not empty; `popleft()` → Alice-ticket, print “Helping Alice …”	`deque([{"customer":"Bob","issue":"App keeps crashing"}])`
5	`handle_next_ticket()`	Queue not empty; `popleft()` → Bob-ticket, print “Helping Bob …”	`deque([])`

6. Trace for a failing example (handling when empty)

Now try to handle a ticket when there are none.

Setup & Operation

                                    
                            support = SupportQueue()
                            # tickets: deque([])

                            support.handle_next_ticket()

Step	Operation	Action taken	Resulting state / note
1	`support = SupportQueue()`	Create empty queue	`deque([])`
2	`handle_next_ticket()`	`if not self.tickets` is True → print “No tickets waiting” and return	State unchanged; operation fails because queue is empty

It fails at step 2 because the queue is empty, so there's no ticket to handle.

7. Summary

Every new ticket joins the back of the line as a small bundle of customer info, and the support agent always works through tickets in the order customers reached out, helping one at a time from the front until the queue is empty.

Problem 3: Breadth-First Search (BFS) - Finding Shortest Path

Use case: Social networks use BFS to find "degrees of connection" (e.g., LinkedIn's "2nd/3rd connection"), and GPS systems use it for shortest routes in unweighted graphs.

Python

                                        
from collections import deque

def bfs_shortest_path(graph, start, target):
    # graph is a dict like {"A": ["B", "C"], "B": ["D"], ...}
    visited = {start}
    queue = deque([(start, [start])])   # (current_node, path_so_far)

    while queue:
        current, path = queue.popleft()   # process the OLDEST discovered node first

        if current == target:
            return path

        for neighbor in graph.get(current, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None   # no path found


social_network = {
    "Alice": ["Bob", "Carol"],
    "Bob": ["Alice", "Dave"],
    "Carol": ["Alice", "Eve"],
    "Dave": ["Bob", "Eve"],
    "Eve": ["Carol", "Dave"]
}

print(bfs_shortest_path(social_network, "Alice", "Eve"))
# ['Alice', 'Carol', 'Eve']  - shortest connection path

Step-by-Step Explanation

1. What problem does it solve?

It solves the “shortest friendship chain” problem: given who knows whom, it finds the smallest number of introductions needed to get from one person to another, and returns that chain of people.

2. Step-by-step walkthrough

Function and inputs

                                    
                            def bfs_shortest_path(graph, start, target):
                                # graph is a dict like {"A": ["B", "C"], "B": ["D"], ...}

graph is a dictionary where each key is a person, and the value is a list of their direct friends (neighbors).
start is the person we begin from.
target is the person we want to reach.

The function will return the shortest list of people from start to target, or None if no path exists.

Track visited people and the queue

                                    
                            visited = {start}
                            queue = deque([(start, [start])])   # (current_node, path_so_far)

visited is a set that remembers which people we've already seen, so we don't loop forever.
queue is a double-ended queue that stores pairs: (current_node, path_so_far).
We start with (start, [start]), meaning “we're at start, and the path so far is just [start]”.

Using a queue ensures we explore people in the order we discovered them, which is the key idea behind Breadth-First Search (BFS).

Main loop: process the oldest discovered node first

                                    
                            while queue:
                                current, path = queue.popleft()   # process the OLDEST discovered node first

while queue: means “keep going as long as there are people left to explore”.
queue.popleft() removes and returns the oldest entry in the queue (first-in, first-out).
current is the person we're looking at now; path is the list of people we took to get here.

Processing the oldest discovered node first guarantees we explore layer-by-layer: all friends, then friends-of-friends, and so on.

Check if we reached the target

                                    
                            if current == target:
                                return path

If the person we're currently at is the target, we've found a path.
Because BFS explores in layers, the first time we reach the target, it's guaranteed to be via the shortest path (fewest steps).
We immediately return path, which is the list of people from start to target.

Explore neighbors (friends) of the current person

                                    
                            for neighbor in graph.get(current, []):
                                if neighbor not in visited:
                                    visited.add(neighbor)
                                    queue.append((neighbor, path + [neighbor]))

graph.get(current, []) fetches the list of friends of current; if current isn't in the graph, it returns an empty list.
For each neighbor (friend):
- If we haven't visited them yet (neighbor not in visited), we mark them as visited with visited.add(neighbor).
- Add them to the queue with the updated path: path + [neighbor].

This builds longer and longer paths as we move outward, but only keeps each person once, avoiding cycles and repeated work.

No path found

                                    
                            return None   # no path found

If the queue becomes empty and we never hit the target, it means there's no way to reach target from start in this network.
In that case, we return None.

Example social network and call

                                    
                            social_network = {
                                "Alice": ["Bob", "Carol"],
                                "Bob": ["Alice", "Dave"],
                                "Carol": ["Alice", "Eve"],
                                "Dave": ["Bob", "Eve"],
                                "Eve": ["Carol", "Dave"]
                            }

                            print(bfs_shortest_path(social_network, "Alice", "Eve"))
                            # ['Alice', 'Carol', 'Eve']

The graph says: Alice knows Bob and Carol; Bob knows Alice and Dave; Carol knows Alice and Eve; Dave knows Bob and Eve; Eve knows Carol and Dave.
We ask for the shortest path from "Alice" to "Eve".
BFS first sees Alice's friends: Bob and Carol.
From Carol, it immediately sees Eve, so the path ['Alice', 'Carol', 'Eve'] is found and returned.

3. Why a queue (and BFS) fits this problem

A queue gives us first-in, first-out ordering, which makes BFS explore nodes level-by-level: all people at distance 1, then distance 2, and so on. This layer-by-layer search is exactly what guarantees the first path we find to the target is the shortest in terms of number of steps.

4. Visual diagram - successful example (Alice → Eve)

social_network:
Alice ── Bob ── Dave
    │             │
Carol ───────── Eve

Start: Alice, Target: Eve


Step 1: queue = [(Alice, [Alice])]
visited = {Alice}

pop Alice → not target
friends: Bob, Carol (neither visited)
┌─────────────────────────────────────┐
│ queue: [(Bob,[A,B]), (Carol,[A,C])] │
└─────────────────────────────────────┘
visited = {Alice, Bob, Carol}


Step 2: pop Bob → not target
friends: Alice (visited, skip), Dave (new)
┌───────────────────────────────────────────────────┐
│ queue: [(Carol,[A,C]), (Dave,[A,B,D])]            │
└───────────────────────────────────────────────────┘
visited = {Alice, Bob, Carol, Dave}


Step 3: pop Carol → not target
friends: Alice (visited, skip), Eve (new!)
┌───────────────────────────────────────────────────────────┐
│ queue: [(Dave,[A,B,D]), (Eve,[A,C,E])]                    │
└───────────────────────────────────────────────────────────┘
visited = {Alice, Bob, Carol, Dave, Eve}


Step 4: pop Dave → not target (already found a shorter path to Eve, but
        Dave was queued before Eve, so we still process him first)
friends: Bob (visited), Eve (already visited, skip)
┌───────────────────────────────┐
│ queue: [(Eve,[A,C,E])]        │
└───────────────────────────────┘


Step 5: pop Eve → MATCH! target found
return ['Alice', 'Carol', 'Eve']

5. Trace table - successful run (Alice → Eve)

Step	Operation	Action taken	Resulting state (visited, queue)
1	Initialize	`visited = {Alice}`, `queue = [(Alice, [Alice])]`	`visited={Alice}`, `queue=[(Alice,[Alice])]`
2	Pop (Alice, [Alice])	Not target; explore Bob, Carol	`visited={Alice,Bob,Carol}`, `queue=[(Bob,[A,B]), (Carol,[A,C])]`
3	Pop (Bob, [Alice, Bob])	Not target; explore Alice (skip), Dave	`visited={A,B,C,D}`, `queue=[(Carol,[A,C]), (Dave,[A,B,D])]`
4	Pop (Carol, [Alice, Carol])	Not target; explore Alice (skip), Eve → enqueue	`visited={A,B,C,D,E}`, `queue=[(Dave,[A,B,D]), (Eve,[A,C,E])]`
5	Pop (Dave, [Alice, Bob, Dave])	Not target; neighbors Bob, Eve already visited → no new enqueues	`visited={A,B,C,D,E}`, `queue=[(Eve,[A,C,E])]`
6	Pop (Eve, [Alice, Carol, Eve])	Eve == target → return path	Returns `['Alice', 'Carol', 'Eve']`

6. Trace for a failing example (no path exists)

Imagine a disconnected network where Eve is in a separate group:

                                    
                            social_network = {
                                "Alice": ["Bob"],
                                "Bob": ["Alice"],
                                "Carol": ["Dave"],
                                "Dave": ["Carol"],
                                "Eve": []
                            }

                            bfs_shortest_path(social_network, "Alice", "Eve")

Step	Operation	Action taken	Resulting state / note
1	Initialize	`visited = {Alice}`, `queue = [(Alice, [Alice])]`	`visited={Alice}`, `queue=[(Alice,[Alice])]`
2	Pop (Alice, [Alice])	Not target; neighbors: Bob → enqueue	`visited={Alice,Bob}`, `queue=[(Bob,[A,B])]`
3	Pop (Bob, [Alice, Bob])	Not target; neighbors: Alice (already visited) → nothing new	`visited={Alice,Bob}`, `queue=[]`
4	Queue empty	Loop ends; return `None`	No path found; function returns `None`

It fails to find a path because Eve is in a separate component with no connections to Alice or Bob, so the queue empties before reaching her.

7. Summary

Starting from one person, BFS explores everyone one hop away first, then two hops away, and so on - using a queue to always process the oldest discovery first - which guarantees the very first time the target is found, it's found by the shortest possible path.

Problem 4: Rate Limiter (Sliding Window)

Use case: APIs limit how many requests a user can make in a given time window (e.g., max 5 requests per 10 seconds) - a queue tracks recent request timestamps.

Python

                                        
from collections import deque
import time

class RateLimiter:
    def __init__(self, max_requests, window_seconds):
        self.max_requests = max_requests
        self.window_seconds = window_seconds
        self.timestamps = deque()

    def allow_request(self):
        now = time.time()

        # Remove timestamps that have fallen outside the time window
        while self.timestamps and now - self.timestamps[0] > self.window_seconds:
            self.timestamps.popleft()

        if len(self.timestamps) < self.max_requests:
            self.timestamps.append(now)
            return True   # request allowed

        return False   # rate limit exceeded


limiter = RateLimiter(max_requests=3, window_seconds=10)
print(limiter.allow_request())   # True
print(limiter.allow_request())   # True
print(limiter.allow_request())   # True
print(limiter.allow_request())   # False - limit hit within the window

Step-by-Step Explanation

1. What problem does it solve?

It solves the too many requests too fast problem: it ensures that no more than a set number of requests are allowed within a rolling time period, protecting servers from overload or abuse.

2. Step-by-step walkthrough

Imports and class setup

                                    
                            from collections import deque
                            import time

                            class RateLimiter:
                                def __init__(self, max_requests, window_seconds):
                                    self.max_requests = max_requests
                                    self.window_seconds = window_seconds
                                    self.timestamps = deque()

deque is a double-ended queue optimized for adding/removing from both ends.
time.time() gives the current time as a number (seconds since a fixed point).
max_requests is the maximum number of allowed requests in the time window.
window_seconds is how long the time window lasts (e.g., 10 seconds).
self.timestamps will store the times (timestamps) of recent allowed requests, in order.

We use a queue of timestamps so we can efficiently drop old ones and count only the recent requests.

Check if a new request is allowed

                                    
                            def allow_request(self):
                                now = time.time()

When someone tries to make a request, we first get the current time as now.

This timestamp will be used to decide if older requests are still “inside” the time window.

Remove old timestamps outside the window

                                    
                            while self.timestamps and now - self.timestamps[0] > self.window_seconds:
                                self.timestamps.popleft()

self.timestamps[0] is the oldest stored timestamp (the front of the queue).
now - self.timestamps[0] is how many seconds ago that oldest request happened.
If that difference is greater than window_seconds, the request is too old and should no longer count.
The while loop keeps removing the oldest timestamps until all remaining ones are within the last window_seconds.

This keeps the queue “sliding”: it always represents requests in the most recent time window.

Decide whether to allow or block the request

                                    
                            if len(self.timestamps) < self.max_requests:
                                self.timestamps.append(now)
                                return True   # request allowed

                            return False   # rate limit exceeded

len(self.timestamps) is how many requests are currently inside the time window.
If that number is less than max_requests, we add the current time now to the queue as a new allowed request and return True.
Otherwise, we've already used up all allowed requests in this window, so we return False to block it.

This enforces the rule: “at most max_requests in any rolling window_seconds period.”

Example usage

                                    
                            limiter = RateLimiter(max_requests=3, window_seconds=10)
                            print(limiter.allow_request())   # True
                            print(limiter.allow_request())   # True
                            print(limiter.allow_request())   # True
                            print(limiter.allow_request())   # False - limit hit within the window

We create a limiter that allows 3 requests per 10 seconds.
First call: queue is empty → allow, store timestamp → True.
Second call: 1 request in window → allow, store timestamp → True.
Third call: 2 requests in window → allow, store timestamp → True.
Fourth call: now 3 requests are already in the 10-second window → cannot add more → False.

If you wait until the oldest timestamp becomes older than 10 seconds, it will be removed and a new request can be allowed again.

3. Why a queue of timestamps fits this problem

A queue naturally stores events in the order they happened, which is exactly what we need to track request times. By removing old timestamps from the front and adding new ones at the back, we maintain a sliding window of recent requests and can enforce the rate limit efficiently.

4. Visual diagram - 4 rapid calls (limit = 3 in 10s)

Assume all four calls happen almost instantly, so now is roughly the same for each.

Setup: max_requests=3, window_seconds=10
timestamps: (empty)


allow_request() #1  →  time = 100.0
cleanup: nothing to remove (queue empty)
len(timestamps) = 0 < 3  →  ALLOWED
┌───────┐
│ 100.0 │
└───────┘
return: True


allow_request() #2  →  time = 100.1
cleanup: 100.0 is still within 10s window → keep it
len(timestamps) = 1 < 3  →  ALLOWED
┌───────┬───────┐
│ 100.0 │ 100.1 │
└───────┴───────┘
return: True


allow_request() #3  →  time = 100.2
cleanup: both still within window → keep them
len(timestamps) = 2 < 3  →  ALLOWED
┌───────┬───────┬───────┐
│ 100.0 │ 100.1 │ 100.2 │
└───────┴───────┴───────┘
return: True


allow_request() #4  →  time = 100.3
cleanup: all 3 still within window → keep them
len(timestamps) = 3, NOT < 3  →  BLOCKED
┌───────┬───────┬───────┐
│ 100.0 │ 100.1 │ 100.2 │   ← nothing added, timestamp NOT recorded
└───────┴───────┴───────┘
return: False

If enough time passes (more than 10 seconds after t1), then t1 will be removed, and a new request can be allowed again.

5. Trace table - successful run (4 rapid calls)

Step	Operation	Action taken	Resulting state (`timestamps`) and return value
1	Create limiter	`max_requests=3`, `window_seconds=10`, `timestamps=[]`	`deque([])`
2	`allow_request()` #1	No old entries; `len=0 < 3` → append `t1`, return `True`	`deque([t1])`, returns `True`
3	`allow_request()` #2	No old entries; `len=1 < 3` → append `t2`, return `True`	`deque([t1, t2])`, returns `True`
4	`allow_request()` #3	No old entries; `len=2 < 3` → append `t3`, return `True`	`deque([t1, t2, t3])`, returns `True`
5	`allow_request()` #4	No old entries; `len=3` not < 3 → do not append, return `False`	`deque([t1, t2, t3])`, returns `False`

6. Trace for a failing example (request blocked, then allowed after window)

Assume: t1, t2, t3 are at time 0, 1, 2 seconds. Next call happens at time 15 seconds.

Step	Time (s)	Operation	Action taken	Resulting state / note
1	0	`allow_request()` #1	Append `t1=0` → `True`	`deque([0])`
2	1	`allow_request()` #2	Append `t2=1` → `True`	`deque([0,1])`
3	2	`allow_request()` #3	Append `t3=2` → `True`	`deque([0,1,2])`
4	3	`allow_request()` #4	`now=3`; `3 - 0 = 3 ≤ 10` → no removal; `len=3` → `False` (blocked)	`deque([0,1,2])`, returns `False`
5	15	`allow_request()` #5	`now=15`; remove `0` (15-0>10), then `1` (15-1>10), then `2` (15-2>10)	`deque([])` after removals
6	15	(same call continued)	Now `len=0 < 3` → append `15`, return `True`	`deque([15])`, returns `True` (allowed after window expired)

It fails at step 4 because all three timestamps are still within the 10-second window, so the limit is hit; it succeeds at step 6 because enough time has passed that all old timestamps are removed, freeing space for a new request.

7. Summary

Every allowed request's timestamp gets remembered in a queue; before allowing a new one, old timestamps that have "expired" past the time window are cleared from the front, and a new request is only let through if there's still room left under the limit.

5. Interview Questions

These come up frequently in coding interviews. Difficulty increases as you go down the list.

Q1 (Easy): Moving Average from a Data Stream

Problem: Given a stream of integers arriving one at a time and a window size, return the moving average of the last k values seen so far.

Key idea: A queue is a natural fit for "the last k things that happened" - enqueue each new value, and once the queue exceeds size k, dequeue the oldest one so the window stays fixed.

Python

                        
from collections import deque

class MovingAverage:
    def __init__(self, size):
        self.size = size
        self.window = deque()
        self.window_sum = 0   # track the running sum so we don't re-add every time

    def next(self, value):
        self.window.append(value)
        self.window_sum += value

        # Once the window is too big, drop the oldest value
        if len(self.window) > self.size:
            oldest = self.window.popleft()
            self.window_sum -= oldest

        return self.window_sum / len(self.window)


ma = MovingAverage(3)
print(ma.next(1))   # 1.0   -> average of [1]
print(ma.next(10))  # 5.5   -> average of [1, 10]
print(ma.next(3))   # 4.67  -> average of [1, 10, 3]
print(ma.next(5))   # 6.0   -> average of [10, 3, 5], 1 has been dropped

Step-by-Step Explanation

1. What problem does it solve?

It solves the recent average problem: instead of averaging all history, it only considers the most recent values (like the last 3 sensor readings or stock prices) so the average reflects current behavior.

2. Step-by-step walkthrough

Imports and class setup

                                
                        from collections import deque

                        class MovingAverage:
                            def __init__(self, size):
                                self.size = size
                                self.window = deque()
                                self.window_sum = 0   # track the running sum so we don't re-add every time

deque is a double-ended queue optimized for adding/removing from both ends.
size is how many recent numbers we want to include in the average (the window size).
self.window will store the recent numbers in order.
self.window_sum keeps a running total of the numbers currently in the window.

Tracking the sum separately avoids re-adding all numbers every time, making each update fast.

Add a new number and update the sum

                                
                        def next(self, value):
                            self.window.append(value)
                            self.window_sum += value

When a new number (value) arrives, we add it to the right end of the queue.
We also add it to window_sum so the sum always matches the numbers currently in the window.

At this point, the window might be temporarily larger than size, which we fix next.

Drop the oldest number if the window is too big

                                
                        if len(self.window) > self.size:
                            oldest = self.window.popleft()
                            self.window_sum -= oldest

len(self.window) is how many numbers are currently stored.
If this count exceeds self.size, we remove the oldest number from the left end using popleft().
We subtract that oldest number from window_sum so the sum stays consistent with the remaining numbers.

This keeps exactly the last size numbers in the window, sliding forward each time a new value arrives.

Compute and return the current average

                                
                        return self.window_sum / len(self.window)

The average is simply the current sum divided by the current count of numbers in the window.
Because we maintain window_sum and the window contents, this calculation is quick and always up to date.

Example usage

                                
                        ma = MovingAverage(3)
                        print(ma.next(1))   # 1.0   -> average of [1]
                        print(ma.next(10))  # 5.5   -> average of [1, 10]
                        print(ma.next(3))   # 4.67  -> average of [1, 10, 3]
                        print(ma.next(5))   # 6.0   -> average of [10, 3, 5], 1 has been dropped

We create a moving average that considers the last 3 numbers.
First call with 1: window = [1] → average = 1 / 1 = 1.0.
Second call with 10: window = [1, 10] → average = (1+10) / 2 = 5.5.
Third call with 3: window = [1, 10, 3] → average = (1+10+3) / 3 ≈ 4.67.
Fourth call with 5:
- Add 5 → window becomes [1, 10, 3, 5] (temporarily size 4).
- Since size > 3, remove oldest 1 → window = [10, 3, 5], sum updated accordingly.
- Average = (10+3+5) / 3 = 18 / 3 = 6.0.

3. Why a queue of numbers fits this problem

A queue naturally stores values in the order they arrived, which is exactly what we need for a sliding window of “most recent N”. By removing from the front when the window is too big and adding to the back for new values, we maintain a correct, up-to-date window with minimal work.

4. Visual diagram - values 1, 10, 3, 5 with size=3

MovingAverage(3)  →  window can hold at most 3 numbers

next(1)
window: [1]                       sum = 1
                                average = 1 / 1 = 1.0

next(10)
window: [1, 10]                   sum = 11
                                average = 11 / 2 = 5.5

next(3)
window: [1, 10, 3]                sum = 14
                                average = 14 / 3 = 4.666... ≈ 4.67

next(5)                           window is now size 4 - TOO BIG (> 3)
window: [1, 10, 3, 5]             sum = 19
            │
            ▼  popleft() removes 1, sum -= 1
window: [10, 3, 5]                sum = 18
                                average = 18 / 3 = 6.0

5. Trace table - successful run (1, 10, 3, 5 with size=3)

Step	Operation	Action taken	Resulting state (`window`, `window_sum`) and returned average
1	Create MA(3)	`size=3`, `window=[]`, `window_sum=0`	`deque([])`, sum=0
2	`next(1)`	Append 1 → sum=1; len=1 ≤ 3 → no removal; avg=1/1	`deque([1])`, sum=1, returns `1.0`
3	`next(10)`	Append 10 → sum=11; len=2 ≤ 3 → no removal; avg=11/2	`deque([1, 10])`, sum=11, returns `5.5`
4	`next(3)`	Append 3 → sum=14; len=3 ≤ 3 → no removal; avg=14/3	`deque([1, 10, 3])`, sum=14, returns `4.666...`
5	`next(5)`	Append 5 → sum=19; len=4>3 → pop 1, sum=18; avg=18/3	`deque([10, 3, 5])`, sum=18, returns `6.0`

6. Trace for an edge-style example (partial window: only 2 values)

Assume size = 3 and we only call next twice.

Step	Operation	Action taken	Resulting state (`window`, `window_sum`) and returned average
1	Create MA(3)	`size=3`, `window=[]`, `window_sum=0`	`deque([])`, sum=0
2	`next(4)`	Append 4 → sum=4; len=1 ≤ 3 → no removal; avg=4/1	`deque([4])`, sum=4, returns `4.0`
3	`next(8)`	Append 8 → sum=12; len=2 ≤ 3 → no removal; avg=12/2	`deque([4, 8])`, sum=12, returns `6.0`

Here, the window is not yet full (only 2 values instead of 3), so no values are dropped; the average is over however many values exist so far.

7. Summary

Each new number joins the back of a fixed-size window and gets added to a running total; once the window grows past its allowed size, the oldest number is dropped from the front and subtracted from the total, so the average always reflects only the most recent values.

Q2 (Medium): Implement a Queue Using Two Stacks

Problem: You're only given stack operations (push/pop, which are LIFO) - implement FIFO queue behavior with them.

Key insight: Reversing order twice restores the original order. Use one stack for incoming items, and only when you need to dequeue, dump everything into a second stack - this naturally reverses it into FIFO order.

Python

                            
class QueueUsingStacks:
    def __init__(self):
        self.in_stack = []    # holds newly enqueued items
        self.out_stack = []   # holds items ready to be dequeued, in FIFO order

    def enqueue(self, x):
        self.in_stack.append(x)

    def dequeue(self):
        # Only refill out_stack when it's empty - this keeps the
        # average cost per operation O(1) even though a single
        # refill can take O(n).
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

        if not self.out_stack:
            raise IndexError("dequeue from empty queue")

        return self.out_stack.pop()


q = QueueUsingStacks()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())   # 1 - correct FIFO order despite using stacks

Step-by-Step Explanation

1. What problem does it solve?

It solves the “queue with stacks” problem: stacks naturally give last-in, first-out behavior, but by using two stacks together, we can mimic a real queue where the first item added is the first item removed.

2. Step-by-step walkthrough

Class and its fields

                                
                        class QueueUsingStacks:
                            def __init__(self):
                                self.in_stack = []    # holds newly enqueued items
                                self.out_stack = []   # holds items ready to be dequeued, in FIFO order

self.in_stack is a list used as a stack for new items being enqueued.
self.out_stack is another stack that holds items in the correct order for dequeuing.

The key idea: pushing to in_stack is easy; when we need to dequeue, we reverse in_stack into out_stack so the oldest item ends up on top.

Enqueue (add to the back)

                                
                        def enqueue(self, x):
                            self.in_stack.append(x)

To add an item x, we simply push it onto in_stack.

All new items pile up in in_stack in the order they arrive, with the newest on top.

Dequeue (remove from the front)

                                
                        def dequeue(self):
                            # Only refill out_stack when it's empty
                            if not self.out_stack:
                                while self.in_stack:
                                    self.out_stack.append(self.in_stack.pop())

                            if not self.out_stack:
                                raise IndexError("dequeue from empty queue")

                            return self.out_stack.pop()

First, check if out_stack is empty.
If it is, we “refill” it by moving all items from in_stack to out_stack:
- self.in_stack.pop() removes the top (most recent) item from in_stack.
- self.out_stack.append(...) pushes that item onto out_stack.
- Repeating this reverses the order: the oldest item from in_stack becomes the top of out_stack.
If out_stack is still empty after trying to refill, we raise an error for "dequeue from empty queue".
Otherwise, we pop from out_stack, returning the oldest enqueued item.

We only refill out_stack when it's empty, which keeps the average cost per operation low even though a single refill can take time proportional to the number of items.

Example usage

                                
                        q = QueueUsingStacks()
                        q.enqueue(1)
                        q.enqueue(2)
                        q.enqueue(3)
                        print(q.dequeue())   # 1 - correct FIFO order despite using stacks

Create a QueueUsingStacks object.
Enqueue 1 → in_stack = [1].
Enqueue 2 → in_stack = [1, 2] (2 on top).
Enqueue 3 → in_stack = [1, 2, 3] (3 on top).
Dequeue:
- out_stack is empty, so we move all items from in_stack to out_stack:
  - Pop 3 → out_stack = [3]
  - Pop 2 → out_stack = [3, 2]
  - Pop 1 → out_stack = [3, 2, 1] (1 on top)
- Now pop from out_stack → returns 1, the first enqueued item.

This shows that even though we used stacks internally, the external behavior is a proper queue.

3. Why two stacks fit this problem

A single stack gives last-in, first-out order, which is the opposite of a queue's first-in, first-out order. By using one stack to collect new items and a second stack to reverse them when needed, we can produce the correct FIFO order while still only using stack operations.

4. Visual diagram - successful example (enqueue 1,2,3 then dequeue)

We'll track in_stack (top on the right) and out_stack (top on the right).

enqueue(1)          enqueue(2)              enqueue(3)
in_stack: [1]        in_stack: [1, 2]        in_stack: [1, 2, 3]
out_stack: []        out_stack: []            out_stack: []
                                                    ▲
                                            (3 is on top - most recent)


dequeue() called
out_stack is EMPTY → refill it by popping everything off in_stack

in_stack: [1, 2, 3]
    │ pop 3 → push to out_stack
    ▼
in_stack: [1, 2]     out_stack: [3]
    │ pop 2 → push to out_stack
    ▼
in_stack: [1]        out_stack: [3, 2]
    │ pop 1 → push to out_stack
    ▼
in_stack: []         out_stack: [3, 2, 1]
                                        ▲
                                    (1 is now on TOP - the oldest item!)

pop from out_stack → removes 1
in_stack: []         out_stack: [3, 2]
returned: 1   correct FIFO order

5. Trace table - successful run (enqueue 1,2,3 then dequeue)

Step	Operation	Action taken	Resulting state (`in_stack`, `out_stack`) and return value
1	Create queue	`in_stack=[]`, `out_stack=[]`	`([], [])`
2	`enqueue(1)`	Append 1 to `in_stack`	`in=[1]`, `out=[]`
3	`enqueue(2)`	Append 2 to `in_stack`	`in=[1, 2]`, `out=[]`
4	`enqueue(3)`	Append 3 to `in_stack`	`in=[1, 2, 3]`, `out=[]`
5	`dequeue()`	`out` empty → move all from `in` to `out` (3,2,1); then pop from `out` → 1	`in=[]`, `out=[3, 2]`, returns `1`

6. Trace for a failing example (dequeue from empty queue)

Try to dequeue when nothing has been enqueued.

                                
                        q = QueueUsingStacks()
                        q.dequeue()

Step	Operation	Action taken	Resulting state / note
1	Create queue	`in_stack=[]`, `out_stack=[]`	`([], [])`
2	`dequeue()`	`out_stack` empty → try to refill, but `in_stack` also empty → raise error	Raises `IndexError("dequeue from empty queue")`

It fails at step 2 because both stacks are empty, meaning there is no item to remove, so the code correctly raises an error instead of returning a fake value.

Summary

New items pile onto one stack, and only when the second stack runs empty do we flip everything over from the first stack into the second - which reverses the order back to correct, so the oldest item always ends up on top and ready to be removed next.

Q3 (Medium): Design a Circular Queue

Problem: Implement a fixed-size queue that reuses freed-up space at the front instead of wasting memory, using a fixed-size array.

Key insight: Use modular arithmetic (% size) to wrap around the front and rear pointers back to index 0 once they hit the end of the array.

Python

                            
class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.queue = [None] * capacity
        self.front = 0
        self.rear = -1
        self.count = 0   # tracks how many elements are currently stored

    def enqueue(self, value):
        if self.count == self.capacity:
            raise OverflowError("Queue is full")

        # Wrap around to the start of the array using modulo
        self.rear = (self.rear + 1) % self.capacity
        self.queue[self.rear] = value
        self.count += 1

    def dequeue(self):
        if self.count == 0:
            raise IndexError("Queue is empty")

        value = self.queue[self.front]
        self.front = (self.front + 1) % self.capacity   # wrap around here too
        self.count -= 1
        return value

    def is_full(self):
        return self.count == self.capacity

    def is_empty(self):
        return self.count == 0


cq = CircularQueue(3)
cq.enqueue(1)
cq.enqueue(2)
cq.enqueue(3)
print(cq.dequeue())   # 1 - frees up a slot
cq.enqueue(4)          # reuses the freed slot instead of needing more memory
print(cq.dequeue())    # 2
print(cq.dequeue())    # 3
print(cq.dequeue())    # 4

Step-by-Step Explanation

1. What problem does it solve?

It solves the “bounded waiting line with limited seats” problem: like a ticket counter with a fixed number of slots, where people join at the back, leave from the front, and freed slots are reused in a circle.

2. Step-by-step walkthrough

Class and its fields

                                
                        class CircularQueue:
                            def __init__(self, capacity):
                                self.capacity = capacity
                                self.queue = [None] * capacity
                                self.front = 0
                                self.rear = -1
                                self.count = 0   # tracks how many elements are currently stored

capacity is the maximum number of items the queue can hold.
self.queue is a list of that size, initially filled with None as empty slots.
self.front is the index of the next item to be removed (the front of the queue).
self.rear is the index of the most recently added item; it starts at -1 because nothing is added yet.
self.count tracks how many items are currently in the queue.

Using count makes it easy to check if the queue is full or empty without tricky index math.

Enqueue (add to the back)

                                
                        def enqueue(self, value):
                            if self.count == self.capacity:
                                raise OverflowError("Queue is full")

                            # Wrap around to the start of the array using modulo
                            self.rear = (self.rear + 1) % self.capacity
                            self.queue[self.rear] = value
                            self.count += 1

First, check if the queue is already full by comparing count to capacity. If full, raise an error.
(self.rear + 1) % self.capacity moves rear one step forward and wraps around to 0 when it reaches the end.
We store value at the new rear position and increase count by 1.

This circular movement lets us reuse slots at the beginning of the array once we reach the end.

Dequeue (remove from the front)

                                
                        def dequeue(self):
                            if self.count == 0:
                                raise IndexError("Queue is empty")

                            value = self.queue[self.front]
                            self.front = (self.front + 1) % self.capacity   # wrap around here too
                            self.count -= 1
                            return value

If count is 0, raise an error for “queue is empty”.
We read the value at front and move front one step forward using wrap-around modulo.
Decrease count by 1 and return the removed value.

Even though we don't explicitly clear the old slot, it's logically removed because count and front no longer include it.

is_full and is_empty helpers

                                
                        def is_full(self):
                            return self.count == self.capacity

                        def is_empty(self):
                            return self.count == 0

is_full checks if the number of stored items equals capacity.
is_empty checks if there are no items at all.

Example usage

                                
                        cq = CircularQueue(3)
                        cq.enqueue(1)
                        cq.enqueue(2)
                        cq.enqueue(3)
                        print(cq.dequeue())   # 1 - frees up a slot
                        cq.enqueue(4)          # reuses the freed slot instead of needing more memory
                        print(cq.dequeue())    # 2
                        print(cq.dequeue())    # 3
                        print(cq.dequeue())    # 4

Create a circular queue with capacity 3.
Enqueue 1, 2, 3 → queue becomes full.
Dequeue → removes 1, freeing one slot.
Enqueue 4 → uses the freed slot via circular wrap-around.
Subsequent dequeues return 2, 3, and 4 in order.

3. Why a circular array fits this problem

A normal list-based queue that removes from the front can waste space or require shifting elements; a circular array avoids that by treating the list as a loop where indices wrap around. This gives efficient, fixed-size queue behavior with constant-time enqueue and dequeue and no need to move existing items.

4. Visual diagram - capacity=3, operations 1,2,3, dequeue, enqueue 4

We'll show queue as a fixed array of size 3, with front, rear, and count.

Initial state
capacity = 3
queue = [None, None, None]
front = 0
rear  = -1
count = 0

After enqueue(1)
rear = (-1 + 1) % 3 = 0
queue = [1, None, None]
front = 0, rear = 0, count = 1

After enqueue(2)
rear = (0 + 1) % 3 = 1
queue = [1, 2, None]
front = 0, rear = 1, count = 2

After enqueue(3)
rear = (1 + 1) % 3 = 2
queue = [1, 2, 3]
front = 0, rear = 2, count = 3 (full)

After dequeue() → returns 1
value = queue[0] = 1
front = (0 + 1) % 3 = 1
queue = [1, 2, 3]   # slot 0 logically free now
front = 1, rear = 2, count = 2

After enqueue(4)
rear = (2 + 1) % 3 = 0 (wraps around to start)
queue = [4, 2, 3]
front = 1, rear = 0, count = 3

Logical order in queue: [2, 3, 4] (from front=1 onward, wrapping)

5. Trace table - successful run (capacity=3)

Step	Operation	Action taken	Resulting state (`queue`, `front`, `rear`, `count`) and return
1	Create CQ(3)	`queue=[None,None,None]`, `front=0`, `rear=-1`, `count=0`	`([None,None,None], 0, -1, 0)`
2	`enqueue(1)`	`rear=0`, `queue[0]=1`, `count=1`	`([1,None,None], 0, 0, 1)`
3	`enqueue(2)`	`rear=1`, `queue[1]=2`, `count=2`	`([1,2,None], 0, 1, 2)`
4	`enqueue(3)`	`rear=2`, `queue[2]=3`, `count=3` (full)	`([1,2,3], 0, 2, 3)`
5	`dequeue()`	`value=1`, `front=1`, `count=2`	`([1,2,3], 1, 2, 2)`, returns `1`
6	`enqueue(4)`	`rear=(2+1)%3=0`, `queue[0]=4`, `count=3`	`([4,2,3], 1, 0, 3)`
7	`dequeue()`	`value=2`, `front=2`, `count=2`	`([4,2,3], 2, 0, 2)`, returns `2`
8	`dequeue()`	`value=3`, `front=0`, `count=1`	`([4,2,3], 0, 0, 1)`, returns `3`
9	`dequeue()`	`value=4`, `front=1`, `count=0`	`([4,2,3], 1, 0, 0)`, returns `4`

6. Trace for a failing example (enqueue when full)

Try to add a fourth item when capacity is 3 and the queue is full.

                                
                        cq = CircularQueue(3)
                        cq.enqueue(1)
                        cq.enqueue(2)
                        cq.enqueue(3)
                        cq.enqueue(4)

Step	Operation	Action taken	Resulting state / note
1	Create CQ(3)	`queue=[None,None,None]`, `front=0`, `rear=-1`, `count=0`	`([None,None,None], 0, -1, 0)`
2	`enqueue(1)`	`rear=0`, `queue[0]=1`, `count=1`	`([1,None,None], 0, 0, 1)`
3	`enqueue(2)`	`rear=1`, `queue[1]=2`, `count=2`	`([1,2,None], 0, 1, 2)`
4	`enqueue(3)`	`rear=2`, `queue[2]=3`, `count=3` (full)	`([1,2,3], 0, 2, 3)`
5	`enqueue(4)`	`count == capacity` → raise `OverflowError("Queue is full")`	Raises `OverflowError("Queue is full")`

It fails at step 5 because count equals capacity, meaning all slots are logically occupied, so the queue correctly refuses to add more items until some are dequeued.

7. Summary

A fixed-size array acts like a circle of numbered seats - front and rear pointers move forward and wrap back around to the start using modulo whenever they reach the end, letting freed-up slots be reused endlessly without ever needing to grow the array or shift any items.

Q4 (Medium): Reverse the First K Elements of a Queue

Problem: Given a queue and an integer k, reverse the first k elements of the queue while keeping the rest of the queue in its original order.

Key insight: Since a queue can't be reversed directly (FIFO order can't be flipped in place), use a stack as a helper - pushing the first k elements onto a stack naturally reverses their order, since a stack is LIFO.

Python

                            
from collections import deque

def reverse_first_k(queue, k):
    if k <= 0 or k > len(queue):
        return queue

    stack = []

    # Move the first k elements into a stack - this reverses their order
    for _ in range(k):
        stack.append(queue.popleft())

    # Push them back into the queue - now in reversed order
    while stack:
        queue.append(stack.pop())

    # Move the remaining (already in-order) elements to the back,
    # so the reversed part stays at the front where it belongs
    for _ in range(len(queue) - k):
        queue.append(queue.popleft())

    return queue


q = deque([1, 2, 3, 4, 5])
print(list(reverse_first_k(q, 3)))
# [3, 2, 1, 4, 5]

Step-by-Step Explanation

1. What problem does it solve?

It solves the partially reverse a line problem: imagine people in a queue where you want to reverse the order of the first k people but leave everyone else standing in the same order behind them.

2. Step-by-step walkthrough

Imports and function signature

                                
                        from collections import deque

                        def reverse_first_k(queue, k):

deque is a double-ended queue that supports efficient popleft() (remove from front) and append() (add to back).
The function takes two inputs:
- queue: a deque representing the line of items.
- k: how many items from the front should be reversed.

The function will modify the queue so that only its first k elements are reversed.

Validate k

                                
                        if k <= 0 or k > len(queue):
                            return queue

If k is zero or negative, there's nothing to reverse, so we just return the queue unchanged.
If k is larger than the number of items in the queue, it's invalid for this logic, so we also return the queue unchanged.

This protects the rest of the code from bad input.

Prepare a temporary stack

                                
                        stack = []

stack is a normal Python list used as a stack (last-in, first-out).

We'll use this stack to temporarily hold the first k items and reverse their order.

Move the first k elements into the stack

                                
                        for _ in range(k):
                            stack.append(queue.popleft())

Repeat k times:
- queue.popleft() removes the front item from the queue.
- stack.append(...) pushes that item onto the stack.

Because a stack is last-in, first-out, the first item removed from the queue ends up at the bottom of the stack, and the k-th item ends up on top, effectively reversing their order.

After this loop:

The queue now contains only the remaining items (from position k+1 onward).
The stack contains the first k items in reversed order (top = original k-th item).

Push them back into the queue in reversed order

                                
                        while stack:
                            queue.append(stack.pop())

While the stack is not empty:
- stack.pop() removes the top item from the stack.
- queue.append(...) adds that item to the back of the queue.

Since the stack's top is the original k-th item, these items are added to the queue in reversed order.

At this point:

The queue's front part is the “rest” of the original items (those after the first k).
The queue's back part is the reversed first-k items.

Rotate the queue so the reversed part comes to the front

                                
                        for _ in range(len(queue) - k):
                            queue.append(queue.popleft())

len(queue) - k is the number of “rest” items (those that were originally after the first k).
Repeat that many times:
- queue.popleft() removes the front item (one of the “rest” items).
- queue.append(...) adds it to the back.

This rotation moves all the “rest” items from the front to the back, so the reversed k items end up at the front of the queue where they belong.

Return the modified queue

                                
                        return queue

The queue now has:
- First k items: reversed.
- Remaining items: original order.

Example usage

                                
                        q = deque([1, 2, 3, 4, 5])
                        print(list(reverse_first_k(q, 3)))
                        # [3, 2, 1, 4, 5]

Start with queue: [1, 2, 3, 4, 5].
We want to reverse the first 3 items.
After moving first 3 to stack:
- Queue: [4, 5]
- Stack (bottom→top): [1, 2, 3]
After popping stack back into queue:
- Queue: [4, 5, 3, 2, 1]
After rotating len(queue) - k = 5 - 3 = 2 times:
- Rotate 1: [5, 3, 2, 1, 4]
- Rotate 2: [3, 2, 1, 4, 5]
Final result: [3, 2, 1, 4, 5].

3. Why a stack fits this problem

A stack naturally reverses the order of items: whatever goes in first comes out last. By moving the first k queue items into a stack and then back into the queue, we automatically get those k items in reversed order without manual index juggling.

4. Visual diagram - successful example (queue = [1, 2, 3, 4, 5], k = 3)

Start: queue = [1, 2, 3, 4, 5],  k = 3
--------------------------------------------------------------------------
Step 1: move first 3 into a stack (via popleft)
queue: [1, 2, 3, 4, 5]
        │ popleft 1 → push to stack
        ▼
queue: [2, 3, 4, 5]     stack: [1]
        │ popleft 2 → push to stack
        ▼
queue: [3, 4, 5]        stack: [1, 2]
        │ popleft 3 → push to stack
        ▼
queue: [4, 5]           stack: [1, 2, 3]
                                    ▲ top
--------------------------------------------------------------------------
Step 2: pop stack, append to queue (reverses the order!)
stack: [1, 2, 3]                queue: [4, 5]
        │ pop 3 → append to queue
        ▼
stack: [1, 2]                   queue: [4, 5, 3]
        │ pop 2 → append to queue
        ▼
stack: [1]                      queue: [4, 5, 3, 2]
        │ pop 1 → append to queue
        ▼
stack: []                       queue: [4, 5, 3, 2, 1]
--------------------------------------------------------------------------
Step 3: rotate the 2 untouched items (4, 5) from front to back
queue: [4, 5, 3, 2, 1]
        │ popleft 4 → append to back
        ▼
queue: [5, 3, 2, 1, 4]
        │ popleft 5 → append to back
        ▼
queue: [3, 2, 1, 4, 5]     ← reversed first 3, untouched rest, in order!

5. Trace table - successful run (queue = [1, 2, 3, 4, 5], k = 3)

Step	Operation	Action taken	Resulting state (`queue`, `stack`)
1	Start	`queue=[1,2,3,4,5]`, `stack=[]`	`queue=[1,2,3,4,5]`, `stack=[]`
2	Move first 3 to stack (i=1)	`popleft()` → 1, `stack.append(1)`	`queue=[2,3,4,5]`, `stack=[1]`
3	Move first 3 to stack (i=2)	`popleft()` → 2, `stack.append(2)`	`queue=[3,4,5]`, `stack=[1,2]`
4	Move first 3 to stack (i=3)	`popleft()` → 3, `stack.append(3)`	`queue=[4,5]`, `stack=[1,2,3]`
5	Push stack back (pop 3)	`stack.pop()` → 3, `queue.append(3)`	`queue=[4,5,3]`, `stack=[1,2]`
6	Push stack back (pop 2)	`stack.pop()` → 2, `queue.append(2)`	`queue=[4,5,3,2]`, `stack=[1]`
7	Push stack back (pop 1)	`stack.pop()` → 1, `queue.append(1)`	`queue=[4,5,3,2,1]`, `stack=[]`
8	Rotate (5-3)=2 times (rot 1)	`popleft()` → 4, `append(4)`	`queue=[5,3,2,1,4]`
9	Rotate (rot 2)	`popleft()` → 5, `append(5)`	`queue=[3,2,1,4,5]` (final)

6. Trace for a failing / edge example (k invalid)

Case 1: k is larger than the queue length.

                                
                        q = deque([1, 2, 3])
                        reverse_first_k(q, 5)   # k > len(queue)

Step	Operation	Action taken	Resulting state / note
1	Start	`queue=[1,2,3]`, `k=5`	`queue=[1,2,3]`, `stack=[]`
2	Check `k`	`k > len(queue)` is True → immediately `return queue`	Queue unchanged: `[1,2,3]`; function exits early

The function stops at step 2 because k is invalid (greater than the number of elements), so it safely returns the original queue without modifying anything. (Another similar edge case is k <= 0, which also returns the queue unchanged for the same reason.)

Summary

The first k items are temporarily poured into a stack to flip their order, poured back into the queue, and then the untouched remaining items are rotated from front to back so the newly reversed section settles correctly at the front.

Q5 (Medium-Hard): Sliding Window Maximum

Problem: GGiven an array and a window size k, return the maximum value in each sliding window as it moves across the array.

Key insight: Use a deque that stores indices, keeping it in decreasing order of value. This lets you get the max in O(1) at any point, and the whole array is processed in O(n) total.

Python

                                
from collections import deque

def sliding_window_max(nums, k):
    result = []
    window = deque()   # stores indices; values stay in decreasing order

    for i, num in enumerate(nums):
        # Remove indices that have slid out of the current window
        if window and window[0] <= i - k:
            window.popleft()

        # Remove smaller values from the back - they can never be
        # the max while a bigger, more recent value is still in play
        while window and nums[window[-1]] < num:
            window.pop()

        window.append(i)

        # Once we've seen at least k elements, record the max
        if i >= k - 1:
            result.append(nums[window[0]])   # front of deque = current max

    return result


print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
# [3, 3, 5, 5, 6, 7]

Step-by-Step Explanation

1. What problem does it solve?

It solves the “moving window maximum” problem: imagine looking at a fixed-size window that slides over a row of numbers, and for each position you want the biggest number currently visible inside that window.

2. Step-by-step walkthrough

Imports and function signature

                                    
                            from collections import deque

                            def sliding_window_max(nums, k):

deque is a double-ended queue that allows fast removal from both front and back.
nums is the list of numbers.
k is the window size (how many consecutive numbers to consider at once).

The function will return a list of maximums, one for each window position.

Prepare result list and the deque

                                    
                            result = []
                            window = deque()   # stores indices; values stay in decreasing order

result will collect the maximum for each window.
window is a deque that stores indices of numbers, not the numbers themselves.
The key idea: values at these indices are kept in decreasing order inside the deque, so the front always holds the index of the current maximum.

Storing indices lets us easily check whether an element has slid out of the window.

Loop through each number with its index

                                    
                            for i, num in enumerate(nums):

i is the current index, num is the current number.

At each step, we update the deque to reflect the current window and then possibly record a maximum.

Remove indices that are out of the current window

                                    
                            if window and window[0] <= i - k:
                                window.popleft()

window[0] is the index at the front of the deque (the oldest index we're tracking).
i - k is the index just before the current window starts.
If the front index is less than or equal to i - k, that element is no longer in the window, so we remove it with popleft().

Remove smaller values from the back

                                    
                            while window and nums[window[-1]] < num:
                                window.pop()

window[-1] is the index at the back of the deque.
While its value is smaller than the current num, we remove it with pop().

A smaller, older value can never be the maximum while a newer, larger value is present in the same or future windows, so we safely discard it. This maintains decreasing order in the deque.

Add the current index

                                    
                            window.append(i)

After removing out-of-window and smaller elements, we add index i to the back of the deque.

Record the maximum once the first full window is formed

                                    
                            if i >= k - 1:
                                result.append(nums[window[0]])   # front of deque = current max

The first full window ends at index k - 1.
For all i >= k - 1, nums[window[0]] gives the current maximum, which we append to result.

Return the list of maximums

                                    
                            return result

Example usage

                                    
                            print(sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
                            # [3, 3, 5, 5, 6, 7]

3. Why a deque fits this problem

A deque allows us to efficiently remove outdated indices from the front and smaller candidates from the back in amortized constant time. This dual-ended removal is exactly what we need to maintain a “best candidates” list for the sliding window maximum.

4. Visual diagram - nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

Initial state
i = -, num = -, window = [], result = []

i = 0, num = 1
window = [0] (vals: [1])
result = []

i = 1, num = 3
window = [1] (vals: [3])
result = []

i = 2, num = -1  (first full window)
window = [1, 2] (vals: [3, -1])
result = [3]

i = 3, num = -3
window = [1, 2, 3] (vals: [3, -1, -3])
result = [3, 3]

i = 4, num = 5
window = [4] (vals: [5])
result = [3, 3, 5]

i = 5, num = 3
window = [4, 5] (vals: [5, 3])
result = [3, 3, 5, 5]

i = 6, num = 6
window = [6] (vals: [6])
result = [3, 3, 5, 5, 6]

i = 7, num = 7
window = [7] (vals: [7])
result = [3, 3, 5, 5, 6, 7]

5. Trace table - successful run

i	num	Action on `window` (indices)	`window` after actions (indices, values)	Result so far
0	1	append 0	`[0] (1)`	`[]`
1	3	pop 0 (1<3), append 1	`[1] (3)`	`[]`
2	-1	append 2	`[1,2] (3,-1)`	`[3]`
3	-3	append 3	`[1,2,3] (3,-1,-3)`	`[3,3]`
4	5	pop left 1 (out), pop 3 (-3<5), pop 2 (-1<5), append 4	`[4] (5)`	`[3,3,5]`
5	3	append 5	`[4,5] (5,3)`	`[3,3,5,5]`
6	6	pop left 4 (out), pop 5 (3<6), append 6	`[6] (6)`	`[3,3,5,5,6]`
7	7	pop 6 (6<7), append 7	`[7] (7)`	`[3,3,5,5,6,7]`

6. Trace for an edge example (k = 1)

When k = 1, each window is just a single element, so the maximum of each window is the element itself.

                                    
                            sliding_window_max([2, 4, 3], 1)
                            # Expected: [2, 4, 3]

i	num	Out-of-window check (`window[0] <= i-1`)	Back removal (`nums[back] < num`)	`window` after append	Result so far
0	2	window empty → skip	empty → skip	`[0] (2)`	`[2]`
1	4	`0 <= 0` → pop left → `[]`	empty → skip	`[1] (4)`	`[2,4]`
2	3	`1 <= 1` → pop left → `[]`	`4 < 3`? No	`[2] (3)`	`[2,4,3]`

7. Summary

The deque keeps indices in decreasing order of value, front to back, by discarding old positions that fell out of the window and smaller values that can never win again - leaving the current maximum always sitting right at the front, ready to read off.

Click here to access the source code repository.

6. Common Patterns Table

Not sure which type of queue problem you're looking at? This section breaks down the most common queue patterns you'll run into - both in real coding interviews and in everyday programming. Each pattern comes with the keywords that usually give it away in a problem statement, plus example problems so you can see it in action.

Pattern	Signal / Keywords in the Problem	Example Problems
Basic FIFO processing	"First come, first served," "process in order," "scheduling"	Print Queue, Support Ticket System
BFS traversal	"Levels," "layer by layer," "spread/infect"	Level Order Traversal, Rotting Oranges
Fixed-size window tracking	"Last k values," "moving average," "recent window"	Moving Average from Data Stream, Rate Limiter
Queue-to-stack conversion (and back)	"Reverse the order," "implement using [the other structure]"	Reverse First K Elements, Queue using Stacks
Circular / fixed-size buffering	"Fixed capacity," "reuse space," "ring buffer"	Design Circular Queue, Design Circular Deque
Stack-to-queue conversion	"Implement using [the other structure]"	Queue using Stacks, Stack using Queues

7. Practice Roadmap

Work through these roughly in order - easy to hard:

Implement Queue using Array/List - Easy (foundational, build it yourself)
Design Circular Queue - Medium (LeetCode #622)
Implement Queue using Stacks - Easy (LeetCode #232)
Moving Average from Data Stream - Easy (LeetCode #346)
Number of Recent Calls (Rate Limiter style) - Easy (LeetCode #933)
Binary Tree Level Order Traversal (BFS basics) - Medium (LeetCode #102)
Reverse First K Elements of a Queue - Medium (GeeksforGeeks classic - good stack/queue combo practice)
Rotting Oranges (BFS on a grid) - Medium (LeetCode #994)
Open the Lock (BFS shortest path) - Medium (LeetCode #752)/li>

Suggested platforms:

LeetCode: filter by the "Queue" or "Breadth-First Search" tag.
NeetCode 150: groups these logically, with the "Graphs" and "Trees" sections leaning heavily on BFS/queue usage.
Codeforces: for competitive-style scheduling and simulation problems.

Next logical topic: Singly Linked List - since the LinkedQueue implementation in Method 3 is built directly on singly linked list nodes, and understanding that structure on its own makes it much easier to see how the front/rear pointers here actually work under the hood.

Learn the Stack data structure in Python: LIFO principles, push/pop/peek operations, and 3 implementations (list, deque, linked list) with interview problems and complexity explained.

Go To Next Tutorial

Implement Google Sign-In with Firebase JS - no backend.

Go To Next Tutorial

Beginner-friendly C programming chapters: follow our step-by-step path from Hello World to real-world projects. Go To Tutorial

Deploy Flask on VPS with Nginx, Gunicorn & SSL. Free & paid options for beginners. Go To Tutorial

Queue Data Structure in Python – Complete Tutorial with Examples

Table of Contents

Introduction

1. What Is Queue?

Real systems/software that use queues internally:

2. Core Operations & Complexity

3. Implementation

Method A: Using Python's built-in list (works, but inefficient)

Method B: Using `collections.deque` (the recommended approach)

Method 3: From Scratch Using a Dictionary (Beginner Version)

4. Real-World Practical Problems

Problem 1: Print Job / Task Scheduler

Problem 2: Customer Support Ticket System

Problem 3: Breadth-First Search (BFS) - Finding Shortest Path

Problem 4: Rate Limiter (Sliding Window)

5. Interview Questions

Q1 (Easy): Moving Average from a Data Stream

Q2 (Medium): Implement a Queue Using Two Stacks

Q3 (Medium): Design a Circular Queue

Q4 (Medium): Reverse the First K Elements of a Queue

Q5 (Medium-Hard): Sliding Window Maximum

6. Common Patterns Table

7. Practice Roadmap

Suggested platforms:

Stack Data Structure in Python

How to Implement Google Sign-In with Firebase & JavaScript

C Programming

How to Create and Deploy a Flask App on VPS

Queue Data Structure in Python – Complete Tutorial with Examples

Table of Contents

Introduction

1. What Is Queue?

Real systems/software that use queues internally:

2. Core Operations & Complexity

3. Implementation

Method A: Using Python's built-in list (works, but inefficient)

Method B: Using collections.deque (the recommended approach)

Method 3: From Scratch Using a Dictionary (Beginner Version)

4. Real-World Practical Problems

Problem 1: Print Job / Task Scheduler

Problem 2: Customer Support Ticket System

Problem 3: Breadth-First Search (BFS) - Finding Shortest Path

Problem 4: Rate Limiter (Sliding Window)

5. Interview Questions

Q1 (Easy): Moving Average from a Data Stream

Q2 (Medium): Implement a Queue Using Two Stacks

Q3 (Medium): Design a Circular Queue

Q4 (Medium): Reverse the First K Elements of a Queue

Q5 (Medium-Hard): Sliding Window Maximum

6. Common Patterns Table

7. Practice Roadmap

Suggested platforms:

Stack Data Structure in Python

How to Implement Google Sign-In with Firebase & JavaScript

C Programming

How to Create and Deploy a Flask App on VPS

Method B: Using `collections.deque` (the recommended approach)