Stacks and Queues in C#

Lesson 5

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 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. C# uses the Stack<T> class to create a stack, with Push used for insert (push), and Pop used for remove (pop, return the element that has been removed).

Let's explore this using a pile of plates.

C#
1using System;
2using System.Collections.Generic;
3
4class StackOfPlates {
5    private Stack<string> stack;
6
7    public StackOfPlates() {
8        stack = new Stack<string>();
9    }
10
11    // Insert a plate at the top of the stack
12    public void AddPlate(string plate) {
13        stack.Push(plate);
14    }
15
16    // Remove the top plate from the stack
17    public string RemovePlate() {
18        if (stack.Count == 0) {
19            return "No plates left to remove!";
20        }
21        return stack.Pop();
22    }
23}
24
25// Create a stack of plates
26class Program {
27    static void Main() {
28        StackOfPlates plates = new StackOfPlates();
29        plates.AddPlate("Plate");  // Pushing a plate
30        plates.AddPlate("Another Plate");  // Pushing another plate
31        // Let's remove a plate; it should be the last one we added.
32        Console.WriteLine("Removed: " + plates.RemovePlate());  // Outputs: Removed: Another Plate
33    }
34}

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. In C#, we can use the Queue<T> class to achieve this behavior, using Enqueue for enqueue (insert at the end) and Dequeue for dequeue (remove from the front, return the element that has been removed).

Let's examine this through a queue of people.

C#
1using System;
2using System.Collections.Generic;
3
4class QueueOfPeople {
5    private Queue<string> queue;
6
7    public QueueOfPeople() {
8        queue = new Queue<string>();
9    }
10
11    // Add a person to the end of the queue
12    public void EnqueuePerson(string person) {
13        queue.Enqueue(person);
14    }
15
16    // Remove the first person from the queue (who has been waiting the longest)
17    public string DequeuePerson() {
18        if (queue.Count == 0) {
19            return "No people left to dequeue!";
20        }
21        return queue.Dequeue();
22    }
23}
24
25// Create a queue of people
26class Program {
27    static void Main() {
28        QueueOfPeople people = new QueueOfPeople();
29        people.EnqueuePerson("Person 1");  // Person 1 enters the queue
30        people.EnqueuePerson("Person 2");  // Person 2 arrives after Person 1
31        // Who's next in line? It must be Person 1!
32        Console.WriteLine("Removed: " + people.DequeuePerson());  // Outputs: Removed: Person 1
33    }
34}

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

Mastering Stack and Queue Operations with a Class

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.

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

C#
1using System;
2using System.Collections.Generic;
3
4class TextEditor {
5    private Stack<string> stack;
6    private Queue<string> queue;
7
8    public TextEditor() {
9        stack = new Stack<string>();
10        queue = new Queue<string>();
11    }
12
13    // Make a change (e.g., edit text, insert image, change font)
14    public void MakeChange(string action) {
15        stack.Push(action);  // Add to the stack of actions
16    }
17
18    // Undo the most recent change
19    public string UndoChange() {
20        if (stack.Count == 0) {
21            return "No changes to undo!";
22        }
23        return stack.Pop();  // Remove the last action from the stack
24    }
25
26    // Add a document to the queue for printing
27    public void AddToPrint(string doc) {
28        queue.Enqueue(doc);
29    }
30
31    // Print the document that has been waiting the longest
32    public string PrintDoc() {
33        if (queue.Count == 0) {
34            return "No documents in print queue!";
35        }
36        return queue.Dequeue();  // Remove the first document from the queue
37    }
38}
39
40// Use our text editor!
41class Program {
42    static void Main() {
43        TextEditor editor = new TextEditor();
44        editor.MakeChange("Changed font size");  // Make a change
45        editor.MakeChange("Inserted image");  // Make another change
46        // Let's undo a change. It should be the last change we made.
47        Console.WriteLine("Undo: " + editor.UndoChange());  // Undo: Inserted image
48
49        editor.AddToPrint("Proposal.docx");  // Queue a document for printing
50        editor.AddToPrint("Report.xlsx");  // Queue another document
51        // Let's print a document. It should be the document that has been waiting the longest.
52        Console.WriteLine("Print: " + editor.PrintDoc());  // Print: Proposal.docx
53    }
54}

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.