Python

Python Stack vs Queue vs Heap

Python Stack vs Queue vs Heap

This tutorial covers Python Stack vs Queue vs Heap.

The terms stacks, queues, and heaps refer to data structures.

Python does not have stacks or queues or heaps. Nevertheless, they are easily implemented with lists.

All three structures can be found in many programming languages.

Stack

Stacks refer to data structures that store items similarly to a pile of books.

The operation behind a stack follows the LIFO principle (last in, first out).

Meaning, just like a pile of books, we put the last one on top (which is then the first one to be taken).

python stack data structure

The mechanics of Python stacks work with the list methods, append() and pop().

Let’s create an empty stack, which will store books. We add (place) the first book.

Adding items (append method)

stack = []

stack.append("Book 1")

print(stack)

# Output: ['Book 1']

Let’s add two more books. They go last in.

stack.append("Book 7")
stack.append("Book 11")

print(stack)

# Output: ['Book 1', 'Book 7', 'Book 11']

Removing items (pop method)

stack = ['Book 1', 'Book 7', 'Book 11']

stack.pop()

print(stack)

# Output: ['Book 1', 'Book 7']

Let’s remove two more books. They go first out.

stack.pop()
stack.pop()

print(stack)

# Output: []

Queue

Queues refer to data structures that store items similarly to a queue of people in a supermarket.

The operation behind a queue follows the FIFO principle (first in, first out).

Meaning, just like a queue of people, we put the first one in front (which is then the first one to go).

python queue data structure

The mechanics of Python queues work with the list methods, append() and pop(0).

Let’s create an empty queue, which will store people. We add the first person.

Adding items (append method)

queue = []

queue.append("Person 1")

print(queue)

# Output: ['Person 1']

Let’s add two more people. They go first in.

queue.append("Person 2")
queue.append("Person 3")

print(queue)

# Output: ['Person 1', 'Person 2', 'Person 3']

Removing items (pop method)

queue = ['Person 1', 'Person 2', 'Person 3']

queue.pop(0)

print(queue)

# Output: ['Person 2', 'Person 3']

Let’s remove two more people. They go first out.

queue.pop(0)
queue.pop(0)

print(queue)

# Output: []

Heap

Heaps refer to data structures that store items in binary trees

In Python, heaps can be implemented with the module Heapq.

There are two types of heaps, min heap and max heap.

Min heaps have each node smaller or equal to its children nodes.

Max heaps have each node larger or equal to its children nodes.

python heap data structure

The mechanics of Python heaps work with lists.

The module has four main operations:

  1. heapify – coverts a list to a heap
  2. heappush – adds an item to a heap
  3. heappop – removes an item from a heap
  4. heapreplace – replaces an item from a heap

Let’s create a heap, with several random data points.

import heapq

heap = [3, 11, 5, 2, 7]

print(heap)

# Output: [3, 11, 5, 2, 7]

Adding items (heappush method)

heapq.heappush(heap, 3)

print(heap)

# Output: [3, 11, 3, 2, 7, 5]

Removing items (heappop method)

heapq.heappop(heap)

print(heap)

# Output: [3, 11, 5, 2, 7]

Converting list to a heap (heapify method)

heapq.heapify(heap)

print(heap)

# Output: [2, 3, 5, 11, 7]

Previous: Python Map, Filter, Reduce

Related Posts