dsa/data_structures/
queue.rs

1use crate::data_structures::node::Node;
2
3/// A queue data structure with a fixed capacity.
4///
5/// This structure implements a simple queue where elements of type `T` are
6/// enqueued and dequeued according to the First-In-First-Out (FIFO) principle.
7pub struct Queue<T> {
8    /// The front of the queue, represented by an `Option` of a `Box` containing the first `Node`.
9    ///
10    /// This points to the first element in the queue. If the queue is empty, this is `None`.
11    /// The front node is removed when dequeuing an element.
12    front: Option<Box<Node<T>>>,
13    /// A pointer to the rear node in the queue.
14    ///
15    /// This is a raw pointer to the last `Node` in the queue. It is used to quickly append new
16    /// nodes at the end when enqueuing. It is set to `null_mut` if the queue is empty.
17    rear: *mut Node<T>,
18    /// The current size of the queue.
19    ///
20    /// This keeps track of how many elements are in the queue. It is incremented when an element
21    /// is enqueued and decremented when an element is dequeued.
22    size: usize,
23}
24
25impl<T> Queue<T> {
26    /// Creates a new, empty `Queue`.
27    ///
28    /// # Examples
29    ///
30    /// ```
31    /// use dsa::data_structures::queue::Queue;
32    /// let queue: Queue<i32> = Queue::new();
33    /// assert!(queue.is_empty());
34    /// ```
35    pub fn new() -> Self {
36        Queue {
37            front: None,
38            rear: std::ptr::null_mut(),
39            size: 0,
40        }
41    }
42
43    /// Adds a value to the rear of the `Queue`.
44    ///
45    /// # Examples
46    ///
47    /// ```
48    /// use dsa::data_structures::queue::Queue;
49    /// let mut queue = Queue::new();
50    /// queue.enqueue(10);
51    /// queue.enqueue(20);
52    /// assert_eq!(queue.peek(), Some(&10));
53    /// ```
54    pub fn enqueue(&mut self, value: T) {
55        let new_node = Box::new(
56            Node::new(
57                value,
58                None
59            )
60        );
61
62        let new_node_ptr: *mut Node<T> = Box::into_raw(new_node);
63
64        if self.rear.is_null() {
65            self.front = unsafe {
66                Some(Box::from_raw(new_node_ptr))
67            };
68            self.rear = new_node_ptr
69        } else {
70            unsafe {
71                (*self.rear).next = Some(Box::from_raw(new_node_ptr));
72                self.rear = new_node_ptr
73            }
74        }
75
76        self.size += 1;
77    }
78
79    /// Removes and returns the value at the front of the `Queue`.
80    ///
81    /// # Examples
82    ///
83    /// ```
84    /// use dsa::data_structures::queue::Queue;
85    /// let mut queue = Queue::new();
86    /// queue.enqueue(10);
87    /// queue.enqueue(20);
88    /// assert_eq!(queue.dequeue(), Some(10));
89    /// assert_eq!(queue.dequeue(), Some(20));
90    /// assert!(queue.dequeue().is_none());
91    /// ```
92    pub fn dequeue(&mut self) -> Option<T> {
93        if self.front.is_none() {
94            return None;
95        }
96
97        let old_front = self.front.take().unwrap();
98        self.front = old_front.next;
99        if self.front.is_none() {
100            self.rear = std::ptr::null_mut();
101        }
102
103        self.size -= 1;
104
105        Some(old_front.value)
106    }
107
108    /// Returns a reference to the value at the front without removing it.
109    ///
110    /// # Examples
111    ///
112    /// ```
113    /// use dsa::data_structures::queue::Queue;
114    /// let mut queue = Queue::new();
115    /// queue.enqueue(10);
116    /// queue.enqueue(20);
117    /// assert_eq!(queue.peek(), Some(&10));
118    /// ```
119    pub fn peek(&self) -> Option<&T> {
120        self.front.as_ref().map(|node| &node.value)
121    }
122
123    /// Checks if the `Queue` is empty.
124    ///
125    /// # Examples
126    ///
127    /// ```
128    /// use dsa::data_structures::queue::Queue;
129    /// let mut queue = Queue::new();
130    /// assert!(queue.is_empty());
131    /// queue.enqueue(10);
132    /// assert!(!queue.is_empty());
133    /// ```
134    pub fn is_empty(&self) -> bool {
135        self.size == 0
136    }
137
138    /// Returns the current size of the `Queue`.
139    ///
140    /// # Examples
141    ///
142    /// ```
143    /// use dsa::data_structures::queue::Queue;
144    /// let mut queue: Queue<i32> = Queue::new();
145    /// queue.enqueue(10);
146    /// queue.enqueue(20);
147    /// queue.dequeue();
148    /// assert_eq!(queue.size(), 1);
149    /// ```
150    pub fn size(&self) -> usize {
151        self.size
152    }
153}
dsa/data_structures/queue.rs

dsa/data_structures/
queue.rs
