955. Implement Queue by Circular

Description

Implement queue by circulant array. You need to support the following methods:

CircularQueue(n): initialize a circular array with size n to store elements

boolean isFull(): return true if the array is full

boolean isEmpty(): return true if there is no element in the array

void enqueue(element): add an element to the queue

int dequeue(): pop an element from the queue

it's guaranteed in the test cases we won't call enqueue if it's full and we also won't call dequeue if it's empty. So it's ok to raise exception in scenarios described above.

Example

Example 1:

Input:

CircularQueue(5)

isFull()

isEmpty()

enqueue(1)

enqueue(2)

dequeue()

Output:

["false","true","1"]

Example 2:

Input:

CircularQueue(5)

isFull()

isEmpty()

enqueue(1)

enqueue(2)

dequeue()

dequeue()

enqueue(1)

enqueue(2)

enqueue(3)

enqueue(4)

enqueue(5)

isFull()

dequeue()

dequeue()

dequeue()

dequeue()

dequeue()

Output:

["false","true","1","2","true","1","2","3","4","5"]

思路：

注意循环数组进队列出队列的front 和rear都会变，所以会存在可能头尾都在数组中间一段，而前后是空的，由于是循环队列，我们在增加元素时，如果此时 rear = array.length - 1 ，rear 需要更新为 0；同理，在元素出队时，如果 front = array.length - 1, front 需要更新为 0. 对此，我们可以通过对数组容量取模来更新。

代码：