leetcode_for_rust/cd0641_design_circular_deque/mod.rs
1//! Design Circular Deque [leetcode: design_circular_deque](https://leetcode.com/problems/design-circular-deque/)
2//!
3//! Design your implementation of the circular double-ended queue (deque).
4//!
5//! Your implementation should support following operations:
6//!
7//! * `MyCircularDeque(k)`: Constructor, set the size of the deque to be k.
8//! * `insertFront()`: Adds an item at the front of Deque. Return true if the operation is successful.
9//! * `insertLast()`: Adds an item at the rear of Deque. Return true if the operation is successful.
10//! * `deleteFront()`: Deletes an item from the front of Deque. Return true if the operation is successful.
11//! * `deleteLast()`: Deletes an item from the rear of Deque. Return true if the operation is successful.
12//! * `getFront()`: Gets the front item from the Deque. If the deque is empty, return -1.
13//! * `getRear()`: Gets the last item from Deque. If the deque is empty, return -1.
14//! * `isEmpty()`: Checks whether Deque is empty or not.
15//! * `isFull()`: Checks whether Deque is full or not.
16//!
17//! ***Example:***
18//!
19//! ```
20//! MyCircularDeque circularDeque = new MycircularDeque(3); // set the size to be 3
21//! circularDeque.insertLast(1); // return true
22//! circularDeque.insertLast(2); // return true
23//! circularDeque.insertFront(3); // return true
24//! circularDeque.insertFront(4); // return false, the queue is full
25//! circularDeque.getRear(); // return 2
26//! circularDeque.isFull(); // return true
27//! circularDeque.deleteLast(); // return true
28//! circularDeque.insertFront(4); // return true
29//! circularDeque.getFront(); // return 4
30//! ```
31//!
32//! **Note:**
33//!
34//! All values will be in the range of [0, 1000].
35//! The number of operations will be in the range of [1, 1000].
36//! Please do not use the built-in Queue library.
37
38/// # Solutions
39///
40/// # Approach 1:
41///
42/// * Time complexity: O(1)
43///
44/// * Space complexity: O(n)
45///
46/// * Runtime: 8 ms
47/// * Memory: 2.8 MB
48///
49/// ```rust
50/// struct MyCircularDeque {
51/// items: Vec<Option<i32>>,
52/// head: i32,
53/// tail: i32,
54/// capacity: i32,
55/// size: i32,
56/// }
57///
58///
59/// /**
60/// * `&self` means the method takes an immutable reference.
61/// * If you need a mutable reference, change it to `&mut self` instead.
62/// */
63/// impl MyCircularDeque {
64///
65/// /** Initialize your data structure here. Set the size of the deque to be k. */
66/// fn new(k: i32) -> Self {
67/// MyCircularDeque {
68/// items: vec![None; k as usize],
69/// head: 0,
70/// tail: -1,
71/// capacity: k,
72/// size: 0,
73/// }
74///
75/// }
76///
77/// /** Adds an item at the front of Deque. Return true if the operation is successful. */
78/// fn insert_front(&mut self, value: i32) -> bool {
79/// if self.is_full() { return false; }
80///
81/// self.head = self.get_curr_position(self.head);
82/// self.items[self.head as usize] = Some(value);
83/// self.size += 1;
84///
85/// if self.size == 1 { self.tail = self.head; }
86///
87/// true
88/// }
89///
90/// /** Adds an item at the rear of Deque. Return true if the operation is successful. */
91/// fn insert_last(&mut self, value: i32) -> bool {
92/// if self.is_full() { return false; }
93///
94/// self.tail = (self.tail + 1) % self.capacity;
95/// self.items[self.tail as usize] = Some(value);
96/// self.size += 1;
97///
98/// true
99/// }
100///
101/// /** Deletes an item from the front of Deque. Return true if the operation is successful. */
102/// fn delete_front(&mut self) -> bool {
103/// if self.is_empty() { return false; }
104///
105/// self.items[self.head as usize] = None;
106/// self.head = (self.head + 1) % self.capacity;
107/// self.size -= 1;
108///
109/// true
110/// }
111///
112/// /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
113/// fn delete_last(&mut self) -> bool {
114/// if self.is_empty() { return false; }
115///
116/// self.items[self.tail as usize] = None;
117/// self.tail = self.get_curr_position(self.tail);
118/// self.size -= 1;
119///
120/// true
121/// }
122///
123/// /** Get the front item from the deque. */
124/// fn get_front(&self) -> i32 {
125/// self.items[self.head as usize].unwrap_or(-1)
126/// }
127///
128/// /** Get the last item from the deque. */
129/// fn get_rear(&self) -> i32 {
130/// self.items[self.tail as usize].unwrap_or(-1)
131/// }
132///
133/// /** Checks whether the circular deque is empty or not. */
134/// fn is_empty(&self) -> bool {
135/// self.size == 0
136/// }
137///
138/// /** Checks whether the circular deque is full or not. */
139/// fn is_full(&self) -> bool {
140/// self.size == self.capacity
141/// }
142///
143/// fn get_curr_position(&self, p: i32) -> i32 {
144/// if p == 0 { self.capacity - 1 } else { (p - 1) % self.capacity }
145/// }
146/// }
147/// /**
148/// * Your MyCircularDeque object will be instantiated and called as such:
149/// * let obj = MyCircularDeque::new(k);
150/// * let ret_1: bool = obj.insert_front(value);
151/// * let ret_2: bool = obj.insert_last(value);
152/// * let ret_3: bool = obj.delete_front();
153/// * let ret_4: bool = obj.delete_last();
154/// * let ret_5: i32 = obj.get_front();
155/// * let ret_6: i32 = obj.get_rear();
156/// * let ret_7: bool = obj.is_empty();
157/// * let ret_8: bool = obj.is_full();
158/// */
159/// ```
160///
161#[allow(dead_code)]
162pub struct MyCircularDeque {
163 items: Vec<Option<i32>>,
164 head: i32,
165 tail: i32,
166 capacity: i32,
167 size: i32,
168}