问题描述
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?
问题分析
问题需要我们实现一个Ring Buffer，问题比较简单，我们在MyCircularQueue结构体内维护以下几个状态：
size表示queue的容量head指向队列头部tail指向队列尾部len当前队列长度list用于容纳元素的数组
每次进行EnQueue操作时，tail后移，为了不会越界，同时达到“环”的效果，自增后再对size取余作为tail新的值；这样就能保证当tail达到最大值时，会重新回到0
DeQueue操作同理
注意，在DeQueue操作时，我们仅仅是移动了head，实际list中原来的head指向的元素还是存在的，只不过不允许访问，可以被后续的EnQueue覆盖掉
示例代码
type MyCircularQueue struct {
list []int
size int
head int
tail int
len int
}
func Constructor(k int) MyCircularQueue {
return MyCircularQueue{
list: make([]int, k),
size: k,
head: 0,
tail: -1,
len: 0,
}
}
func (this *MyCircularQueue) EnQueue(value int) bool {
if this.IsFull() {
return false
}
this.len++
this.tail = (this.tail + 1) % this.size
this.list[this.tail] = value
return true
}
func (this *MyCircularQueue) DeQueue() bool {
if this.IsEmpty() {
return false
}
this.head = (this.head + 1) % this.size
this.len--
return true
}
func (this *MyCircularQueue) Front() int {
if this.IsEmpty() {
return -1
}
return this.list[this.head]
}
func (this *MyCircularQueue) Rear() int {
if this.IsEmpty() {
return -1
}
return this.list[this.tail]
}
func (this *MyCircularQueue) IsEmpty() bool {
return this.len == 0
}
func (this *MyCircularQueue) IsFull() bool {
return this.len == this.size
}