algo_rs/data_structure/queue/
two_stacks_queue.rs

1use crate::data_structure::queue::Queue;
2
3pub struct TwoStacksQueue<T> {
4    s1: Vec<T>,
5    s2: Vec<T>,
6}
7
8impl<T> TwoStacksQueue<T> {
9    pub fn new() -> Self {
10        Self {
11            s1: Vec::<T>::new(),
12            s2: Vec::<T>::new(),
13        }
14    }
15
16    pub fn with_capacity(size: usize) -> Self {
17        Self {
18            s1: Vec::<T>::with_capacity(size),
19            s2: Vec::<T>::with_capacity(size),
20        }
21    }
22
23    fn rebalance(&mut self) {
24        while self.s1.len() > 0 {
25            self.s2.push(self.s1.pop().unwrap());
26        }
27    }
28}
29
30impl<T> Queue<T> for TwoStacksQueue<T> {
31    fn push_back(&mut self, item: T) {
32        self.s1.push(item)
33    }
34
35    fn pop_front(&mut self) -> Option<T> {
36        if self.s2.is_empty() {
37            self.rebalance();
38        }
39
40        self.s2.pop()
41    }
42
43    fn front(&self) -> Option<&T> {
44        if !self.s2.is_empty() {
45            return self.s2.last();
46        }
47
48        self.s1.first()
49    }
50
51    fn is_empty(&self) -> bool {
52        self.s1.is_empty() && self.s2.is_empty()
53    }
54}
55
56#[cfg(test)]
57mod tests {
58    use crate::data_structure::queue::two_stacks_queue::TwoStacksQueue;
59    use crate::data_structure::queue::Queue;
60    extern crate test;
61    use test::Bencher;
62
63    #[test]
64    fn test_growable_queue_push_pop() {
65        let mut queue = TwoStacksQueue::<i32>::new();
66        for i in 0..33 {
67            queue.push_back(i);
68            queue.push_back(i + 1);
69            queue.push_back(i + 2);
70            assert_eq!(Some(i), queue.pop_front());
71            assert_eq!(Some(i + 1), queue.pop_front());
72            assert_eq!(Some(i + 2), queue.pop_front());
73            assert_eq!(None, queue.pop_front());
74        }
75    }
76
77    #[test]
78    fn test_growable_queue_is_empty() {
79        let mut queue = TwoStacksQueue::<i32>::new();
80        assert_eq!(true, queue.is_empty());
81        queue.push_back(1);
82        assert_eq!(false, queue.is_empty());
83        queue.pop_front();
84        assert_eq!(true, queue.is_empty());
85    }
86
87    #[test]
88    fn test_growable_queue_front() {
89        let mut queue = TwoStacksQueue::<i32>::new();
90        assert_eq!(None, queue.front());
91        queue.push_back(1);
92        assert_eq!(1, *queue.front().unwrap());
93        queue.push_back(2);
94        assert_eq!(1, *queue.front().unwrap());
95        queue.pop_front();
96        assert_eq!(2, *queue.front().unwrap());
97        queue.pop_front();
98        assert_eq!(None, queue.front());
99    }
100
101    #[bench]
102    fn bench_growable_queue_push_pop(b: &mut Bencher) {
103        b.iter(|| {
104            let mut queue = TwoStacksQueue::<i32>::with_capacity(20);
105            for i in 0..10000 {
106                for _ in 0..10 {
107                    queue.push_back(i);
108                }
109
110                for _ in 0..10 {
111                    queue.pop_front();
112                }
113            }
114        });
115    }
116}
algo_rs/data_structure/queue/two_stacks_queue.rs

algo_rs/data_structure/queue/
two_stacks_queue.rs
