Design Circular Queue

The key idea

Problem

Design your implementation of a circular queue. A circular queue is a linear data structure that follows FIFO (First In First Out) order, but the last position is connected back to the first position to form a ring. It is also called a ring buffer.

The benefit of a circular queue is that we can use the spaces in front of the queue. In a normal queue, once it becomes full we cannot insert the next element even though there is empty space at the front. With a circular queue, those freed spaces can be reused.

Implement the MyCircularQueue class:

- MyCircularQueue(k) initializes the queue with a fixed capacity of k.
- enQueue(value) inserts value at the rear of the queue. Return true if the operation is successful, or false if the queue is full.
- deQueue() removes an element from the front of the queue. Return true if successful, or false if the queue is empty.
- Front() returns the front item, or -1 if the queue is empty.
- Rear() returns the rear item, or -1 if the queue is empty.
- isEmpty() returns true if the queue is empty.
- isFull() returns true if the queue is full.

You must implement each operation in O(1) time and you are not allowed to use the built-in queue library.

Constraints

• 1 <= k <= 1000
• 0 <= value <= 1000
• At most 3000 calls will be made to enQueue, deQueue, Front, Rear, isEmpty, and isFull.

Examples

Complexity

Time: O(1) Space: O(k)

More Design problems

• Binary Search Tree IteratorMEDIUM
• Design HashMapEASY
• Design HashSetEASY
• Design TwitterMEDIUM
• Detect SquaresMEDIUM
• Encode and Decode StringsMEDIUM
• Implement Queue using StacksEASY
• Implement Stack using QueuesEASY
• Insert Delete GetRandom O(1)MEDIUM
• LFU CacheHARD
• LRU CacheMEDIUM
• Maximum Frequency StackHARD