1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

//! Implement Queue using Stacks [leetcode: implement_queue_using_stacks](https://leetcode.com/problems/implement-queue-using-stacks/)
//!
//! Implement the following operations of a queue using stacks.
//! * push(x) -- Push element x to the back of queue.
//! * pop() -- Removes the element from in front of queue.
//! * peek() -- Get the front element.
//! * empty() -- Return whether the queue is empty.
//!
//! ***Example:***
//!
//! ```
//! MyQueue queue = new MyQueue();
//!
//! queue.push(1);
//! queue.push(2);
//! queue.peek();  // returns 1
//! queue.pop();   // returns 1
//! queue.empty(); // returns false
//! ```
//!
//! ***Notes***
//!
//! * You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
//! * Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
//! * You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

/// # Solutions
///
/// # Approach 1: Linkedlist
///
/// * Time complexity: O(1)
///
/// * Space complexity: O(1)
///
/// ```rust
/// use std::collections::LinkedList;
///
/// struct MyQueue {
///     queue: LinkedList<i32>,
/// }
///
///
/// /**
///  * `&self` means the method takes an immutable reference.
///  * If you need a mutable reference, change it to `&mut self` instead.
///  */
/// impl MyQueue {
///
///     /** Initialize your data structure here. */
///     fn new() -> Self {
///         return MyQueue { queue: LinkedList::new(), };
///
///     }
///
///     /** Push element x to the back of queue. */
///     fn push(&mut self, x: i32) {
///         self.queue.push_back(x);
///
///     }
///
///     /** Removes the element from in front of queue and returns that element. */
///     fn pop(&mut self) -> i32 {
///         return self.queue.pop_front().unwrap();
///     }
///
///     /** Get the front element. */
///     fn peek(&mut self) -> i32 {
///         let n = self.queue.pop_front().unwrap();
///         self.queue.push_front(n);
///         return n;
///     }
///
///     /** Returns whether the queue is empty. */
///     fn empty(&self) -> bool {
///         return self.queue.is_empty();
///     }
/// }
/// /**
///  * Your MyQueue object will be instantiated and called as such:
///  * let obj = MyQueue::new();
///  * obj.push(x);
///  * let ret_2: i32 = obj.pop();
///  * let ret_3: i32 = obj.peek();
///  * let ret_4: bool = obj.empty();
///  */
/// ```
///
/// # Approach 2: Stack
///
/// * Time complexity: O(n)
///
/// * Space complexity: O(n)
///
/// ```rust
/// #[derive(Default)]
/// struct MyQueue {
///     stack: Vec<i32>,
///     queue: Vec<i32>,
/// }
///
/// /**
///  * `&self` means the method takes an immutable reference.
///  * If you need a mutable reference, change it to `&mut self` instead.
///  */
/// impl MyQueue {
///
///     /** Initialize your data structure here. */
///     fn new() -> Self {
///         Default::default()
///     }
///
///     /** Push element x to the back of queue. */
///     fn push(&mut self, x: i32) {
///         while let Some(q) = self.queue.pop() { self.stack.push(q); }
///         self.stack.push(x);
///         while let Some(s) = self.stack.pop() { self.queue.push(s); }
///     }
///
///     /** Removes the element from in front of queue and returns that element. */
///     fn pop(&mut self) -> i32 {
///         self.queue.pop().unwrap()
///     }
///
///     /** Get the front element. */
///     fn peek(&self) -> i32 {
///         *self.queue.last().unwrap()
///     }
///
///     /** Returns whether the queue is empty. */
///     fn empty(&self) -> bool {
///         self.queue.is_empty()
///     }
/// }
///
/// /**
///  * Your MyQueue object will be instantiated and called as such:
///  * let obj = MyQueue::new();
///  * obj.push(x);
///  * let ret_2: i32 = obj.pop();
///  * let ret_3: i32 = obj.peek();
///  * let ret_4: bool = obj.empty();
///  */
/// ```
///
pub struct MyQueue;