A circular queue, also called a ring buffer, is a queue with a fixed number of places. After the last place comes the first place again, so the places form a ring.
A plain array wastes the places at the front after items leave. A ring does not. When an item leaves from the front, its place can be used again by a new item at the back.
Write a class MyCircularQueue with these methods:
MyCircularQueue(k): make an empty queue with k places.enQueue(value): add value at the back. Return true if it was added. Return false if there is no free place.deQueue(): remove the item at the front. Return true if an item was removed. Return false if the queue was empty.Front(): return the item at the front, or -1 if the queue is empty.Rear(): return the item at the back, or -1 if the queue is empty.isEmpty(): return true if the queue has no items.isFull(): return true if all k places are in use.
Do not use the ready-made queue or deque of your language.
Examples
Example 1:
Input
["MyCircularQueue", "Front", "enQueue", "enQueue", "Rear", "enQueue", "isFull", "enQueue", "deQueue", "enQueue", "Rear", "Front", "isEmpty"]
[[3], [], [7], [8], [], [9], [], [4], [], [4], [], [], []]
Output
[null, -1, true, true, 8, true, true, false, true, true, 4, 8, false]
Explanation
The queue has 3 places. At the start, Front() returns -1, because the queue is empty.
enQueue(7) and enQueue(8) work, and Rear() returns 8.
enQueue(9) works too, so isFull() is true. Then enQueue(4) returns false, because there is no free place.
deQueue() removes 7. Now enQueue(4) works, using the place that 7 freed.
Rear() returns 4 and Front() returns 8. The queue still has items, so isEmpty() returns false.
Example 2:
Input
["MyCircularQueue", "enQueue", "Front", "Rear", "deQueue", "deQueue", "isEmpty", "isFull"]
[[1], [6], [], [], [], [], [], []]
Output
[null, true, 6, 6, true, false, true, false]
Explanation
The queue has 1 place. After enQueue(6), both Front() and Rear() return 6.
The first deQueue() removes it. The second deQueue() returns false, because the queue is empty.
So isEmpty() is true and isFull() is false.