Queues

🚶‍♂️ What is a Queue?

A Queue is a linear data structure that follows FIFO (First In, First Out). Like a line at a store - first person in line gets served first!


# Simple queue using Python list
queue = []

# Enqueue (add to rear)
queue.append(10)  # [10]
queue.append(20)  # [10, 20]
queue.append(30)  # [10, 20, 30]

# Dequeue (remove from front)
first = queue.pop(0)  # Returns 10, queue becomes [20, 30]
print(f"Served: {first}")
print(f"Queue: {queue}")

FIFO

Order

O(1)

Operations

Both Ends

Access

Queue Operations

➡️

Enqueue

Add element to the rear

O(1) Insert

⬅️

Dequeue

Remove element from front

O(1) Remove

👁️

Front

View front element

O(1) Read

❓

isEmpty

Check if queue is empty

O(1) Check

Lesson 1: Simple Queue Implementation

Create a basic Queue class:

Basic Queue Class


class Queue:
    def __init__(self):
        self.items = []
    
    def enqueue(self, item):
        """Add item to rear"""
        self.items.append(item)
    
    def dequeue(self):
        """Remove and return front item"""
        if self.is_empty():
            return None
        return self.items.pop(0)
    
    def front(self):
        """View front item"""
        if self.is_empty():
            return None
        return self.items[0]
    
    def is_empty(self):
        """Check if queue is empty"""
        return len(self.items) == 0
    
    def size(self):
        """Get number of items"""
        return len(self.items)

# Example usage
queue = Queue()
queue.enqueue("Alice")
queue.enqueue("Bob")
queue.enqueue("Charlie")

print(f"Front: {queue.front()}")      # Alice
print(f"Served: {queue.dequeue()}")   # Alice
print(f"Size: {queue.size()}")        # 2

Lesson 2: Real-World Applications

Task Scheduling

CPU process scheduling
Print job queues
Background tasks

Web Services

Request handling
Message queues
API rate limiting

Algorithms

Breadth-First Search
Level-order traversal
Buffer for data streams

Real Life

Waiting lines
Call centers
Traffic systems

Lesson 3: Customer Service Queue

Simulate a customer service system:

Customer Service System


class CustomerService:
    def __init__(self):
        self.queue = []
        self.ticket_number = 1
    
    def add_customer(self, name):
        """Customer joins the queue"""
        ticket = f"#{self.ticket_number}"
        self.queue.append((ticket, name))
        print(f"{name} joined queue with ticket {ticket}")
        self.ticket_number += 1
    
    def serve_customer(self):
        """Serve the next customer"""
        if not self.queue:
            print("No customers waiting!")
            return
        
        ticket, name = self.queue.pop(0)
        print(f"Now serving: {name} (ticket {ticket})")
        return name
    
    def show_queue(self):
        """Display current queue"""
        if not self.queue:
            print("Queue is empty")
            return
        
        print("Current queue:")
        for i, (ticket, name) in enumerate(self.queue):
            position = "Next" if i == 0 else f"Position {i+1}"
            print(f"  {ticket} {name} - {position}")

# Example usage
service = CustomerService()

# Customers arrive
service.add_customer("Alice")
service.add_customer("Bob")
service.add_customer("Charlie")

service.show_queue()

# Serve customers
service.serve_customer()  # Alice
service.serve_customer()  # Bob

service.show_queue()      # Only Charlie left

Lesson 4: Circular Queue

More efficient queue implementation:

Circular Queue


class CircularQueue:
    def __init__(self, max_size):
        self.max_size = max_size
        self.queue = [None] * max_size
        self.front = 0
        self.rear = 0
        self.count = 0
    
    def enqueue(self, item):
        """Add item to queue"""
        if self.is_full():
            print("Queue is full!")
            return False
        
        self.queue[self.rear] = item
        self.rear = (self.rear + 1) % self.max_size
        self.count += 1
        return True
    
    def dequeue(self):
        """Remove item from queue"""
        if self.is_empty():
            return None
        
        item = self.queue[self.front]
        self.queue[self.front] = None
        self.front = (self.front + 1) % self.max_size
        self.count -= 1
        return item
    
    def is_empty(self):
        return self.count == 0
    
    def is_full(self):
        return self.count == self.max_size
    
    def size(self):
        return self.count

# Example usage
cq = CircularQueue(3)

cq.enqueue("A")
cq.enqueue("B")
cq.enqueue("C")
cq.enqueue("D")  # Queue is full!

print(cq.dequeue())  # A
cq.enqueue("D")      # Now fits
print(f"Size: {cq.size()}")  # 3

Practice Project: Print Job Manager

Manage print jobs using a queue:

Print Job Manager


class PrintJob:
    def __init__(self, document, pages):
        self.document = document
        self.pages = pages
    
    def __str__(self):
        return f"{self.document} ({self.pages} pages)"

class PrintQueue:
    def __init__(self):
        self.jobs = []
    
    def add_job(self, document, pages):
        """Add print job to queue"""
        job = PrintJob(document, pages)
        self.jobs.append(job)
        print(f"Added: {job}")
    
    def print_next(self):
        """Print the next job"""
        if not self.jobs:
            print("No jobs in queue!")
            return
        
        job = self.jobs.pop(0)
        print(f"Printing: {job}")
        return job
    
    def show_queue(self):
        """Show all pending jobs"""
        if not self.jobs:
            print("Print queue is empty")
            return
        
        print("Print Queue:")
        for i, job in enumerate(self.jobs, 1):
            print(f"  {i}. {job}")
    
    def total_pages(self):
        """Calculate total pages to print"""
        return sum(job.pages for job in self.jobs)

# Example usage
printer = PrintQueue()

# Add print jobs
printer.add_job("Report.pdf", 10)
printer.add_job("Photos.jpg", 5)
printer.add_job("Invoice.doc", 2)

printer.show_queue()
print(f"Total pages: {printer.total_pages()}")

# Print jobs
printer.print_next()  # Report.pdf
printer.print_next()  # Photos.jpg

printer.show_queue()  # Only Invoice.doc left