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

Structure	Access Pattern	Example Analogy	Principle
Stack	Last-In, First-Out (LIFO)	Stack of plates	The last item added is removed first
Queue	First-In, First-Out (FIFO)	Line at a ticket counter	The first person in line is served first

---

🧱 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)

Operation	Description	Example	Time Complexity
append(x)	Push element to top	stack.append(5)	O(1)
pop()	Remove and return top element	stack.pop()	O(1)
stack[-1]	Peek top element	—	O(1)

---

⚙️ 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)

Operation	Method	Complexity
Enqueue	append()	O(1)
Dequeue	popleft()	O(1)
Peek	queue[0]	O(1)

---

⚙️ 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

Feature	Stack (LIFO)	Queue (FIFO)	Deque (Double-ended)
Add	append()	append()	append() or appendleft()
Remove	pop()	popleft()	pop() or popleft()
Order	Last in, first out	First in, first out	Both directions
Use Cases	Undo, recursion, parsing	Scheduling, BFS, buffering	Bidirectional processing

---

⚙️ Performance and Complexity Overview

Operation	Stack (List)	Queue (List)	Queue (Deque)
Add (push/enqueue)	O(1)	O(1)	O(1)
Remove (pop/dequeue)	O(1)	O(n)	O(1)
Peek	O(1)	O(1)	O(1)

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

---

🧠 Real-World Use Cases

Structure	Common Applications
Stack	Browser history, Undo/Redo, Recursion, Syntax parsing
Queue	Task scheduling, BFS traversal, Message processing
Deque	Palindrome checking, sliding window algorithms

---

🧾 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.