stdlib_rs/collections/
queue_with_stack.rs

1#![deny(missing_docs)]
2
3use std::iter::FromIterator;
4use std::mem;
5
6#[derive(Default, Debug, Eq, PartialEq)]
7/// A queue created with two stacks.
8pub struct Queue<T>(Vec<T>, Vec<T>);
9
10impl<T> Queue<T> {
11    /// Creates a new Queue.
12    pub fn new() -> Self {
13        Queue(vec![], vec![])
14    }
15
16    /// Adds an item to the end of the queue in O(1) time.
17    pub fn push(&mut self, item: T) {
18        self.0.push(item);
19    }
20
21    /// Removes the first item from the queue in O(n) time.
22    pub fn pop(&mut self) -> Option<T> {
23        self.move_to_second_stack();
24        self.1.pop()
25    }
26
27    fn move_to_second_stack(&mut self) {
28        let v = mem::take(&mut self.0);
29        let iter = v.into_iter().rev();
30        self.1.extend(iter);
31    }
32}
33
34impl<T> FromIterator<T> for Queue<T> {
35    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Queue<T> {
36        let mut queue = Queue::new();
37        for i in iter {
38            queue.push(i);
39        }
40        queue
41    }
42}
43
44impl<T> IntoIterator for Queue<T> {
45    type Item = T;
46    type IntoIter = std::iter::Chain<std::vec::IntoIter<T>, std::vec::IntoIter<T>>;
47
48    fn into_iter(self) -> Self::IntoIter {
49        self.0.into_iter().chain(self.1.into_iter())
50    }
51}
52
53/// Create a new `Queue` with the elements inside the macro.
54/// Works like the `vec![]` macro.
55/// ## Examples
56/// ```
57/// # use stdlib_rs::queue;
58/// # use stdlib_rs::collections::queue_with_stack::*;
59/// let queue = queue![1, 2, 3];
60/// let empty: Queue<i32> = queue![];
61/// let mut other = Queue::new();
62/// other.push(1);
63/// other.push(2);
64/// other.push(3);
65/// assert_eq!(queue, other);
66/// assert_eq!(empty, Queue::new());
67/// ```
68#[macro_export]
69macro_rules! queue [
70    ($($e:expr),*) => ({
71        let mut _temp  = Queue::new();
72        $(_temp.push($e);)*
73        _temp
74    })
75];
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80
81    #[test]
82    fn new_test() {
83        let queue: Queue<i32> = Queue::new();
84        assert_eq!(Queue::new(), queue);
85    }
86
87    #[test]
88    fn push_test() {
89        let mut queue = queue![];
90        queue.push(10);
91
92        assert_eq!(queue, Queue(vec![10], vec![]));
93    }
94
95    #[test]
96    fn pop_test() {
97        let mut queue = queue![10];
98
99        assert_eq!(queue.pop(), Some(10));
100    }
101
102    #[test]
103    fn push_then_pop_loop() {
104        let mut queue = queue![];
105        for i in 1..10 {
106            queue.push(i);
107        }
108        for i in 1..10 {
109            assert_eq!(queue.pop(), Some(i));
110        }
111    }
112
113    #[test]
114    fn from_iter_test() {
115        let iter = 1..5;
116        let mut queue = Queue::from_iter(iter);
117
118        for i in 1..5 {
119            assert_eq!(queue.pop(), Some(i));
120        }
121    }
122
123    #[test]
124    fn into_iter_test() {
125        let queue = queue![1, 2, 3];
126
127        let mut iter = queue.into_iter();
128        for i in 1..3 {
129            assert_eq!(Some(i), iter.next());
130        }
131    }
132}
stdlib_rs/collections/queue_with_stack.rs

stdlib_rs/collections/
queue_with_stack.rs
