Stacks and Queues

Introduction

In this lesson, we'll explore stacks and queues, their properties and usage in Rust.

Key Points

• Stacks: A data structure that stores elements in a last-in-first-out (LIFO) order.
• Queues: A data structure that stores elements in a first-in-first-out (FIFO) order.

Stacks

A stack is a collection of elements that follows the Last In, First Out (LIFO) principle. The last element added is the first one to be removed. This is the opposite of a queue, where the first element added is the first one to be removed.

#[derive(Debug)]
struct Stack<T> {
    items: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self {
        Stack { items: Vec::new() }
    }

    fn push(&mut self, item: T) {
        self.items.push(item);
    }

    fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

    fn peek(&self) -> Option<&T> {
        self.items.last()
    }

    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }
}

fn main() {
    let mut stack = Stack::new();
    stack.push(1);
    stack.push(2);
    stack.push(3);

    println!("Stack: {:?}", stack);
    println!("Top item: {:?}", stack.peek());

    while let Some(item) = stack.pop() {
        println!("Popped: {}", item);
    }
}

Code Explanation

• push adds an element to the top of the stack.
• pop removes the top element from the stack.
• peek returns a reference to the top element of the stack.
• is_empty returns true if the stack is empty, and false otherwise.

Queues

A queue is a collection of elements that follows the First In, First Out (FIFO) principle. The first element added is the first one to be removed. This is the opposite of a stack, where the last element added is the first one to be removed.

use std::collections::VecDeque;

#[derive(Debug)]
struct Queue<T> {
    items: VecDeque<T>,
}

impl<T> Queue<T> {
    fn new() -> Self {
        Queue {
            items: VecDeque::new(),
        }
    }

    fn enqueue(&mut self, item: T) {
        self.items.push_back(item);
    }

    fn dequeue(&mut self) -> Option<T> {
        self.items.pop_front()
    }

    fn peek(&self) -> Option<&T> {
        self.items.front()
    }

    fn is_empty(&self) -> bool {
        self.items.is_empty()
    }
}

fn main() {
    let mut queue = Queue::new();
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);

    println!("Queue: {:?}", queue);
    println!("Front item: {:?}", queue.peek());

    while let Some(item) = queue.dequeue() {
        println!("Dequeued: {}", item);
    }
}

Code Explanation

• enqueue adds an element to the end of the queue.
• dequeue removes the first element and returns it.
• peek returns the first element without removing it.
• is_empty checks if the queue is empty.

Real World Examples

Stacks

When you browse the web, your browser keeps track of the pages you've visited in a stack-like structure. This allows you to go back to the previous page by popping the most recent page off the stack.

How It Works:

• Push: When you navigate to a new page, the URL is pushed onto the stack.
• Pop: When you hit the "Back" button, the browser pops the most recent URL from the stack and navigates to it.
• Peek: You can see the current URL on top of the stack without removing it.

Queues

A print spooler manages print jobs sent to a printer. It uses a queue to ensure that print jobs are processed in the order they are received.

How It Works:

• Enqueue: When a new print job is submitted, it is added to the end of the queue.
• Dequeue: The print spooler processes the print jobs from the front of the queue, printing them one by one.
• Peek: You can check the next job to be printed without removing it from the queue.

Conclusion

Stacks and queues are essential for managing data in various applications. By implementing these structures in Rust, you can handle data efficiently and understand fundamental programming concepts better.