Stacks and Queues — Managing Data Flow

**Stacks** and **Queues** are two of the most fundamental data structures in computer science.

Chapter 3: Data Structures

Sub-chapter: Stacks and Queues — Managing Data Flow

Stacks and Queues are two of the most fundamental data structures in computer science.
They define how data is stored and accessed — in a particular order — and are used in everything from web browsers to operating systems and algorithms like BFS and DFS.

🧠 Concept Overview

🧱 Stack (LIFO — Last In, First Out)

A stack works like a pile of plates:

• You push a plate onto the top.
• You pop the top plate off.
• You can peek at the top plate without removing it.

Implementation Using Python Lists

stack = []  # Empty stack

# Push elements
stack.append(1)
stack.append(2)
stack.append(3)
print("Stack:", stack)

# Peek at the top
print("Top element:", stack[-1])

# Pop element
top = stack.pop()
print("Popped:", top)
print("Stack after pop:", stack)

⚙️ Example — Browser History (Stack Simulation)

history = []

# Visiting pages
history.append("home")
history.append("about")
history.append("contact")

print("Current:", history[-1])

# Go back (pop last page)
history.pop()
print("Back to:", history[-1])

Output:

Current: contact
Back to: about

🧭 Stacks are perfect for undo/redo systems, recursion, and backtracking.

⚡ Queue (FIFO — First In, First Out)

A queue is like a line of people waiting:

• The first person in line is the first to be served.
• New people join the back of the line.

Implementation Using Lists (⚠️ Not Recommended for Performance)

queue = []

queue.append("A")  # Enqueue
queue.append("B")
queue.append("C")
print("Queue:", queue)

front = queue.pop(0)  # Dequeue
print("Dequeued:", front)
print("Queue after dequeue:", queue)

⚠️ pop(0) takes O(n) time since it shifts all elements. For large queues, use collections.deque instead.

🧱 Efficient Queue with collections.deque

Python’s collections.deque is optimized for fast appends and pops from both ends (O(1)).

from collections import deque

queue = deque()

queue.append("Task1")  # Enqueue
queue.append("Task2")
queue.append("Task3")

print("Queue:", queue)

queue.popleft()  # Dequeue front
print("After dequeue:", queue)

⚙️ Example — Task Queue Simulation

from collections import deque

tasks = deque(["Render Video", "Upload File", "Send Email"])

print("Current task:", tasks[0])
tasks.popleft()
print("Next task:", tasks[0])

Output:

Current task: Render Video
Next task: Upload File

🧩 Queues are ideal for task scheduling, job management, and real-time systems.

🧮 Priority Queues (Using heapq)

A priority queue assigns importance to each element.
Lower numbers have higher priority (by default).

import heapq

tasks = []
heapq.heappush(tasks, (2, "Write report"))
heapq.heappush(tasks, (1, "Fix critical bug"))
heapq.heappush(tasks, (3, "Reply to emails"))

while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"Processing task: {task} (priority {priority})")

Output:

Processing task: Fix critical bug (priority 1)
Processing task: Write report (priority 2)
Processing task: Reply to emails (priority 3)

🧩 Example — Printer Queue Simulation

from collections import deque
import time

printer_queue = deque(["Doc1", "Doc2", "Doc3"])

while printer_queue:
    current = printer_queue.popleft()
    print(f"Printing {current}...")
    time.sleep(1)  # simulate printing time
print("All documents printed!")

🧱 Stack vs Queue vs Deque Comparison

⚙️ Performance and Complexity Overview

⚡ Use deque for performance-critical queues.
🧩 Use list when simplicity is enough for small stacks.

🧠 Real-World Use Cases

🧾 Key Takeaways

• Stack → LIFO: Ideal for backtracking and undo systems.
• Queue → FIFO: Ideal for task ordering and scheduling.
• Use collections.deque for efficient implementations.
• Priority Queues (via heapq) handle tasks based on importance.
• These structures are essential in algorithms, compilers, and real-world systems.

Stacks and queues teach you discipline in data access order — the foundation for designing reliable, efficient algorithms.