Stacks & Queues

Stacks and queues are abstract data types that restrict how elements are added and removed. They model real-world waiting lines and last-in-first-out behavior.

Stack — LIFO (Last In, First Out)

A stack is like a stack of plates: you add to the top and remove from the top. The last item placed is the first one retrieved.

Stack Operations

• push(item) — adds an item to the top
• pop() — removes and returns the top item
• peek() — returns the top item without removing it
• is_empty() — checks if the stack is empty

Array-Based Stack

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

    def push(self, item):
        self.items.append(item)

    def pop(self):
        if self.is_empty():
            return None
        return self.items.pop()

    def peek(self):
        if self.is_empty():
            return None
        return self.items[-1]

    def is_empty(self):
        return len(self.items) == 0

Linked List Stack

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

class LinkedListStack:
    def __init__(self):
        self.top = None

    def push(self, data):
        node = StackNode(data)
        node.next = self.top
        self.top = node

    def pop(self):
        if self.top is None:
            return None
        data = self.top.data
        self.top = self.top.next
        return data

    def peek(self):
        return self.top.data if self.top else None

    def is_empty(self):
        return self.top is None

Stack Applications

• Undo/Redo: Text editors push each change onto a stack; Undo pops it.
• Call Stack: Functions push a stack frame when called and pop it on return.
• Expression Evaluation: Converting infix to postfix, evaluating postfix expressions.
• Syntax Parsing: Checking matching parentheses, braces, and brackets.

Queue — FIFO (First In, First Out)

A queue is like a line at a ticket counter: the first person in line is the first one served.

Queue Operations

• enqueue(item) — adds an item to the rear
• dequeue() — removes and returns the front item
• front() — returns the front item without removing it
• is_empty() — checks if the queue is empty

Array-Based Queue

class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        if self.is_empty():
            return None
        return self.items.pop(0)

    def front(self):
        return self.items[0] if not self.is_empty() else None

    def is_empty(self):
        return len(self.items) == 0

Circular Queue

A circular queue reuses array slots by wrapping around. It uses a fixed-size array with front and rear pointers.

class CircularQueue:
    def __init__(self, capacity):
        self.capacity = capacity
        self.items = [None] * capacity
        self.front = 0
        self.rear = 0
        self.size = 0

    def enqueue(self, item):
        if self.size == self.capacity:
            return False
        self.items[self.rear] = item
        self.rear = (self.rear + 1) % self.capacity
        self.size += 1
        return True

    def dequeue(self):
        if self.size == 0:
            return None
        item = self.items[self.front]
        self.front = (self.front + 1) % self.capacity
        self.size -= 1
        return item

Deque (Double-Ended Queue)

Allows insertion and deletion from both ends. Python's collections.deque is a highly optimized implementation.

Priority Queue

Elements are dequeued in order of priority, not insertion order. Typically implemented with a binary heap. Operations: O(log n) for insertion and deletion.

Time Complexities

• Stack push/pop/peek: O(1)
• Queue enqueue/dequeue: O(1) amortized (or with circular buffer)
• Priority queue insert/delete: O(log n)