Deque Implementation in Rust

1. Introduction

A deque, pronounced "deck" and short for "double-ended queue," is an ordered collection of items similar to the queue. It has two ends, a front and a rear, and the items remain positioned in the collection. What makes a deque different is the unrestrictive nature of adding and removing items. New items can be added at either the front or the rear. Likewise, existing items can be removed from either end.

2. Implementation Steps

1. Define the Deque struct with a Vec to store the deque elements.

2. Implement a new function to initialize the deque.

3. Implement push_front to add an element to the front of the deque.

4. Implement push_back to add an element to the back of the deque.

5. Implement pop_front to remove an element from the front.

6. Implement pop_back to remove an element from the back.

7. Implement an is_empty function to check if the deque is empty.

8. Implement a peek_front and peek_back function to view the front and back element without removing it.

3. Implementation in Rust Programming

pub struct Deque<T> {
    elements: Vec<T>,
}
impl<T> Deque<T> {
    // Initialize an empty deque
    pub fn new() -> Self {
        Deque {
            elements: Vec::new(),
        }
    }
    // Add an element to the front
    pub fn push_front(&mut self, value: T) {
        self.elements.insert(0, value);
    }
    // Add an element to the back
    pub fn push_back(&mut self, value: T) {
        self.elements.push(value);
    }
    // Remove and return an element from the front
    pub fn pop_front(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            Some(self.elements.remove(0))
        }
    }
    // Remove and return an element from the back
    pub fn pop_back(&mut self) -> Option<T> {
        self.elements.pop()
    }
    // Peek at the front element without removing it
    pub fn peek_front(&self) -> Option<&T> {
        self.elements.first()
    }
    // Peek at the back element without removing it
    pub fn peek_back(&self) -> Option<&T> {
        self.elements.last()
    }
    // Check if the deque is empty
    pub fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }
}
fn main() {
    let mut deque = Deque::new();
    deque.push_front("Front 1");
    deque.push_back("Back 1");
    deque.push_front("Front 2");
    deque.push_back("Back 2");
    println!("Peek Front: {:?}", deque.peek_front());
    println!("Peek Back: {:?}", deque.peek_back());
    println!("Pop Front: {:?}", deque.pop_front());
    println!("Pop Back: {:?}", deque.pop_back());
    println!("After operations, Peek Front: {:?}", deque.peek_front());
}

Output:

Peek Front: Some("Front 2")
Peek Back: Some("Back 2")
Pop Front: Some("Front 2")
Pop Back: Some("Back 2")
After operations, Peek Front: Some("Front 1")

Explanation:

1. We create a Deque struct that internally uses a Vec for storage. This allows for dynamic resizing.

2. The new function initializes an empty deque.

3. push_front inserts an element at the front of the deque.

4. push_back appends an element to the back of the deque.

5. pop_front removes and returns the front element.

6. pop_back removes and returns the back element.

7. peek_front and peek_back allow for viewing the front and back elements, respectively, without removing them.

8. The is_empty function checks if there are any elements in the deque.

9. The main function demonstrates the usage of the deque by performing various operations and printing the results.