09. Crafting Elegant Code with Stacks and Queues

Data structures are essential not only for performance but also for creating code that is simpler and easier to read. This chapter introduces stacks and queues, which are simply arrays with specific restrictions. These restrictions make them elegant tools for handling temporary data—information that is processed and then discarded, such as food orders in a diner.

Stacks

A stack is a data structure based on an array but imposes strict rules on how data can be accessed:

• Insertion (Pushing): Data can be inserted only at the end (the top) of the stack.
• Deletion (Popping): Data can be deleted only from the end (the top) of the stack.
• Reading (Peeking): Only the last element (the top) of a stack can be read.

Think of a stack like a stack of dishes . You can only add a dish to the top, remove a dish from the top, and look at the dish on the very top. So, you have to consider that:

• The end of the array is the stack’s top.
• The beginning of the array is the stack’s bottom.

We use the terms push for insertion and pop for deletion:

1. Start Empty: Stack: $\text{[ ]}$
2. Push 5: The 5 is added to the top (end). Stack: $\text{[5]}$
3. Push 3: The 3 is added to the top. Stack: $\text{[5, 3]}$
4. Push 0: The 0 is added to the top. Stack: $\text{[5, 3, 0]}$

Popping the example stack:

1. Pop 0: The last item pushed (0) is removed first. Stack: $\text{[5, 3]}$
2. Pop 3: The next item at the top (3) is removed. Stack: $\text{[5]}$

The defining characteristic of a stack is its access pattern, summarized by the acronym LIFO: Last In, First Out. It indicates that the last item added (pushed) onto a stack is always the first item to be removed (popped).

Despite the restrictions, stacks are incredibly useful because they impose order, which simplifies many algorithms dealing with temporary data.

Abstract Data Types (ADT)

A stack is an example of an Abstract Data Type (ADT). Unlike an array, which is a built-in data structure that interacts directly with memory, an ADT is a set of theoretical rules and constraints that dictate how data should be handled, regardless of the underlying implementation.

Since a stack is not always a built-in type, it must be implemented on top of a built-in structure, typically an array. The Python Stack class demonstrates this:

class Stack:
    def __init__(self):
        self.data = [] # The underlying array
    
    def push(self, element):
        self.data.append(element) # Array insertion at the end
    
    def pop(self):
        # ... logic to return self.data.pop()
    
    def read(self):
        # ... logic to return self.data[-1]

By wrapping the array in the Stack class, we create an interface that enforces the LIFO (Last In, First Out) rules. This restriction is the essence of the ADT.

The Set is another example of an ADT, representing a theoretical list of non-duplicated data elements, which can be implemented using arrays or hash tables under the hood.

Stacks in Action: Code Linter

Stacks are powerful tools for handling temporary data where the order of processing is critical. A classic example is a program, like a linter, that validates the balanced and correctly ordered syntax of braces ((, ), [, ], {, }).

The linter must detect three types of brace errors:

Type	Description	Example
Type #1	Unclosed opening brace.	(var x = 2;
Type #2	Closing brace without a preceding opening brace.	var x = 2;)
Type #3	Mismatched closing brace.	(var x = [1, 2, 3)];

The elegance of the stack comes from its LIFO property, which perfectly models the nesting requirement of braces: the last brace opened must be the first one closed. The algorithm uses an empty stack and processes the code line character by character:

1. Opening Brace Found: The brace is pushed onto the stack. This signifies we are waiting for a match.
2. Closing Brace Found:
   • Empty Stack?: If the stack is empty, it’s Syntax Error Type #2 (closing brace has no opening counterpart).
   • Pop and Check: The top opening brace is popped and checked for a match against the current closing brace. If they don’t match, it’s Syntax Error Type #3.
3. End of Line: If the entire line is processed and the stack is not empty, it means the remaining opening braces were never closed. This is Syntax Error Type #1.

Let’s see this process step by step:

The stack serves as a temporary container to keep track of the history of unmatched opening braces, allowing for an efficient and beautiful solution.

Code Implementation (Linter lint Method)

The implementation uses the Stack class to enforce the rules:

# ... Inside Linter.lint(text) method ...
 
# 1. Clear any previous data from stack
while self.stack.read():
    self.stack.pop()
matching_braces = {"(": ")", "[": "]", "{": "}"}
 
for char in text:
    if char in matching_braces.keys(): # Opening brace
        self.stack.push(char)
    elif char in matching_braces.values(): # Closing brace
        if not self.stack.read():
            return char + " does not have opening brace" # Type #2
        else:
            popped_opening_brace = self.stack.pop()
            if char != matching_braces.get(popped_opening_brace):
                return char + " has mismatched opening brace" # Type #3
 
# 4. Check for unclosed braces after loop finishes
if self.stack.read():
    return self.stack.read() + " does not have closing brace" # Type #1
return True

The algorithm’s time complexity is $O(N)$, where $N$ is the number of characters in the code line, because each character is processed exactly once, and each stack operation (push, pop, read) is an $O(1)$ operation on an array.

The Importance of Constrained Data Structures

Although an array can technically perform all the operations of a stack, constrained data structures like the stack and queue are vital for several reasons:

• Preventing Bugs: The constraints of a stack enforce the rules of the algorithm. In the linter example, the algorithm fails if elements are removed from the middle. By using a stack, a programmer is prevented from inadvertently removing items from anywhere but the top, eliminating a source of bugs.
• New Mental Models: Constrained structures provide a specific mental model for problem-solving. The stack introduces the core concept of a LIFO (Last In, First Out) process, which can be elegantly applied to solve various problems.
• Code Elegance and Readability: Using a stack makes the code familiar and elegant to other developers. When a reader sees a stack being utilized, they immediately understand that the algorithm is operating with a LIFO-based process, improving code comprehension.

Stack Wrap-Up

Stacks are the ideal data structure for processing any temporary data that adheres to the LIFO (Last In, First Out) principle. A common real-world example is the Undo function in a word processor:

• Each user action (e.g., a keystroke) is pushed onto the stack.
• When the user clicks “Undo,” the most recent action is popped off the stack and reversed, guaranteeing that actions are undone in the reverse order they were performed.

Queues

A queue is an Abstract Data Type (ADT) designed for processing temporary data, but unlike a stack, it adheres to the First In, First Out (FIFO) principle.

You can visualize a queue as a line of people at a theater: the first person to enter the line is the first person to leave it and enter the theater.

The structure is typically depicted horizontally, and its ends are referred to as the front and the back.

A queue is an array with the following three restrictions:

• Insertion (Enqueue): Data can be inserted only at the back (end) of a queue. (Same as a stack.)
• Deletion (Dequeue): Data can be deleted only from the front of a queue. (Opposite of a stack.)
• Reading (Peek): Only the element at the front of a queue can be read. (Opposite of a stack.)

The term for inserting data is enqueue, and the term for removing data is dequeue. Let’s make an example of both operations:

1. Insert 5: $\text{[5]}$ (5 is at the front and back)
2. Insert 9: $\text{[5, 9]}$ (5 is front, 9 is back)
3. Insert 100: $\text{[5, 9, 100]}$ (5 is front, 100 is back)

Now, dequeue operations remove from the front:

1. Remove 5: The first item inserted (5) is the first removed. $\text{[9, 100]}$
2. Remove 9: $\text{[100]}$

Queue Implementation

A queue is implemented as an ADT using an array under the hood:thon

class Queue:
    def __init__(self):
        self.data = [] # The underlying array
 
    def enqueue(self, element):
        self.data.append(element) # Insert at the end (O(1))
 
    def dequeue(self):
        if len(self.data) > 0:
            return self.data.pop(0) # REMOVE from the front/index 0 (O(N))
        else:
            return None
    
    def read(self):
        if len(self.data) > 0:
            return self.data[0] # READ the front element (O(1))

Note that the dequeue operation, using pop(0) on a standard array, is $O(N)$ because it requires shifting all remaining elements to fill the gap created by removing the first element.

Queues in Action: Print Manager

Queues are frequently used in applications that require tasks to be processed in the strict order they were received, such as: printing jobs, background workers, and handling asynchronous requests.

A PrintManager uses a queue to ensure documents are printed in the order they were submitted (FIFO).

1. Enqueue: The queue_print_job method uses self.queue.enqueue(document) to add documents to the back of the queue.
2. Process: The run method processes the jobs, where the while loop continuously checks the front of the queue (read()) and uses dequeue() to remove and process the document at the front.

import queue
 
class PrintManager:
	def __init__(self):
		self.queue = queue.Queue()
	def queue_print_job(self, document):
		self.queue.enqueue(document)
	def run(self):
		while self.queue.read():
			self.print_document(self.queue.dequeue())
	def print_document(self, document):
	# Code to run the actual printer goes here.
	# For demo purposes, we'll print to the terminal:
	print(document)

We can then utilize this class as follows:

print_manager = PrintManager()
print_manager.queue_print_job("First Document")
print_manager.queue_print_job("Second Document")
print_manager.queue_print_job("Third Document")
print_manager.run()

Output:

First Document
Second Document
Third Document

The queue perfectly models and enforces this real-world scenario where events (documents, requests, airplanes, patients) must be handled sequentially in the order of arrival.