Stacks and Queues

 Stacks and queues are essential data structures in programming, each with unique characteristics and uses.

1.Stack (LIFO - Last In, First Out)

A stack is a LIFO (Last In, First Out) data structure, where the last element added is the first one removed. Think of it like a stack of plates: you add to the top, and you also remove from the top.

In Python, we can use a list to implement a stack because lists support adding and removing items from the end in constant time, which aligns with stack operations.

Stack Operations

1. Push: Add an item to the stack.
2. Pop: Remove the last item added.
3. Peek: Get the value of the last item without removing it.
4. IsEmpty: Check if the stack is empty.

Here's a simple implementation of a stack using a list in Python:

class Stack:

    def __init__(self):

        self.stack = []

    def push(self, item):

        self.stack.append(item)

    def pop(self):

        if not self.is_empty():

            return self.stack.pop()

        else:

            return "Stack is empty"

    def peek(self):

        if not self.is_empty():

            return self.stack[-1]

        else:

            return "Stack is empty"

    def is_empty(self):

        return len(self.stack) == 0

    def size(self):

        return len(self.stack)

# Example Usage

s = Stack()

s.push(5)

s.push(10)

print("Peek:", s.peek())  # Output: 10

print("Pop:", s.pop())    # Output: 10

print("Is Empty:", s.is_empty())  # Output: False

Practical Example of a Stack

Stacks are often used in:

• Backtracking problems: e.g., the undo feature in applications.
• Recursive function calls: Python uses a call stack to manage function calls.
• Balancing symbols: e.g., checking for balanced parentheses.

2.Queue (FIFO - First In, First Out)

A queue is a FIFO (First In, First Out) data structure, where the first element added is the first one removed. Imagine it like a line at a supermarket checkout: the first person in line is the first served.

In Python, you can implement a queue using a list, but it’s inefficient for larger queues because removing elements from the front takes $O(n)$ time. Instead, collections.deque is ideal as it provides fast O(1) time complexity for both adding and removing elements from both ends.

Queue Operations

1. Enqueue: Add an item to the end of the queue.
2. Dequeue: Remove the item from the front of the queue.
3. Peek: Get the value of the first item without removing it.
4. IsEmpty: Check if the queue is empty.

Here’s an example using deque from Python’s collections module:

from collections import deque

class Queue:

    def __init__(self):

        self.queue = deque()

    def enqueue(self, item):

        self.queue.append(item)

    def dequeue(self):

        if not self.is_empty():

            return self.queue.popleft()

        else:

            return "Queue is empty"

    def peek(self):

        if not self.is_empty():

            return self.queue[0]

        else:

            return "Queue is empty"

    def is_empty(self):

        return len(self.queue) == 0

    def size(self):

        return len(self.queue)

# Example Usage

q = Queue()

q.enqueue("apple")

q.enqueue("banana")

print("Peek:", q.peek())  # Output: apple

print("Dequeue:", q.dequeue())  # Output: apple

print("Is Empty:", q.is_empty())  # Output: False

Practical Example of a Queue

Queues are widely used in:

• Scheduling tasks in operating systems.
• Handling requests in web servers.
• Breadth-first search (BFS) in graph algorithms.

Stacks and queues are powerful, simple tools for handling ordered data access. Their efficient data management patterns are fundamental in programming and are implemented easily using Python’s list and deque structures.