Data StructuresBeginner10 min readUpdated March 2025

Stacks and Queues

Stacks (LIFO) and Queues (FIFO) are abstract data types that restrict how elements are added and removed. Despite their simplicity, they are fundamental to algorithms like DFS, BFS, expression evaluation, and task scheduling.

The Stack: Last In, First Out

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. Think of a stack of plates — you can only add or remove from the top.

Core operations: - push(item) — Add item to the top: O(1) - pop() — Remove and return the top item: O(1) - peek() / top() — View the top item without removing: O(1) - is_empty() — Check if stack is empty: O(1)

Real-world applications: - Function call stack (recursion) - Undo/redo in text editors - Browser back button history - Balanced parentheses checking - Expression evaluation (infix to postfix)

The Queue: First In, First Out

A queue is a linear data structure that follows the FIFO (First In, First Out) principle. Think of a line at a checkout — the first person in line is the first to be served.

Core operations: - enqueue(item) — Add item to the back: O(1) - dequeue() — Remove and return the front item: O(1) - peek() / front() — View the front item: O(1) - is_empty() — Check if queue is empty: O(1)

Real-world applications: - BFS (Breadth-First Search) - Task scheduling (OS process queues) - Print spooler - Message queues (Kafka, RabbitMQ) - Rate limiting

Implementing Stack and Queue in Python

Python provides efficient implementations using lists and deque:

python

from collections import deque

# ---- Stack using Python list ----
class Stack:
    def __init__(self):
        self._data = []

    def push(self, item):
        self._data.append(item)       # O(1) amortized

    def pop(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._data.pop()       # O(1)

    def peek(self):
        if self.is_empty():
            raise IndexError("Stack is empty")
        return self._data[-1]

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

    def __len__(self):
        return len(self._data)

# ---- Queue using collections.deque ----
# deque provides O(1) append and popleft (list.pop(0) is O(n)!)
class Queue:
    def __init__(self):
        self._data = deque()

    def enqueue(self, item):
        self._data.append(item)       # O(1)

    def dequeue(self):
        if self.is_empty():
            raise IndexError("Queue is empty")
        return self._data.popleft()   # O(1)

    def peek(self):
        return self._data[0]

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

# ---- Application: Balanced Parentheses ----
def is_balanced(s):
    stack = Stack()
    pairs = {')': '(', '}': '{', ']': '['}
    for char in s:
        if char in '({[':
            stack.push(char)
        elif char in ')}]':
            if stack.is_empty() or stack.pop() != pairs[char]:
                return False
    return stack.is_empty()

print(is_balanced("({[]})"))   # True
print(is_balanced("({[})"))    # False

# ---- Application: BFS using Queue ----
from collections import defaultdict

def bfs(graph, start):
    visited = set()
    queue = Queue()
    queue.enqueue(start)
    visited.add(start)
    order = []
    while not queue.is_empty():
        node = queue.dequeue()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.enqueue(neighbor)
    return order

Monotonic Stack

A monotonic stack maintains elements in either increasing or decreasing order. It is a powerful pattern for problems involving "next greater element," "largest rectangle," and "trapping rain water":

python

# Next Greater Element using Monotonic Stack - O(n)
def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n
    stack = []   # Stores indices

    for i in range(n):
        # While stack not empty and current element > element at stack top
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

print(next_greater_element([4, 1, 2, 5, 3]))
# [-1, 2, 5, -1, -1] -> 4 has no greater, 1's next greater is 2, etc.

Key Takeaways

Stacks are LIFO — push and pop from the same end. Used for DFS, recursion, and undo operations.
Queues are FIFO — enqueue at back, dequeue from front. Used for BFS and task scheduling.
Use collections.deque for queues in Python — list.pop(0) is O(n), deque.popleft() is O(1).
Monotonic stacks solve "next greater/smaller element" problems in O(n) instead of O(n^2).
Both stacks and queues have O(1) push/enqueue and pop/dequeue operations.

Contact Us

Have a question or feedback? Fill out the form below or reach us directly at support@nvaitraining.com