Lesson 5
Exploring Stacks and Queues in Ruby
Introduction: Stacks and Queues

Welcome to an exploration of two foundational data structures: Stacks and Queues! These structures are essential for organizing data in a structured, efficient manner. Imagine a stack like a pile of plates, where the last plate added is the first to be removed (LIFO). In contrast, a queue is like a line at the store, where the first person in line is served first (FIFO). Let’s dive in and see how these structures work in Ruby!

Stacks: Last In, First Out (LIFO)

A stack follows the LIFO (Last In, First Out) principle. Think of a stack as a pile of plates — the last plate added is the first to be removed. In Ruby, arrays make a convenient base for stacks, using push to add items and pop to remove them.

Here’s a simple example using a stack of plates:

Ruby
1class StackOfPlates 2 def initialize 3 @stack = [] 4 end 5 6 # Add a plate to the top of the stack 7 def add_plate(plate) 8 @stack.push(plate) 9 end 10 11 # Remove the top plate from the stack 12 def remove_plate 13 return "No plates left to remove!" if @stack.empty? 14 @stack.pop 15 end 16end 17 18plates = StackOfPlates.new 19plates.add_plate('Plate 1') 20plates.add_plate('Plate 2') 21puts "Removed: #{plates.remove_plate}" # Output: Removed: Plate 2

In this example, the last plate added (Plate 2) is the first one removed, demonstrating the LIFO behavior of a stack.

Queues: First In, First Out (FIFO)

A queue follows the FIFO (First In, First Out) principle, much like waiting in line. Ruby arrays can also represent queues, where push adds an item to the end, and shift removes the item from the front.

Here’s an example of a queue of people:

Ruby
1class QueueOfPeople 2 def initialize 3 @queue = [] 4 end 5 6 # Add a person to the end of the queue 7 def enqueue_person(person) 8 @queue.push(person) 9 end 10 11 # Remove the first person from the queue 12 def dequeue_person 13 return "No people left to dequeue!" if @queue.empty? 14 @queue.shift 15 end 16end 17 18people = QueueOfPeople.new 19people.enqueue_person('Person 1') 20people.enqueue_person('Person 2') 21puts "Removed: #{people.dequeue_person}" # Output: Removed: Person 1

Here, Person 1, the first to enter the queue, is also the first to leave, showcasing the FIFO behavior of a queue.

Stacks and Queues: When and Where to Use?
  • Stacks are ideal for managing ordered tasks, such as:
    • Undo/Redo Systems: In text editors, the last action (e.g., inserting text) is undone first.
    • Call Stack in Recursion: Tracks function calls, with the most recent call resolved first.
    • Expression Evaluation: Used to evaluate postfix or infix expressions.
    • Web Browser History: Navigates back to the most recent page visited.
  • Queues are great when the order of arrival is important, like:
    • Task Scheduling: Ensures tasks are processed in the order they arrive (e.g., print jobs).
    • Breadth-First Search (BFS): Utilizes a queue to explore nodes level by level.
    • Event Queues: Processes events in systems like GUI applications.
    • Customer Service Lines: Serves customers in the order they arrive.
Mastering Stack and Queue Operations With a Class

Let’s combine both structures in a realistic scenario: a text editor with an Undo feature (stack) and a Print Queue (queue).

Ruby
1class TextEditor 2 def initialize 3 @stack = [] # Stack for storing undo actions 4 @queue = [] # Queue for print jobs 5 end 6 7 # Make a change and add it to the stack 8 def make_change(action) 9 @stack.push(action) 10 end 11 12 # Undo the most recent change 13 def undo_change 14 return "No changes to undo!" if @stack.empty? 15 @stack.pop 16 end 17 18 # Add a document to the print queue 19 def add_to_print(doc) 20 @queue.push(doc) 21 end 22 23 # Print the first document in the queue 24 def print_doc 25 return "No documents in print queue!" if @queue.empty? 26 @queue.shift 27 end 28end 29 30editor = TextEditor.new 31editor.make_change("Changed font size") 32editor.make_change("Inserted image") 33puts "Undo: #{editor.undo_change}" # Output: Undo: Inserted image 34 35editor.add_to_print("Proposal.docx") 36editor.add_to_print("Report.xlsx") 37puts "Print: #{editor.print_doc}" # Output: Print: Proposal.docx

In this example:

  • The stack (@stack) holds changes to be undone, with the last change made being the first to undo.
  • The queue (@queue) manages print jobs in the order they’re added, with the first document queued being the first to print.
Lesson Summary

Great job! You’ve covered the essentials of stacks and queues, two critical data structures in programming. Stacks follow the LIFO principle, perfect for tasks like undo actions, while queues follow FIFO, ideal for tasks like print job management. Keep practicing to reinforce these concepts — happy coding!

Enjoy this lesson? Now it's time to practice with Cosmo!
Practice is how you turn knowledge into actual skills.