Stacks & Queues

14.2. Stacks & Queues#

Stacks and queues are linear abstract data types. Both store ordered collections, but they remove items in different orders.

Outline

Stacks
  o Last-in, first-out behavior
  o Python list implementation
Queues
  o First-in, first-out behavior
  o collections.deque implementation
Stack or Queue?
Summary

14.2.1. Stacks#

A stack is a last-in, first-out structure. The newest item is the first item removed.

Common stack operations:

  • push(item): add an item to the top

  • pop(): remove and return the top item

  • peek(): look at the top item without removing it

  • is_empty(): check whether the stack has no items

Stacks are useful for undo history, browser back buttons, expression evaluation, recursion, and depth-first traversal.

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

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

    def pop(self):
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self._items.pop()

    def peek(self):
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self._items[-1]

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


history = Stack()
history.push("open file")
history.push("edit line 10")
history.push("rename variable")

print(history.pop())
print(history.pop())

rename variable
edit line 10

### Exercise: Reverse Words with a Stack
# Write a function named reverse_words(sentence) that uses a Stack
# to reverse the order of words in a sentence.
#
# Example: reverse_words("data structures matter") should return
# "matter structures data".
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
def reverse_words(sentence):
    stack = Stack()
    for word in sentence.split():
        stack.push(word)

    reversed_words = []
    while not stack.is_empty():
        reversed_words.append(stack.pop())

    return " ".join(reversed_words)


print(reverse_words("data structures matter"))

matter structures data

14.2.2. Queues#

A queue is a first-in, first-out structure. The oldest item is the first item removed.

Common queue operations:

  • enqueue(item): add an item to the back

  • dequeue(): remove and return the front item

  • is_empty(): check whether the queue has no items

In Python, collections.deque is usually the right implementation for a queue.

from collections import deque


class Queue:
    def __init__(self):
        self._items = deque()

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

    def dequeue(self):
        if self.is_empty():
            raise IndexError("dequeue from empty queue")
        return self._items.popleft()

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


line = Queue()
line.enqueue("alice")
line.enqueue("bob")
line.enqueue("charlie")

print(line.dequeue())
print(line.dequeue())

alice
bob

### Exercise: Serve a Customer Line
# Create a Queue. Add apple, banana, and cherry as customer names.
# Serve two customers by calling dequeue twice and printing the result.
### Your code starts here.



### Your code ends here.

Hide code cell source

 
### Solution
customers = Queue()
customers.enqueue("apple")
customers.enqueue("banana")
customers.enqueue("cherry")

print(customers.dequeue())
print(customers.dequeue())

apple
banana

14.2.3. Stack or Queue?#

Problem

Better structure

Reason

Undo edits

Stack

Undo the newest action first

Print jobs

Queue

Print the oldest waiting job first

Browser back button

Stack

Return to the most recent page

Help desk tickets

Queue

Serve earlier requests first

Depth-first search

Stack

Explore one path deeply before backing up

Breadth-first search

Queue

Explore nearby nodes first

 
### Exercise: Pick the Structure
# For each workflow, write "stack" or "queue" in the dictionary value.
# 1. Undo history
# 2. Waiting room check-in
# 3. Browser back button
### Your code starts here.

choices = {
    "undo history": "",
    "waiting room": "",
    "browser back": "",
}

print(choices)

### Your code ends here.

{'undo history': '', 'waiting room': '', 'browser back': ''}

Hide code cell source

 
### Solution
choices = {
    "undo history": "stack",
    "waiting room": "queue",
    "browser back": "stack",
}

print(choices)

{'undo history': 'stack', 'waiting room': 'queue', 'browser back': 'stack'}

14.2.4. Summary#

Stacks and queues are simple but powerful. Use a stack when the newest item should be handled first. Use a queue when the oldest waiting item should be handled first.

Contents