622. Design Circular Queue #

Problem #

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.

Implementation 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.

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 <= 1000
0 <= value <= 1000
At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Follow up:

Could you solve the problem without using the built-in queue?

Problem Statement #

Design your implementation of a circular queue. A circular queue is a linear data structure whose operations are based on the FIFO (First In First Out) principle, and the tail of the queue is connected after the head to form a circle. It is also called a “ring buffer”.

One benefit of a circular queue is that we can make use of the spaces previously used by the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is still space in front of the queue. But using a circular queue, we can use these spaces to store new values.

Your implementation should support the following operations:

MyCircularQueue(k): Constructor, sets the queue length to k.
Front: Gets the element from the front of the queue. If the queue is empty, return -1.
Rear: Gets the rear element. If the queue is empty, return -1.
enQueue(value): Inserts an element into the circular queue. Return true if the insertion is successful.
deQueue(): Deletes an element from the circular queue. Return true if the deletion is successful.
isEmpty(): Checks whether the circular queue is empty.
isFull(): Checks whether the circular queue is full.

Solution Approach #

Easy problem. Design a circular queue implemented with an array underneath. Additionally maintain 4 variables: the queue’s total cap, the queue’s current size, the index of the front element left, and the index after the rear element right. Each time an element is added, maintain left, right, and size. The indices need to take modulo cap, because after exceeding the size of cap, storage needs to wrap around. The code implementation is not difficult; see the code below for details.

Code #

package leetcode

type MyCircularQueue struct {
	cap   int
	size  int
	queue []int
	left  int
	right int
}

func Constructor(k int) MyCircularQueue {
	return MyCircularQueue{cap: k, size: 0, left: 0, right: 0, queue: make([]int, k)}
}

func (this *MyCircularQueue) EnQueue(value int) bool {
	if this.size == this.cap {
		return false
	}
	this.size++
	this.queue[this.right] = value
	this.right++
	this.right %= this.cap
	return true

}

func (this *MyCircularQueue) DeQueue() bool {
	if this.size == 0 {
		return false
	}
	this.size--
	this.left++
	this.left %= this.cap
	return true
}

func (this *MyCircularQueue) Front() int {
	if this.size == 0 {
		return -1
	}
	return this.queue[this.left]
}

func (this *MyCircularQueue) Rear() int {
	if this.size == 0 {
		return -1
	}
	if this.right == 0 {
		return this.queue[this.cap-1]
	}
	return this.queue[this.right-1]
}

func (this *MyCircularQueue) IsEmpty() bool {
	return this.size == 0
}

func (this *MyCircularQueue) IsFull() bool {
	return this.size == this.cap
}

/**
 * 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();
 */