Queue Data Structure in Rust

About This Module

This module explores queue data structures, which follow the First-In-First-Out (FIFO) principle. Students will learn about queue operations, various implementation strategies, and the trade-offs between different approaches. The module covers both custom implementations and Rust's standard library VecDeque, with a focus on performance considerations and practical applications in data processing and algorithms.

Prework

Before this lecture, please read:

• The Rust Book Chapter 8.1: "Storing Lists of Values with Vectors" - https://doc.rust-lang.org/book/ch08-01-vectors.html
• Rust std::collections::VecDeque documentation - https://doc.rust-lang.org/std/collections/struct.VecDeque.html
• The Rust Book Chapter 4: "Understanding Ownership" - https://doc.rust-lang.org/book/ch04-00-understanding-ownership.html (review for clone operations)

Pre-lecture Reflections

1. What are some real-world scenarios where FIFO ordering is essential?
2. Why might using a Vec with remove(0) be problematic for queue operations?
3. How does memory layout affect performance in different queue implementations?

Learning Objectives

By the end of this lecture, you should be able to:

• Understand the FIFO principle and queue operations
• Implement queues using different underlying data structures
• Analyze performance trade-offs between queue implementations
• Use Rust's VecDeque effectively for both stack and queue operations
• Choose appropriate data structures based on access patterns and performance requirements

Queues

Queue:

• FIFO: first in first out
• add items at the end
• get items from the front

Question: Why is it problematic to use Vec as a Queue?

Generic Queue operations

Warning: This is not Rust syntax.

• enqueue(object): Insert object at the end of the queue. Input: object, Output: none
• dequeue(): Remove an object from the front of the queue and return it. Input: none, Output: object
• size(): Number of objects in queue
• isEmpty(): Return boolean indicated if queue is empty
• front(): Return a reference to front object in the queue without removing it

Queue Complexity using Singly Linked List?

• Remember in a singly linked list the most recent element is first pointer while the oldest is at the tail end of the list
• Adding a queue element O(1)
• Removing a queue element requires list traversal so O(n)

You can do better with doubly linked lists and tail pointer

Assume first points to most recently added element and last to oldest element

• Adding a queue element still O(1)
• Removing the older element O(1)
• But the memory fragmentation issues persist

The VecDeque container in Rust

std::collections::VecDeque<T>

• generalization of queue and stack
• accessing front: methods push_front(x) and pop_front()
• accessing back: methods push_back(x) and pop_back()
• pop_front and pop_back return Option<T>

Using VecDeque as a Stack

Use push_back and pop_back

#![allow(unused)]
fn main() {
use std::collections::VecDeque;

// using as a stack: push_back & pop_back
let mut stack = VecDeque::new();

stack.push_back(1);
stack.push_back(2);
stack.push_back(3);

println!("{:?}",stack.pop_back());
println!("{:?}",stack.pop_back());

stack.push_back(4);
stack.push_back(5);

println!("{:?}",stack.pop_back());
}

Using VecDeque as a Queue

#![allow(unused)]
fn main() {
use std::collections::VecDeque;

// using as a queue: push_back & pop_front
let mut queue = VecDeque::new();

queue.push_back(1);
queue.push_back(2);
queue.push_back(3);

println!("{:?}",queue.pop_front());
println!("{:?}",queue.pop_front());

queue.push_back(4);
queue.push_back(5);

println!("{:?}",queue.pop_front());
}

VecDeque operation semantics

• push_back + pop_back (Stack Behavior)
• push_front + pop_front (Stack Behavior)
• push_back + pop_front (Queue Behavior)
• push_front + pop_back (Queue Behavior)

Implementation of VecDeque

• use an array allocated on the heap (think of it as a circular buffer)
• keep index of the front and end
• wrap around

Out of space?

• double the size
• good complexity due to amortization

See Wikipedia: Circular Buffer for more details.

Priority Queues (for a later lecture)

In-Class Poll

True or False:

1. In a queue data structure, the first element added is the first element removed (FIFO principle).

   • True ✓ (This is the definition of FIFO - First In First Out)

2. When using a singly linked list to implement a queue, both enqueue and dequeue operations can be performed in O(1) time complexity.

   • False ✗ (enqueue is O(1) and dequeue is O(n) for singly linked list)

3. Rust's VecDeque can function as both a stack and a queue depending on which methods you use.

   • True ✓ (VecDeque can be used as both stack and queue depending on the methods used)

4. To use a VecDeque as a queue, you should use push_back() to add elements and pop_back() to remove elements.

   • False ✗ (To use as a queue, you should use push_back() to add elements and pop_front() to remove elements)

5. VecDeque is implemented using a doubly linked list that grows by 1 as needed.

   • False ✗ (VecDeque is implemented using a circular buffer)

Recap