Stacks, Queues & Linked Lists

Introduction

Data structures are fundamental building blocks for software development. They provide efficient ways to store and manage data, enabling developers to build complex applications with ease. In this section, we will explore three essential data structures: Stacks, Queues, and Linked Lists. Each of these structures has unique characteristics and is suited for different types of problems.

Stacks

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. This means that the last element added to the stack will be the first one to be removed. Think of it like a stack of plates; you can only add or remove the top plate.

Implementation in Python

Python provides several ways to implement a stack, but the most common is using a list with its built-in methods append() and pop(). Here's how you can create a simple stack:

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

    def push(self, item):
        """Add an item to the top of the stack."""
        self.items.append(item)

    def pop(self):
        """Remove and return the top item from the stack."""
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("pop from empty stack")

    def peek(self):
        """Return the top item from the stack without removing it."""
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("peek from empty stack")

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

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

# Example usage
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # Output: 3
print(stack.peek()) # Output: 2
print(stack.is_empty()) # Output: False

Use Cases

• Function Call Management: Stacks are used to manage function calls in programming languages. Each time a function is called, its context is pushed onto the stack, and when it returns, the context is popped off.
• Expression Evaluation: Stacks are used in evaluating expressions, especially for converting infix notation to postfix or prefix notation.

Queues

A queue is another linear data structure that follows the First-In-First-Out (FIFO) principle. This means that the first element added to the queue will be the first one to be removed. Think of it like a line at a store; the person who arrives first gets served first.

Implementation in Python

Python can implement queues using lists, but for better performance, especially with large datasets, you should use the collections.deque class. Here's how:

from collections import deque

# Creating a Queue class
class Queue:
    def __init__(self):
        self.items = deque()

    def enqueue(self, item):
        """Add an item to the end of the queue."""
        self.items.append(item)

    def dequeue(self):
        """Remove and return the front item from the queue."""
        if not self.is_empty():
            return self.items.popleft()
        raise IndexError("dequeue from empty queue")

    def peek(self):
        """Return the front item from the queue without removing it."""
        if not self.is_empty():
            return self.items[0]
        raise IndexError("peek from empty queue")

    def is_empty(self):
        """Check if the queue is empty."""
        return len(self.items) == 0

    def size(self):
        """Return the number of items in the queue."""
        return len(self.items)

# Example usage
queue = Queue()
queue.enqueue(1)
queue.enqueue(2)
queue.enqueue(3)
print(queue.dequeue()) # Output: 1
print(queue.peek())    # Output: 2
print(queue.is_empty())# Output: False

Use Cases

• Task Scheduling: Queues are used in operating systems to manage tasks waiting for execution.
• Breadth-First Search (BFS): Queues are essential in BFS algorithms, where nodes are explored level by level.

Linked Lists

A linked list is a linear data structure consisting of nodes. Each node contains data and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists do not require contiguous memory locations for storing elements.

Types of Linked Lists

1. Singly Linked List: Each node has a single pointer to the next node.
2. Doubly Linked List: Each node has two pointers: one pointing to the next node and another pointing to the previous node.
3. Circular Linked List: The last node points back to the first node, forming a loop.

Implementation in Python

Here's how you can implement a singly linked list:

# Node class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Singly Linked List class
class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        """Add a new node with the given data at the end of the list."""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def prepend(self, data):
        """Add a new node with the given data at the beginning of the list."""
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def delete_with_value(self, key):
        """Delete the first occurrence of the node with the given value."""
        current = self.head
        if current and current.data == key:
            self.head = current.next
            current = None
            return
        prev = None
        while current and current.data != key:
            prev = current
            current = current.next
        if not current:
            return
        prev.next = current.next
        current = None

    def print_list(self):
        """Print the elements of the list."""
        current = self.head
        while current:
            print(current.data, end=" -> ")
            current = current.next
        print("None")

# Example usage
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.prepend(0)
llist.print_list() # Output: 0 -> 1 -> 2 -> None
llist.delete_with_value(1)
llist.print_list() # Output: 0 -> 2 -> None

Use Cases

• Dynamic Memory Allocation: Linked lists are used in systems where memory allocation is dynamic, such as managing free blocks of memory.
• Implementing Stacks and Queues: Linked lists can be used to implement stacks and queues, especially when you need efficient insertions and deletions.

Best Practices

1. Choose the Right Data Structure: Always choose the data structure that best fits your problem. For example, use a stack for LIFO operations and a queue for FIFO operations.
2. Consider Time Complexity: Be aware of the time complexity of each operation in the data structure you are using. For instance, appending to a list is O(1) but inserting at the beginning is O(n).
3. Handle Edge Cases: Always handle edge cases such as empty structures or null values to avoid runtime errors.
4. Use Built-in Libraries: When possible, use Python's built-in libraries like collections.deque for queues, as they are optimized and provide better performance.

Conclusion

Stacks, Queues, and Linked Lists are fundamental data structures in computer science and software engineering. Understanding their properties, implementations, and use cases will help you design efficient algorithms and solve complex problems. By mastering these concepts, you'll be well-equipped to tackle a wide range of programming challenges.