CQH102: Stacks and Queues – Managing Ordered Data

In our last post, we explored arrays and linked lists—the foundation of storing data in a sequence. Now, let’s look at two specialized structures built on top of them: Stacks and Queues.

These structures aren’t just academic—they’re everywhere in real-world computing. From undo functionality in editors to printer job queues and browser history, understanding these tools will supercharge your ability to model problems.

Stacks – Last In, First Out (LIFO)

A stack operates just like a stack of plates: you add to the top, and you remove from the top.

Core Operations

push(item) – Add an item to the top.
pop() – Remove and return the top item.
peek() – Look at the top item without removing it.
is_empty() – Check if the stack is empty.

Python Example

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

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

    def pop(self):
        return self.items.pop() if not self.is_empty() else None

    def peek(self):
        return self.items[-1] if not self.is_empty() else None

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

Real-World Uses

Undo functionality – Each action is pushed onto a stack; undo pops the last one.
Browser history – Navigate back by popping pages off the stack.
Expression evaluation – Used in calculators and compilers.

Performance

All operations are O(1) – very efficient.

Queues – First In, First Out (FIFO)

A queue is like a line at a theme park: the first person to arrive is the first to get on the ride.

Core Operations

enqueue(item) – Add an item to the end.
dequeue() – Remove and return the front item.
peek() – Look at the front item without removing it.
is_empty() – Check if the queue is empty.

Python Example

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

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

    def dequeue(self):
        return self.items.pop(0) if not self.is_empty() else None

    def peek(self):
        return self.items[0] if not self.is_empty() else None

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

Real-World Uses

Print queues – Jobs are handled in the order they were submitted.
Customer service lines – First call, first served.
Task scheduling – CPUs often use queues to manage process execution.

Performance

Enqueue is O(1), but dequeue is O(n) due to list shifting in Python.
To improve this, you can use collections.deque for O(1) on both ends.

Choosing Between a Stack and a Queue

Feature	Stack (LIFO)	Queue (FIFO)
Access	Top only	Front only
Use Case	Undo, Backtracking	Scheduling, Messaging
Complexity	O(1) for push/pop	O(1) enqueue, O(n) dequeue (list)

Both structures are simple but powerful. You’ll encounter them often, especially when working with algorithms involving recursion, backtracking, and task management.

Challenge Time! 🚀

Write a program that:

Uses a stack to reverse a word.
Uses a queue to simulate a line of 5 people, where each person gets served in turn.

Try extending the queue version to add new people while others are being served!

Let us know your solutions and questions in the comments. And stay tuned—we’ll be diving into Hash Tables next, unlocking the power of ultra-fast lookup!