Stack & Queues in Data Structure

In previous weeks, I discussed Arrays and Linked Lists. Today, I'll dive into two more fundamental data structures: Stacks and Queues.

What is a Stack?

A Stack is a linear data structure that follows a specific order of operations known as FILO (First In Last Out) or LIFO (Last In First Out). This means the most recently added item is the first one to be removed. Common operations performed on a stack include:

• push: Add an element to the top of the stack

• pop: Remove the last element added (the top element)

• peek: View the top element without removing it

Stacks can be easily implemented in Python using the built-in list data structure. The append() method adds elements to the list (push), and pop() removes the last element (pop), both operating in O(1) time.

Here’s an example of a basic stack implementation in Python:

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

    def pop(self) -> None:
        if len(self.values) != 0:
            self.values.pop()
        else:
            raise IndexError("Pop from an empty stack")

    def push(self, value) -> None:
        self.values.append(value)

    def peek(self):
        if len(self.values) != 0:
            return self.values[-1]
        else:
            raise IndexError("Peek from an empty stack")

What is a Queue?

A Queue is another linear data structure that maintains the order of elements in a FIFO (First In First Out) or LILO (Last In Last Out) fashion. Elements are added at the rear (enqueue) and removed from the front (dequeue). Queues are particularly useful in scenarios like:

• Handling print jobs

• Managing web server requests

• Task scheduling in operating systems

Unlike Stacks, Python’s built-in list is not the most efficient choice for implementing queues, as removing elements from the front of a list takes O(n) time. Instead, Queues can be efficiently implemented using Singly Linked Lists or Doubly Linked Lists.

Here’s an example of a Queue implementation using a Singly Linked List in Python:

class Node:
    def __init__(self, val=0, next=None) -> None:
        self.val = val
        self.next: None | Node = next

class Queue:
    def __init__(self) -> None:
        self.head = None
        self.tail = None

    def enqueue(self, value) -> None:
        new_node = Node(value)
        if self.tail:
            self.tail.next = new_node
        self.tail = new_node
        if not self.head:
            self.head = new_node

    def dequeue(self) -> None:
        if self.head:
            self.head = self.head.next
            if not self.head:
                self.tail = None
        else:
            raise IndexError("Queue is empty")

    def peek(self):
        if self.head:
            return self.head.val
        else:
            raise IndexError("Queue is empty")

    def print_all(self) -> None:
        curr = self.head
        while curr:
            print(curr.val, end=" -> ")
            curr = curr.next
        print("None")

This implementation efficiently adds and removes elements in O(1) time, avoiding the inefficiencies of list-based queue implementations.

Conclusion

• Stacks are ideal for scenarios where you need Last In First Out behavior, such as in function call management or browser history.

• Queues are suited for First In First Out operations, making them useful for managing tasks in sequential order, like processing server requests.

Both data structures are key to efficient problem-solving in various applications, and knowing how to implement them optimally ensures better performance and resource management.