algo_rs/data_structure/queue/
fixed_queue.rs

1use crate::data_structure::queue::Queue;
2
3pub struct FixedQueue<T: Default> {
4    inner: Vec<T>,
5    head: usize,
6    tail: usize,
7    size: usize,
8}
9
10impl<T: Default> FixedQueue<T> {
11    pub fn new(size: usize) -> Self {
12        Self {
13            head: 0,
14            tail: 0,
15            size: 0,
16            inner: Vec::<T>::with_capacity(size),
17        }
18    }
19}
20
21impl<T: Default> Queue<T> for FixedQueue<T> {
22    fn push_back(&mut self, item: T) {
23        if self.size == self.inner.capacity() {
24            panic!("queue is full")
25        }
26
27        if self.inner.len() < self.inner.capacity() {
28            self.inner.push(item);
29        } else {
30            self.inner[self.head] = item;
31        }
32
33        self.size += 1;
34        self.head += 1;
35
36        if self.head == self.inner.capacity() {
37            self.head = 0;
38        }
39    }
40
41    fn pop_front(&mut self) -> Option<T> {
42        if self.size == 0 {
43            return None;
44        }
45
46        let result = std::mem::take(&mut self.inner[self.tail]);
47        self.tail += 1;
48
49        if self.tail == self.inner.capacity() {
50            self.tail = 0;
51        }
52
53        self.size -= 1;
54
55        Some(result)
56    }
57
58    fn front(&self) -> Option<&T> {
59        if self.size == 0 {
60            return None;
61        }
62
63        Some(&self.inner[self.tail])
64    }
65
66    fn is_empty(&self) -> bool {
67        self.size == 0
68    }
69}
70
71#[cfg(test)]
72mod tests {
73    use crate::data_structure::queue::fixed_queue::FixedQueue;
74    use crate::data_structure::queue::Queue;
75
76    extern crate test;
77    use std::collections::VecDeque;
78    use test::Bencher;
79
80    #[test]
81    fn test_push_pop() {
82        let mut queue = FixedQueue::<i32>::new(10);
83        for i in 0..33 {
84            queue.push_back(i);
85            queue.push_back(i + 1);
86            queue.push_back(i + 2);
87            assert_eq!(Some(i), queue.pop_front());
88            assert_eq!(Some(i + 1), queue.pop_front());
89            assert_eq!(Some(i + 2), queue.pop_front());
90            assert_eq!(None, queue.pop_front());
91        }
92    }
93
94    #[test]
95    fn test_is_empty() {
96        let mut queue = FixedQueue::<i32>::new(10);
97        assert_eq!(true, queue.is_empty());
98        queue.push_back(1);
99        assert_eq!(false, queue.is_empty());
100        queue.pop_front();
101        assert_eq!(true, queue.is_empty());
102    }
103
104    #[test]
105    fn test_front() {
106        let mut queue = FixedQueue::<i32>::new(10);
107        assert_eq!(None, queue.front());
108        queue.push_back(1);
109        assert_eq!(1, *queue.front().unwrap());
110        queue.push_back(2);
111        assert_eq!(1, *queue.front().unwrap());
112        queue.pop_front();
113        assert_eq!(2, *queue.front().unwrap());
114        queue.pop_front();
115        assert_eq!(None, queue.front());
116    }
117
118    #[test]
119    #[should_panic(expected = "queue is full")]
120    fn test_panic_when_full() {
121        let mut queue = FixedQueue::new(0);
122        queue.push_back(1);
123    }
124
125    #[bench]
126    fn bench_push_pop(b: &mut Bencher) {
127        b.iter(|| {
128            let mut queue = FixedQueue::<i32>::new(20);
129            for i in 0..10000 {
130                for _ in 0..10 {
131                    queue.push_back(i);
132                }
133
134                for _ in 0..10 {
135                    queue.pop_front();
136                }
137            }
138        });
139    }
140
141    #[bench]
142    fn bench_rust_std_veq_deque_push_pop(b: &mut Bencher) {
143        b.iter(|| {
144            let mut queue = VecDeque::<i32>::with_capacity(20);
145            for i in 0..10000 {
146                for _ in 0..10 {
147                    queue.push_back(i);
148                }
149
150                for _ in 0..10 {
151                    queue.pop_front();
152                }
153            }
154        });
155    }
156}
algo_rs/data_structure/queue/fixed_queue.rs

algo_rs/data_structure/queue/
fixed_queue.rs
