Description#
Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".
One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.
Implement the MyCircularQueue class:
MyCircularQueue(k) Initializes the object with the size of the queue to be k.int Front() Gets the front item from the queue. If the queue is empty, return -1.int Rear() Gets the last item from the queue. If the queue is empty, return -1.boolean enQueue(int value) Inserts an element into the circular queue. Return true if the operation is successful.boolean deQueue() Deletes an element from the circular queue. Return true if the operation is successful.boolean isEmpty() Checks whether the circular queue is empty or not.boolean isFull() Checks whether the circular queue is full or not.
You must solve the problem without using the built-in queue data structure in your programming language.
Example 1:
Input
["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
Output
[null, true, true, true, false, 3, true, true, true, 4]
Explanation
MyCircularQueue myCircularQueue = new MyCircularQueue(3);
myCircularQueue.enQueue(1); // return True
myCircularQueue.enQueue(2); // return True
myCircularQueue.enQueue(3); // return True
myCircularQueue.enQueue(4); // return False
myCircularQueue.Rear(); // return 3
myCircularQueue.isFull(); // return True
myCircularQueue.deQueue(); // return True
myCircularQueue.enQueue(4); // return True
myCircularQueue.Rear(); // return 4
Constraints:
1 <= k <= 10000 <= value <= 1000- At most
3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.
Solutions#
Solution 1#
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
| class MyCircularQueue:
def __init__(self, k: int):
self.q = [0] * k
self.front = 0
self.size = 0
self.capacity = k
def enQueue(self, value: int) -> bool:
if self.isFull():
return False
idx = (self.front + self.size) % self.capacity
self.q[idx] = value
self.size += 1
return True
def deQueue(self) -> bool:
if self.isEmpty():
return False
self.front = (self.front + 1) % self.capacity
self.size -= 1
return True
def Front(self) -> int:
return -1 if self.isEmpty() else self.q[self.front]
def Rear(self) -> int:
if self.isEmpty():
return -1
idx = (self.front + self.size - 1) % self.capacity
return self.q[idx]
def isEmpty(self) -> bool:
return self.size == 0
def isFull(self) -> bool:
return self.size == self.capacity
# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()
|
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
| class MyCircularQueue {
private int[] q;
private int front;
private int size;
private int capacity;
public MyCircularQueue(int k) {
q = new int[k];
capacity = k;
}
public boolean enQueue(int value) {
if (isFull()) {
return false;
}
int idx = (front + size) % capacity;
q[idx] = value;
++size;
return true;
}
public boolean deQueue() {
if (isEmpty()) {
return false;
}
front = (front + 1) % capacity;
--size;
return true;
}
public int Front() {
if (isEmpty()) {
return -1;
}
return q[front];
}
public int Rear() {
if (isEmpty()) {
return -1;
}
int idx = (front + size - 1) % capacity;
return q[idx];
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == capacity;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue obj = new MyCircularQueue(k);
* boolean param_1 = obj.enQueue(value);
* boolean param_2 = obj.deQueue();
* int param_3 = obj.Front();
* int param_4 = obj.Rear();
* boolean param_5 = obj.isEmpty();
* boolean param_6 = obj.isFull();
*/
|
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
| class MyCircularQueue {
private:
int front;
int size;
int capacity;
vector<int> q;
public:
MyCircularQueue(int k) {
capacity = k;
q = vector<int>(k);
front = size = 0;
}
bool enQueue(int value) {
if (isFull()) return false;
int idx = (front + size) % capacity;
q[idx] = value;
++size;
return true;
}
bool deQueue() {
if (isEmpty()) return false;
front = (front + 1) % capacity;
--size;
return true;
}
int Front() {
if (isEmpty()) return -1;
return q[front];
}
int Rear() {
if (isEmpty()) return -1;
int idx = (front + size - 1) % capacity;
return q[idx];
}
bool isEmpty() {
return size == 0;
}
bool isFull() {
return size == capacity;
}
};
/**
* Your MyCircularQueue object will be instantiated and called as such:
* MyCircularQueue* obj = new MyCircularQueue(k);
* bool param_1 = obj->enQueue(value);
* bool param_2 = obj->deQueue();
* int param_3 = obj->Front();
* int param_4 = obj->Rear();
* bool param_5 = obj->isEmpty();
* bool param_6 = obj->isFull();
*/
|
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
| type MyCircularQueue struct {
front int
size int
capacity int
q []int
}
func Constructor(k int) MyCircularQueue {
q := make([]int, k)
return MyCircularQueue{0, 0, k, q}
}
func (this *MyCircularQueue) EnQueue(value int) bool {
if this.IsFull() {
return false
}
idx := (this.front + this.size) % this.capacity
this.q[idx] = value
this.size++
return true
}
func (this *MyCircularQueue) DeQueue() bool {
if this.IsEmpty() {
return false
}
this.front = (this.front + 1) % this.capacity
this.size--
return true
}
func (this *MyCircularQueue) Front() int {
if this.IsEmpty() {
return -1
}
return this.q[this.front]
}
func (this *MyCircularQueue) Rear() int {
if this.IsEmpty() {
return -1
}
idx := (this.front + this.size - 1) % this.capacity
return this.q[idx]
}
func (this *MyCircularQueue) IsEmpty() bool {
return this.size == 0
}
func (this *MyCircularQueue) IsFull() bool {
return this.size == this.capacity
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* obj := Constructor(k);
* param_1 := obj.EnQueue(value);
* param_2 := obj.DeQueue();
* param_3 := obj.Front();
* param_4 := obj.Rear();
* param_5 := obj.IsEmpty();
* param_6 := obj.IsFull();
*/
|
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
| class MyCircularQueue {
private queue: number[];
private left: number;
private right: number;
private capacity: number;
constructor(k: number) {
this.queue = new Array(k);
this.left = 0;
this.right = 0;
this.capacity = k;
}
enQueue(value: number): boolean {
if (this.isFull()) {
return false;
}
this.queue[this.right % this.capacity] = value;
this.right++;
return true;
}
deQueue(): boolean {
if (this.isEmpty()) {
return false;
}
this.left++;
return true;
}
Front(): number {
if (this.isEmpty()) {
return -1;
}
return this.queue[this.left % this.capacity];
}
Rear(): number {
if (this.isEmpty()) {
return -1;
}
return this.queue[(this.right - 1) % this.capacity];
}
isEmpty(): boolean {
return this.right - this.left === 0;
}
isFull(): boolean {
return this.right - this.left === this.capacity;
}
}
/**
* Your MyCircularQueue object will be instantiated and called as such:
* var obj = new MyCircularQueue(k)
* var param_1 = obj.enQueue(value)
* var param_2 = obj.deQueue()
* var param_3 = obj.Front()
* var param_4 = obj.Rear()
* var param_5 = obj.isEmpty()
* var param_6 = obj.isFull()
*/
|
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
| struct MyCircularQueue {
queue: Vec<i32>,
left: usize,
right: usize,
capacity: usize,
}
/**
* `&self` means the method takes an immutable reference.
* If you need a mutable reference, change it to `&mut self` instead.
*/
impl MyCircularQueue {
fn new(k: i32) -> Self {
let k = k as usize;
Self {
queue: vec![0; k],
left: 0,
right: 0,
capacity: k,
}
}
fn en_queue(&mut self, value: i32) -> bool {
if self.is_full() {
return false;
}
self.queue[self.right % self.capacity] = value;
self.right += 1;
true
}
fn de_queue(&mut self) -> bool {
if self.is_empty() {
return false;
}
self.left += 1;
true
}
fn front(&self) -> i32 {
if self.is_empty() {
return -1;
}
self.queue[self.left % self.capacity]
}
fn rear(&self) -> i32 {
if self.is_empty() {
return -1;
}
self.queue[(self.right - 1) % self.capacity]
}
fn is_empty(&self) -> bool {
self.right - self.left == 0
}
fn is_full(&self) -> bool {
self.right - self.left == self.capacity
}
}/**
* Your MyCircularQueue object will be instantiated and called as such:
* let obj = MyCircularQueue::new(k);
* let ret_1: bool = obj.en_queue(value);
* let ret_2: bool = obj.de_queue();
* let ret_3: i32 = obj.front();
* let ret_4: i32 = obj.rear();
* let ret_5: bool = obj.is_empty();
* let ret_6: bool = obj.is_full();
*/
|
