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;