Stacks and Queues: Mastering Advanced Data Structures in Python

Lesson 5

Introduction: Stacks and Queues

Welcome to an exciting exploration of two fundamental data structures: Stacks and Queues! Remember, data structures store and organize data in a manner that is structured and efficient. Stacks and Queues are akin to stacking plates and standing in a line, respectively. Intriguing, isn't it? Let's dive in!

Stacks: Last In, First Out (LIFO)

A Stack adheres to the "Last In, First Out" or LIFO principle. It's like a pile of plates where the last plate added is the first one to be removed. Python uses the list to create a stack, with append() used for push, and pop() used for pop.

Let's explore this using a pile of plates.

Python
1class StackOfPlates:
2  def __init__(self):
3    self.stack = []
4
5  # Inserts a plate at the top of the stack
6  def add_plate(self, plate):
7    self.stack.append(plate)
8
9  # Removes the top plate from the stack
10  def remove_plate(self):
11    if len(self.stack) == 0:
12      return "No plates left to remove!"
13    return self.stack.pop()
14
15# Create a stack of plates
16plates = StackOfPlates()
17plates.add_plate('Plate') # Pushing a plate
18plates.add_plate('Another Plate') # Pushing another plate
19# Let's remove a plate; it should be the last one we added.
20print('Removed:', plates.remove_plate())  # Outputs: Removed: Another Plate

The last plate added was removed first, demonstrating the LIFO property of a stack.

Queues: First In, First Out (FIFO)

A Queue represents the "First In, First Out" or FIFO principle, much like waiting in line at the grocery store. Python's deque class creates queues according to the FIFO principle, providing append() for enqueue and popleft() for dequeue.

Let's examine this through a queue of people.

Python
1from collections import deque
2
3class QueueOfPeople:
4  def __init__(self):
5    self.queue = deque([])
6
7  # Add a person to the end of the queue
8  def enqueue_person(self, person):
9    self.queue.append(person)
10
11  # Remove the first person from the queue (who has been waiting the longest)
12  def dequeue_person(self):
13    if len(self.queue) == 0:
14      return "No people left to dequeue!"
15    return self.queue.popleft()
16
17# Create a queue of people
18people = QueueOfPeople()
19people.enqueue_person('Person 1') # Person 1 enters the queue
20people.enqueue_person('Person 2') # Person 2 arrives after Person 1
21# Who's next in line? It must be Person 1!
22print('Removed:', people.dequeue_person())  # Outputs: Removed: Person 1

Here, Person 1, the first to join the queue, left before Person 2, demonstrating the FIFO property of a queue.

Stacks and Queues: When and Where to Use?

Stacks handle ordered data efficiently, much like your web browser's history. Queues, on the other hand, are optimal when the order of arrival is essential, such as in a store queue.

Mastering Stack and Queue Operations With a Class

Let's depict the two structures in a text editor that features an Undo mechanism (a Stack) and a Print Queue.

Python
1from collections import deque
2
3class TextEditor:
4  def __init__(self):
5    self.stack = []
6    self.queue = deque([])
7
8  # Make a change (e.g., edit text, insert image, change font)
9  def make_change(self, action):
10    self.stack.append(action) # Add to the stack of actions
11
12  # Undo the most recent change
13  def undo_change(self):
14    if len(self.stack) == 0:
15      return "No changes to undo!"
16    return self.stack.pop() # Remove the last action from the stack
17
18  # Add a document to the queue for printing
19  def add_to_print(self, doc):
20    self.queue.append(doc)
21
22  # Print the document that has been waiting the longest
23  def print_doc(self):
24    if len(self.queue) == 0:
25      return "No documents in print queue!"
26    return self.queue.popleft() # Remove the first document from the queue
27
28# Use our text editor!
29editor = TextEditor()
30editor.make_change("Changed font size") # Make a change
31editor.make_change("Inserted image") # Make another change
32# Let's undo a change. It should be the last change we made.
33print('Undo:', editor.undo_change())  # Undo: Inserted image
34
35editor.add_to_print("Proposal.docx") # Queue a document for printing
36editor.add_to_print("Report.xlsx") # Queue another document
37# Let's print a document. It should be the document that has been waiting the longest.
38print('Print:', editor.print_doc())  # Print: Proposal.docx

This code reintroduces the concepts of a Stack (Undo feature) and Queue (Print queue) in the context of a real-life scenario.

Lesson Summary

Great work! You have examined the mechanics of Stacks and Queues, both integral data structures. Remember to practice what you've learned. Happy coding!

Enjoy this lesson? Now it's time to practice with Cosmo!

Practice is how you turn knowledge into actual skills.