Implementing Stacks & Queues

Concept 1: The Stack - Last-In, First-Out (LIFO)

A stack is an abstract data type that serves as a collection of elements, with two principal operations. It operates on a "Last-In, First-Out" (LIFO) principle.

Technical Explanation

The LIFO principle means that the last element added to the stack will be the first one to be removed. The core operations are:

• push(item): Adds an item to the "top" of the stack.
• pop(): Removes and returns the item from the "top" of the stack.
• peek() (or top()): Returns the top item without removing it.
• isEmpty(): Checks if the stack is empty.

All these operations are expected to have a time complexity of $O(1)$.

Metaphor: A Stack of Plates

Imagine a spring-loaded stack of plates in a cafeteria. You can only do two things:

1. Push: Place a new, clean plate on top of the stack.
2. Pop: Take the topmost plate off the stack.
   You cannot take a plate from the middle or the bottom. The last plate you put on is always the first one you take off.

Real-World Use Cases

• Function Call Stack: When you call a function, it's pushed onto the program's call stack. When it returns, it's popped off. This is how your program keeps track of where to return to.
• Undo/Redo Functionality: Each action you take is pushed onto an "undo" stack. When you hit "undo," the last action is popped and reversed.
• Expression Evaluation: Stacks are used to parse and evaluate mathematical expressions (e.g., converting infix to postfix notation).

Python Code Snippet (Conceptual)

Python's built-in list can simulate a stack easily, as its append() and pop() methods (with no index) operate on the end of the list in amortized $O(1)$ time.

# Simulating a stack with a Python list
call_stack = []

print("Simulating function calls...")
call_stack.append("main()")      # main() is called
print(f"Stack: {call_stack}")
call_stack.append("function_A()")# main() calls function_A()
print(f"Stack: {call_stack}")
call_stack.append("function_B()")# function_A() calls function_B()
print(f"Stack: {call_stack}")

print("\nSimulating function returns...")
returned_function = call_stack.pop() # function_B() returns
print(f"Returned: {returned_function}, Stack: {call_stack}")
returned_function = call_stack.pop() # function_A() returns
print(f"Returned: {returned_function}, Stack: {call_stack}")

While this works, building our own stack forces us to understand the underlying mechanics and trade-offs.

Concept 2: Implementing a Stack with a Linked List

A singly linked list is a natural fit for implementing a stack. The "top" of the stack can be mapped directly to the "head" of the list.

Technical Explanation

By using the head of a singly linked list as the top of our stack, we can leverage the $O(1)$ operations we learned about in the previous lesson.

• push(item) becomes insert_at_beginning(item). This involves creating a new node and setting its next pointer to the old head, then updating the head. This is $O(1)$.
• pop() becomes remove_from_beginning(). This involves updating the head to point to head.next. This is also $O(1)$.

Python Code Snippet

Let's build a formal Stack class that encapsulates a linked list.

# We'll reuse the SinglyNode from the previous lesson
class SinglyNode:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

class Stack:
    """A LIFO Stack implemented using a singly linked list."""
    def __init__(self):
        self._head = None
        self._size = 0

    def __len__(self):
        return self._size

    def isEmpty(self):
        return self._size == 0

    def push(self, value):
        """Adds an item to the top of the stack. O(1)"""
        self._head = SinglyNode(value, self._head)
        self._size += 1

    def pop(self):
        """Removes and returns the top item. O(1)"""
        if self.isEmpty():
            raise IndexError("pop from an empty stack")
        value = self._head.value
        self._head = self._head.next
        self._size -= 1
        return value

    def peek(self):
        """Returns the top item without removing it. O(1)"""
        if self.isEmpty():
            raise IndexError("peek from an empty stack")
        return self._head.value

# Example Usage
s = Stack()
s.push(10)
s.push(20)
s.push(30)
print(f"Top of stack: {s.peek()}") # Expected: 30
print(f"Popped: {s.pop()}")       # Expected: 30
print(f"Stack size: {len(s)}")   # Expected: 2

Design Decisions: Linked List vs. Dynamic Array for Stacks

• Linked List:
  • Pro: Truly $O(1)$ push and pop operations. No need for resizing, so performance is consistent.
  • Con: Higher memory footprint per element due to storing a pointer. Can suffer from poor cache locality as nodes may be scattered in memory.
• Dynamic Array:
  • Pro: Better cache performance due to contiguous memory. Lower memory overhead per element.
  • Con: Push operation (append) is amortized $O(1)$. Occasionally, the array must be resized and copied, causing a single, slow operation. For most applications, this is perfectly acceptable.

Concept 3: The Queue - First-In, First-Out (FIFO)

A queue is the counterpart to a stack. It also serves as a collection of elements, but it operates on a "First-In, First-Out" (FIFO) principle.

Technical Explanation

The FIFO principle dictates that the first element added to the queue will be the first one to be removed. The terminology is different from stacks:

• enqueue(item): Adds an item to the "back" or "rear" of the queue.
• dequeue(): Removes and returns the item from the "front" or "head" of the queue.
• front() (or peek()): Returns the front item without removing it.
• isEmpty(): Checks if the queue is empty.

Like stacks, all these operations are expected to have a time complexity of $O(1)$.

Metaphor: A Checkout Line

A queue is exactly like a line at a grocery store checkout.

1. Enqueue: A new person arrives and joins the back of the line.
2. Dequeue: The person at the front of the line is served and leaves.
   The first person to get in line is the first person to be served.

Real-World Use Cases

• Request Handling: A web server puts incoming requests into a queue to be processed one by one, ensuring fairness.
• Print Spooling: When you send multiple documents to a printer, they are placed in a queue.
• Breadth-First Search (BFS): A core graph traversal algorithm that uses a queue to explore nodes level by level. We'll cover this in a future module.

Python Code Snippet (Conceptual)

Python's standard library provides a highly optimized double-ended queue, collections.deque, which is perfect for FIFO operations.

from collections import deque

# Using collections.deque for an efficient queue
request_queue = deque()

request_queue.append("Request 1") # Enqueue
request_queue.append("Request 2") # Enqueue
request_queue.append("Request 3") # Enqueue
print(f"Queue: {request_queue}")

processed_request = request_queue.popleft() # Dequeue
print(f"Processed: {processed_request}, Queue: {request_queue}")
processed_request = request_queue.popleft() # Dequeue
print(f"Processed: {processed_request}, Queue: {request_queue}")

Concept 4: Implementing a Queue with a Linked List

Implementing an efficient queue with a linked list requires a small but crucial enhancement over our stack implementation: a pointer to the tail.

Technical Explanation

To achieve $O(1)$ for both enqueue and dequeue:

• We must dequeue from the head of the list ($O(1)$ remove_from_beginning).
• We must enqueue at the tail of the list.

If we only have a head pointer, enqueuing requires traversing the entire list to find the last node, an $O(N)$ operation. The solution is to maintain a second pointer, tail, that always points to the last node in the list. This allows us to add a new node at the end in $O(1)$ time.

Python Code Snippet

Here is a queue implementation using a singly linked list with head and tail pointers.

# We'll use the same SinglyNode class

class Queue:
    """A FIFO Queue implemented using a singly linked list with head and tail pointers."""
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def isEmpty(self):
        return self._size == 0

    def enqueue(self, value):
        """Adds an item to the back of the queue. O(1)"""
        new_node = SinglyNode(value)
        if self.isEmpty():
            self._head = new_node
            self._tail = new_node
        else:
            self._tail.next = new_node
            self._tail = new_node
        self._size += 1

    def dequeue(self):
        """Removes and returns the front item. O(1)"""
        if self.isEmpty():
            raise IndexError("dequeue from an empty queue")
        value = self._head.value
        self._head = self._head.next
        self._size -= 1
        if self.isEmpty(): # Important edge case!
            self._tail = None
        return value

    def front(self):
        """Returns the front item without removing it. O(1)"""
        if self.isEmpty():
            raise IndexError("front from an empty queue")
        return self._head.value

# Example Usage
q = Queue()
q.enqueue('A')
q.enqueue('B')
print(f"Front of queue: {q.front()}") # Expected: A
print(f"Dequeued: {q.dequeue()}")     # Expected: A
q.enqueue('C')
print(f"Front of queue: {q.front()}") # Expected: B
print(f"Queue size: {len(q)}")       # Expected: 2

Concept 5: The Circular Queue (Ring Buffer)

While a linked list queue is efficient, its scattered memory access can be a bottleneck in high-performance systems. For maximum speed, we turn to arrays, but we need a clever trick to avoid the costly pop(0) operation: the circular buffer.

Technical Explanation

A naive array-based queue where you dequeue from the front (pop(0)) is horribly inefficient ($O(N)$) because all subsequent elements must be shifted.

A circular queue (or ring buffer) solves this. It's a fixed-size array with two pointers (indices): head and tail.

• head: The index of the front element (next to be dequeued).
• tail: The index of the next available slot for an element to be enqueued.

When either pointer reaches the end of the array, it "wraps around" to the beginning. This wrap-around logic is implemented elegantly using the modulo operator (%): next_index = (current_index + 1) % capacity.

How do we know if the queue is empty or full?

1. Empty: The queue is empty when the head and tail pointers are at the same index (if you also track size). A simpler way is to maintain a size counter. The queue is empty when size == 0.
2. Full: The queue is full when size == capacity.

Python Code Snippet

Let's implement a CircularQueue using a fixed-size Python list.

class CircularQueue:
    """A FIFO Queue implemented using a circular buffer (array)."""
    def __init__(self, k: int):
        self._data = [0] * k
        self._capacity = k
        self._head = 0
        self._size = 0

    def enQueue(self, value: int) -> bool:
        """Inserts an element into the circular queue. O(1)"""
        if self.isFull():
            return False
        
        # Calculate tail index using head, size, and capacity
        tail_index = (self._head + self._size) % self._capacity
        self._data[tail_index] = value
        self._size += 1
        return True

    def deQueue(self) -> bool:
        """Deletes an element from the circular queue. O(1)"""
        if self.isEmpty():
            return False
        
        # Head just moves forward, wrapping around
        self._head = (self._head + 1) % self._capacity
        self._size -= 1
        return True

    def Front(self) -> int:
        """Get the front item from the queue."""
        if self.isEmpty():
            return -1
        return self._data[self._head]

    def Rear(self) -> int:
        """Get the last item from the queue."""
        if self.isEmpty():
            return -1
        # Calculate the index of the last element
        rear_index = (self._head + self._size - 1) % self._capacity
        return self._data[rear_index]

    def isEmpty(self) -> bool:
        return self._size == 0

    def isFull(self) -> bool:
        return self._size == self._capacity

Interview Question: High-Performance Buffering

You're designing a system to handle incoming network packets for a router's network interface card (NIC). The rate of packets is extremely high and processing latency must be minimal. Would you choose a linked list-based queue or a circular array-based queue to buffer the packets? Justify your choice.

Answer: For this high-performance, low-latency scenario, the circular array-based queue is the superior choice. The justification rests on two key "under the hood" principles:

1. Cache Locality: The circular array stores packet data in a contiguous block of memory. When the CPU processes one packet, the data for the next several packets is likely already pulled into its high-speed cache (L1/L2). This "cache friendliness" dramatically reduces memory access latency compared to a linked list, where nodes are scattered across memory, causing frequent cache misses.
2. Allocation Overhead: A linked list queue must dynamically allocate memory for each new node on every enqueue operation. This involves system calls, which are relatively slow. The circular array pre-allocates a large buffer once, and enqueue/dequeue operations merely update integer indices, avoiding any per-operation allocation overhead.

Conclusion

Today, you've moved from foundational structures to abstract data types, a key step in algorithmic thinking. You now understand not just what stacks and queues do, but how they are built and the deep performance implications of the choices you make.

Key Takeaways:

• Stacks are LIFO (Last-In, First-Out), perfect for tasks like managing function calls or undo history. They are efficiently implemented with a linked list's head or a dynamic array's end.
• Queues are FIFO (First-In, First-Out), ideal for processing items in order, like server requests or print jobs.
• Linked List Queues are dynamic and provide true $O(1)$ operations but suffer from pointer overhead and poor cache locality.
• Array-based Queues require a circular buffer to achieve $O(1)$ performance. This implementation offers superior cache performance and is the standard for high-throughput, low-latency systems, at the cost of having a fixed capacity.

Preview of the Next Lesson

We've focused on data structures that add and remove elements one at a time. In the next lesson, we will explore a powerful algorithmic pattern for processing contiguous blocks of data: the sliding window pattern. This technique is often used to find optimal subarrays or substrings in linear time, and you'll see how a queue-like structure (specifically, a deque) is often the key to an efficient implementation.