Python · Heaps · Stacks · Queues

Complete Guide to Heaps, Stacks & Queues in Python

In this chapter you will learn three fundamental data structures: Stacks (LIFO), Queues (FIFO) and Heaps (priority queues), with diagrams, time complexity and Python implementations.

What you will learn

• How stacks, queues and heaps are structured and how they behave
• When to use LIFO vs FIFO vs priority-based ordering
• Python implementations using list, deque and heapq
• Real-world use cases (undo, schedulers, graph algorithms, etc.)

STACK · LIFO

1. Stacks (LIFO)

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element added is the first one removed – like a stack of plates.

1.1 What is a Stack?

A stack is a linear data structure that follows the LIFO (Last In, First Out) principle. The last element added is the first one removed – like a stack of plates.

1.2 Core Stack Operations

Operation	Description	Time
push(x)	Insert item onto the top of the stack	O(1)
pop()	Remove and return top item	O(1)
peek()	Return top item without removing it	O(1)
is_empty()	Check if stack has no elements	O(1)

1.3 Stack Using Python List

Python's built-in list can be used as a stack with append() and pop() methods.

# Using Python list as a stack stack = [] # push stack.append(10) stack.append(20) stack.append(30) print(stack) # [10, 20, 30] # pop (LIFO) print(stack.pop()) # 30 print(stack.pop()) # 20 print(stack.pop()) # 10 Run Reset

1.4 Custom Stack Class

Here is a simple implementation of a Stack class in Python:

class Stack: def __init__(self): self.items = [] def push(self, value): self.items.append(value) def pop(self): if not self.items: return None return self.items.pop() def peek(self): return self.items[-1] if self.items else None def is_empty(self): return len(self.items) == 0 def __repr__(self): return f"Stack({self.items})" Run Reset

1.5 Real-World Uses of Stacks

Stacks are widely used in various applications, such as:

• Undo/redo (text editors, Photoshop)
• Browser history (Back button)
• Expression evaluation (parsing, calculators)
• Checking balanced parentheses
• Depth-First Search (DFS) in graphs/trees

QUEUE · FIFO

2. Queues (FIFO)

A queue is a linear data structure that follows FIFO (First In, First Out). The first element added is the first one removed – like a line of people waiting for tickets.

2.1 What is a Queue?

A queue is a linear data structure that follows FIFO (First In, First Out). The first element added is the first one removed – like a line of people waiting for tickets.

2.2 Core Queue Operations

The main operations for a queue are:

Operation	Description	Time
enqueue(x)	Insert item at the back of the queue	O(1)
dequeue()	Remove and return front item	O(1) with deque
peek()	View the front item without removing it	O(1)
is_empty()	Check if queue has no elements	O(1)

2.3 Why Not Use List pop(0)?

If you implement a queue as a list and use pop(0) to dequeue, each removal shifts all remaining elements one step – this is O(n).

Instead, Python provides collections.deque, which is optimized for fast appends and pops from both ends.

2.4 Queue Implementation with deque

Here is how to use deque for a queue:

from collections import deque q = deque() # enqueue q.append(10) q.append(20) q.append(30) print(q) # deque([10, 20, 30]) # dequeue (FIFO) print(q.popleft()) # 10 print(q.popleft()) # 20 print(q.popleft()) # 30 Run Reset

2.5 Custom Queue Class

Here is a simple implementation of a Queue class using deque:

from collections import deque class Queue: def __init__(self): self.items = deque() def enqueue(self, value): self.items.append(value) def dequeue(self): if not self.items: return None return self.items.popleft() def peek(self): return self.items[0] if self.items else None def is_empty(self): return len(self.items) == 0 def __repr__(self): return f"Queue({list(self.items)})" Run Reset

2.6 Real-World Uses of Queues

Queues are commonly used in various applications, such as:

• Task scheduling (CPU processes, OS schedulers)
• Print job queues
• Message queues (RabbitMQ, Kafka)
• Customer service systems (support tickets)
• Breadth-First Search (BFS) in graphs/trees
• Networking – buffering packets

HEAP · PRIORITY QUEUE

3. Heaps (Priority Queues)

A heap is a specialized tree-based data structure that satisfies the heap property. It is commonly used to implement priority queues, where elements are ordered based on priority rather than insertion order.

3.1 What is a Heap?

A heap is a special tree-based data structure that satisfies the heap property and is always a complete binary tree (all levels filled from left to right).

Two main types:

• Min-heap – smallest element is always at the root
• Max-heap – largest element is always at the root

3.2 Min-Heap Example

Here is an example of a min-heap:

Min-heap property: every parent node is ≤ its children. The smallest value is always at the top.

3.3 Heaps in Python – heapq Module

Python does not have a dedicated Heap class, but the heapq module provides a very efficient min-heap implementation built on top of a list.

3.4 Basic Heap Operations with heapq

Here are the main operations using the heapq module:

import heapq h = [] heapq.heappush(h, 10) heapq.heappush(h, 1) heapq.heappush(h, 7) print(h) # underlying list in heap order (not fully sorted) print(heapq.heappop(h)) # 1 (smallest) print(heapq.heappop(h)) # 7 print(heapq.heappop(h)) # 10 Run Reset

3.5 Converting a List into a Heap

You can convert an existing list into a heap in-place using heapq.heapify():

import heapq arr = [10, 3, 5, 1, 7] heapq.heapify(arr) print(arr) # now has heap structure internally Run Reset

3.6 Max-Heap Trick in Python

Python's heapq supports only a min-heap, but we can simulate a max-heap by pushing negative values.

import heapq max_heap = [] heapq.heappush(max_heap, -10) heapq.heappush(max_heap, -1) heapq.heappush(max_heap, -7) print(-heapq.heappop(max_heap)) # 10 (max) print(-heapq.heappop(max_heap)) # 7 print(-heapq.heappop(max_heap)) # 1 Run Reset

3.7 Priority Queue Example

A common use of a heap is to implement a priority queue.

import heapq tasks = [] heapq.heappush(tasks, (1, "Low priority")) # priority 1 heapq.heappush(tasks, (0, "High priority")) # priority 0 heapq.heappush(tasks, (2, "Very low priority")) while tasks: priority, task = heapq.heappop(tasks) print(priority, task) Run Reset

Output:

0 High priority
1 Low priority
2 Very low priority

3.8 Time Complexity of Heap Operations

The time complexities for key heap operations are:

Operation	Description	Time
heappush	Insert element	O(log n)
heappop	Remove smallest element	O(log n)
heapify	Build heap from list	O(n)

3.9 Real-World Uses of Heaps

Heaps are widely used in various applications, such as:

• Dijkstra’s algorithm (shortest path in graphs)
• A* search for pathfinding
• CPU scheduling and job schedulers
• Event simulation (next event has highest priority)
• Live leaderboards and top-K queries
• Streaming median using two heaps

4. Comparison: Stack vs Queue vs Heap

Here is a summary comparison of stacks, queues and heaps:

Feature	Stack	Queue	Heap
Order	LIFO (Last In, First Out)	FIFO (First In, First Out)	Priority (min or max element first)
Python Implementation	list (append, pop)	collections.deque	heapq module
Main Use Cases	Undo, recursion, DFS	Scheduling, BFS, messaging	Priority queues, shortest paths
Insertion	append(): O(1)	append(): O(1)	heappush(): O(log n)
Removal	pop(): O(1)	popleft(): O(1)	heappop(): O(log n)

5. When to Use Stack, Queue, or Heap?

Here are guidelines on when to choose each data structure:

5.1 Use a Stack when...

• You need LIFO behavior
• Implementing undo/redo
• Parsing expressions, function calls, recursion
• Performing Depth-First Search (DFS)

5.2 Use a Queue when...

• You need FIFO behavior
• Scheduling tasks or processing jobs in order
• Implementing Breadth-First Search (BFS)
• Handling messages/events

5.3 Use a Heap when...

• You always need to access the smallest or largest element quickly
• Building a priority queue
• Implementing Dijkstra / A* / other greedy algorithms
• Finding top-K or maintaining dynamic rankings