Stacks, Queues, and Deques

Introduction

Imagine you're at a busy coffee shop. Customers arrive and form a line - the first person to arrive gets served first. This is a queue. Now imagine stacking plates in a cafeteria - you can only take the top plate, and new plates are placed on top. This is a stack.

These simple concepts power everything from web browsers to operating systems. Understanding stacks and queues is like learning the basic grammar of computer science - they appear everywhere once you know to look for them.

Stacks: Last In, First Out (LIFO)

A stack is like a stack of books or cafeteria trays. You can only access the top item, and new items are always placed on top.

Stack Operations

# Using a list as a stack
stack = []

# Push (add to top)
stack.append('book1')
stack.append('book2')
stack.append('book3')
print(stack)  # ['book1', 'book2', 'book3']

# Pop (remove from top)
top_book = stack.pop()
print(top_book)  # 'book3'
print(stack)     # ['book1', 'book2']

# Peek (look at top without removing)
if stack:
    print(f"Top book: {stack[-1]}")  # 'book2'

Stack Implementation

class Stack:
    def __init__(self):
        self.items = []
    
    def push(self, item):
        """Add item to top of stack."""
        self.items.append(item)
    
    def pop(self):
        """Remove and return item from top of stack."""
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self.items.pop()
    
    def peek(self):
        """Return top item without removing it."""
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self.items[-1]
    
    def is_empty(self):
        """Check if stack is empty."""
        return len(self.items) == 0
    
    def size(self):
        """Return number of items in stack."""
        return len(self.items)

# Usage
book_stack = Stack()
book_stack.push("Harry Potter")
book_stack.push("Lord of the Rings")
book_stack.push("The Hobbit")

print(book_stack.peek())  # "The Hobbit"
print(book_stack.pop())   # "The Hobbit"
print(book_stack.size())  # 2

Queues: First In, First Out (FIFO)

A queue is like a line at a store or restaurant. The first person to arrive is the first to be served.

Queue Operations

# Using a list as a queue (inefficient)
queue = []

# Enqueue (add to back)
queue.append('customer1')
queue.append('customer2')
queue.append('customer3')
print(queue)  # ['customer1', 'customer2', 'customer3']

# Dequeue (remove from front) - inefficient with lists
front_customer = queue.pop(0)
print(front_customer)  # 'customer1'
print(queue)          # ['customer2', 'customer3']

Efficient Queue with Deque

from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()
    
    def enqueue(self, item):
        """Add item to back of queue."""
        self.items.append(item)
    
    def dequeue(self):
        """Remove and return item from front of queue."""
        if self.is_empty():
            raise IndexError("Dequeue from empty queue")
        return self.items.popleft()
    
    def peek(self):
        """Return front item without removing it."""
        if self.is_empty():
            raise IndexError("Peek from empty queue")
        return self.items[0]
    
    def is_empty(self):
        """Check if queue is empty."""
        return len(self.items) == 0
    
    def size(self):
        """Return number of items in queue."""
        return len(self.items)

# Usage
checkout_line = Queue()
checkout_line.enqueue("Alice")
checkout_line.enqueue("Bob")
checkout_line.enqueue("Charlie")

print(checkout_line.peek())    # "Alice"
print(checkout_line.dequeue()) # "Alice"
print(checkout_line.size())    # 2

Deques: Double-Ended Queues

A deque (pronounced "deck") allows efficient operations from both ends. It's like having doors at both ends of a tunnel.

Deque Operations

from collections import deque

# Create a deque
numbers = deque([1, 2, 3, 4, 5])

# Add to right (end)
numbers.append(6)      # [1, 2, 3, 4, 5, 6]

# Add to left (beginning)
numbers.appendleft(0)  # [0, 1, 2, 3, 4, 5, 6]

# Remove from right
right = numbers.pop()      # 6, deque([0, 1, 2, 3, 4, 5])

# Remove from left
left = numbers.popleft()   # 0, deque([1, 2, 3, 4, 5])

# Peek operations
print(numbers[0])     # 1 (leftmost)
print(numbers[-1])    # 5 (rightmost)

Deque as Stack and Queue

# As a stack (LIFO)
stack = deque()
stack.append('bottom')
stack.append('middle') 
stack.append('top')
print(stack.pop())  # 'top'

# As a queue (FIFO)
queue = deque()
queue.append('first')
queue.append('second')
queue.append('third')
print(queue.popleft())  # 'first'

Real-World Applications

Browser History (Stack)

class BrowserHistory:
    def __init__(self):
        self.history = []
        self.current = -1
    
    def visit(self, url):
        """Visit a new URL."""
        # Remove forward history when visiting new page
        self.history = self.history[:self.current + 1]
        self.history.append(url)
        self.current += 1
    
    def back(self):
        """Go back to previous page."""
        if self.current > 0:
            self.current -= 1
            return self.history[self.current]
        return None
    
    def forward(self):
        """Go forward to next page."""
        if self.current < len(self.history) - 1:
            self.current += 1
            return self.history[self.current]
        return None

# Usage
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("stackoverflow.com")
browser.visit("github.com")

print(browser.back())    # "stackoverflow.com"
print(browser.back())    # "google.com"
print(browser.forward()) # "stackoverflow.com"

Print Queue (Queue)

from collections import deque

class PrintQueue:
    def __init__(self):
        self.queue = deque()
    
    def add_job(self, document_name, user):
        """Add a print job to the queue."""
        job = {"document": document_name, "user": user, "timestamp": time.time()}
        self.queue.append(job)
        print(f"Added print job: {document_name} for {user}")
    
    def process_job(self):
        """Process the next print job."""
        if self.queue:
            job = self.queue.popleft()
            print(f"Printing: {job['document']} for {job['user']}")
            return job
        else:
            print("No jobs in queue")
            return None
    
    def show_queue(self):
        """Show all pending jobs."""
        if not self.queue:
            print("Print queue is empty")
        else:
            print("Pending print jobs:")
            for i, job in enumerate(self.queue, 1):
                print(f"{i}. {job['document']} - {job['user']}")

# Usage
printer = PrintQueue()
printer.add_job("report.pdf", "Alice")
printer.add_job("presentation.pptx", "Bob")
printer.add_job("resume.docx", "Charlie")

printer.show_queue()
printer.process_job()
printer.process_job()

Text Editor Undo/Redo (Two Stacks)

class TextEditor:
    def __init__(self):
        self.text = ""
        self.undo_stack = []
        self.redo_stack = []
    
    def type_text(self, new_text):
        """Add text and save previous state for undo."""
        self.undo_stack.append(self.text)
        self.text += new_text
        self.redo_stack.clear()  # Clear redo stack when new action
    
    def undo(self):
        """Undo last action."""
        if self.undo_stack:
            self.redo_stack.append(self.text)
            self.text = self.undo_stack.pop()
            return True
        return False
    
    def redo(self):
        """Redo last undone action."""
        if self.redo_stack:
            self.undo_stack.append(self.text)
            self.text = self.redo_stack.pop()
            return True
        return False

# Usage
editor = TextEditor()
editor.type_text("Hello ")
editor.type_text("world!")
print(editor.text)  # "Hello world!"

editor.undo()
print(editor.text)  # "Hello "

editor.undo()
print(editor.text)  # ""

editor.redo()
print(editor.text)  # "Hello "

Performance Comparison

Common Use Cases

Key Points to Remember

• Stacks follow LIFO (Last In, First Out) principle
• Queues follow FIFO (First In, First Out) principle
• Deques provide efficient operations from both ends
• Choose the right data structure based on your access patterns
• Python's collections.deque is optimized for queue and stack operations
• These fundamental structures power many real-world applications

Stacks and queues are linear data structures. In the next lesson, we'll explore trees - hierarchical structures that model many real-world relationships like family trees, file systems, and organizational charts.