Implementing Linear ADTs: Stack and Queue

TL;DR

You'll learn how to implement two fundamental linear ADTs, Stack and Queue, using common underlying data structures like arrays and linked lists. Stacks use a Last-In, First-Out (LIFO) principle, while Queues use a First-In, First-Out (FIFO) principle. Understanding their operations and choosing the right implementation are key to efficient data management.

1. The Mental Model

Imagine a Stack like a stack of plates: you add new plates to the top, and you can only take plates from the top. A Queue is like a line at a store: people join at the back, and the person at the front gets served first.

2. The Core Material

Linear ADTs like Stack and Queue store data in a sequential order. The difference lies in how elements are added and removed.

2.1 Stack: LIFO (Last-In, First-Out)

Photo by Michael Orshan on Pexels

A Stack has two primary operations:
* push(item): Adds an item to the top of the stack.
* pop(): Removes and returns the item from the top of the stack. If the stack is empty, it usually raises an error.

Other common operations include peek() (returns the top item without removing it) and is_empty() (checks if the stack has any items).

Implementation Choices for Stack:

1. Using a Python List (Dynamic Array): This is often the simplest approach.

   • push() maps to list.append().
   • pop() maps to list.pop().
   • This is efficient because append and pop from the end of a Python list are generally O(1) on average.

2. Using a Linked List:

   • Each node stores an item and a reference to the next node.
   • push() adds a new node at the head (front) of the list.
   • pop() removes the node at the head of the list.
   • Both operations are O(1) since you're always modifying the head.

2.2 Queue: FIFO (First-In, First-Out)

Photo by Sóc Năng Động on Pexels

A Queue has two primary operations:
* enqueue(item): Adds an item to the rear (back) of the queue.
* dequeue(): Removes and returns the item from the front of the queue. If the queue is empty, it usually raises an error.

Other common operations include peek() (returns the front item without removing it) and is_empty().

Implementation Choices for Queue:

1. Using a Python List (Dynamic Array):

   • enqueue() maps to list.append() (adding to the back).
   • dequeue() maps to list.pop(0) (removing from the front).
   • Caution: list.pop(0) is inefficient, as it requires shifting all subsequent elements, making it O(N) where N is the number of items. This isn't ideal for large queues.

2. Using a collections.deque (Double-Ended Queue):

   • deque is optimized for adding and removing from both ends.
   • enqueue() maps to deque.append().
   • dequeue() maps to deque.popleft().
   • Both operations are O(1). This is generally the preferred Python implementation for queues.

3. Using a Linked List: This is the most common textbook approach for efficient queues.

   • You maintain pointers to both the head (front) and tail (rear) of the list.
   • enqueue() adds a new node at the tail.
   • dequeue() removes the node at the head.
   • Both operations are O(1).

Here's a diagram summarizing the core operations and underlying structures:

graph TD
    A["ADT Type"] --> B["Stack (LIFO)"];
    A --> C["Queue (FIFO)"];

    B --> B1["push(item)"];
    B --> B2["pop()"];
    B --> B3["peek()"];

    C --> C1["enqueue(item)"];
    C --> C2["dequeue()"];
    C --> C3["peek()"];

    B1 --> B_Impl1["Python List: .append()"];
    B2 --> B_Impl2["Python List: .pop()"];
    B_Impl1 & B_Impl2 --> B_Perf1["O(1) average"];

    B1 --> B_LL_push["Linked List: Add to head"];
    B2 --> B_LL_pop["Linked List: Remove from head"];
    B_LL_push & B_LL_pop --> B_Perf2["O(1)"];

    C1 --> C_Impl1["Python List: .append()"];
    C2 --> C_Impl2["Python List: .pop(0)"];
    C_Impl1 & C_Impl2 --> C_Perf1["O(N) for .pop(0) - Inefficient"];

    C1 --> C_Deque1["collections.deque: .append()"];
    C2 --> C_Deque2["collections.deque: .popleft()"];
    C_Deque1 & C_Deque2 --> C_Perf2["O(1)"];

    C1 --> C_LL_enqueue["Linked List: Add to tail"];
    C2 --> C_LL_dequeue["Linked List: Remove from head"];
    C_LL_enqueue & C_LL_dequeue --> C_Perf3["O(1)"];

3. Worked Example

Let's implement a simple Stack using a Python list:

class MyStack:
    def __init__(self):
        self._data = [] # Internal list to store stack elements

    def push(self, item):
        """Adds an item to the top of the stack."""
        self._data.append(item)
        print(f"Pushed: {item}. Stack: {self._data}")

    def pop(self):
        """Removes and returns the item from the top of the stack."""
        if self.is_empty():
            raise IndexError("Stack is empty, cannot pop.")
        item = self._data.pop()
        print(f"Popped: {item}. Stack: {self._data}")
        return item

    def peek(self):
        """Returns the item from the top of the stack without removing it."""
        if self.is_empty():
            raise IndexError("Stack is empty, no top item.")
        return self._data[-1]

    def is_empty(self):
        """Checks if the stack is empty."""
        return len(self._data) == 0

    def size(self):
        """Returns the number of items in the stack."""
        return len(self._data)

# Demonstrate the Stack
stack = MyStack()
print(f"Is empty? {stack.is_empty()}") # Output: Is empty? True

stack.push(10) # Output: Pushed: 10. Stack: [10]
stack.push(20) # Output: Pushed: 20. Stack: [10, 20]
stack.push(30) # Output: Pushed: 30. Stack: [10, 20, 30]

print(f"Top item: {stack.peek()}") # Output: Top item: 30
print(f"Stack size: {stack.size()}") # Output: Stack size: 3

stack.pop() # Output: Popped: 30. Stack: [10, 20]
stack.pop() # Output: Popped: 20. Stack: [10]

print(f"Is empty? {stack.is_empty()}") # Output: Is empty? False

stack.push(40) # Output: Pushed: 40. Stack: [10, 40]
stack.pop() # Output: Popped: 40. Stack: [10]
stack.pop() # Output: Popped: 10. Stack: []

print(f"Is empty? {stack.is_empty()}") # Output: Is empty? True

try:
    stack.pop()
except IndexError as e:
    print(f"Error: {e}") # Output: Error: Stack is empty, cannot pop.

4. Key Takeaways

• Stacks follow a LIFO (Last-In, First-Out) principle, adding and removing from the same end.
• Queues follow a FIFO (First-In, First-Out) principle, adding to one end and removing from the other.
• For Stacks, a Python list's append() and pop() (from the end) provide efficient O(1) operations.
• For Queues, a Python list's pop(0) is inefficient (O(N)); collections.deque or a custom linked list implementation offers efficient O(1) operations.
• Both ADTs can be efficiently implemented using linked lists by carefully managing head and tail pointers.
• peek() allows you to inspect the top/front element without modifying the structure.
• Always check if the ADT is is_empty() before attempting to pop() or dequeue() to avoid errors.

Common Mistakes to Avoid:
- Using list.pop(0) for a Queue in Python; always opt for collections.deque or a linked list instead.
- Forgetting to handle empty stack/queue conditions, which can lead to IndexError or None being returned unexpectedly.
- Confusing LIFO and FIFO principles during implementation or usage.
- In a linked list queue, failing to update both head and tail pointers correctly, especially when the queue becomes empty or has only one element.

5. Now Try It

Implement a Queue class in Python using collections.deque. Include enqueue(item), dequeue(), peek(), is_empty(), and size() methods. Then, write a short script to enqueue three different items, peek at the front, dequeue two items, and check if it's empty, printing the queue's state or relevant output after each major operation.

What success looks like: Your Queue class performs all operations correctly and efficiently, mirroring the behavior of a real-world queue, with enqueue and dequeue being O(1).