Design Circular Queue

71.4k
0

Design a circular queue with a fixed capacity k. The queue must support insertion at the rear, deletion from the front, access to both end values, and checks for empty and full states.

Implement the following operations:

  • enQueue(value): Inserts value at the rear of the queue. Returns true if the insertion is successful; otherwise, returns false when the queue is full.

  • deQueue(): Removes the front value from the queue. Returns true if the deletion is successful; otherwise, returns false when the queue is empty.

  • Front(): Returns the front value of the queue. Returns -1 when the queue is empty.

  • Rear(): Returns the rear value of the queue. Returns -1 when the queue is empty.

  • isEmpty(): Returns true when the queue contains no values; otherwise, returns false.

  • isFull(): Returns true when the queue has reached its capacity k; otherwise, returns false.

Built-in queue libraries cannot be used.

Example 1

Input: ["MyCircularQueue", "enQueue", "enQueue", "enQueue", "enQueue", "Rear", "isFull", "deQueue", "enQueue", "Rear"]

values = [[3], [1], [2], [3], [4], [], [], [], [4], []]
Output: [null, true, true, true, false, 3, true, true, true, 4]
Explanation: A queue of capacity 3 stores 1, 2, and 3. Insertion of 4 fails while the queue is full. Deletion removes 1, and the next insertion places 4 in the freed array position. The rear value becomes 4.

Example 2

Input: ["MyCircularQueue", "Front", "deQueue", "enQueue", "isFull", "Rear"]

values = [[1], [], [], [7], [], []]


Output: [null, -1, false, true, true, 7]
Explanation: An empty queue returns -1 from Front and rejects deletion. Insertion of 7 fills the single available position, so isFull returns true and Rear returns 7.

Brute Force Approach

The simplest queue implementation uses a dynamic array to store values from left to right.

  • Insertion

    • Add each new value immediately after the current rear element, so the queue grows from left to right.

    • Reject insertion when the array size reaches capacity k.

  • Deletion

    • Remove the first value from the array.

    • Shift every remaining value one position toward the beginning.

    • Shifting keeps the front value at index 0, but makes deletion expensive.

  • Front and Rear

    • The first array value represents the front.

    • The last array value represents the rear.

    • Return -1 when the queue is empty.

  • Empty and Full Checks

    • The queue is empty when the array size is 0.

    • The queue is full when the array size is equal to k.

The main drawback is that every deletion may require shifting all remaining values. A circular array avoids this repeated shifting.

Algorithm

  • Initialize an empty dynamic array and store the maximum capacity k.

  • Before insertion, check whether the current size is equal to k. Return false when the queue is full.

  • Insert the new value immediately after the current rear element and return true.

  • Before deletion, check whether the current size is 0. Return false when the queue is empty.

  • Remove the first value and shift all remaining values one position toward the beginning.

  • Return the first value for Front() and the last value for Rear(). Return -1 when the queue is empty.

  • Return size == 0 for isEmpty() and size == k for isFull().

Dry Run

Circular Queue Brute

Circular Queue Brute

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
vector<int> queue;
int capacity;
public:
// Initialize an empty queue with fixed capacity.
Solution(int k) {
capacity = k;
}
// Insert a value at the rear when space remains.
bool enQueue(int value) {
// Full capacity prevents another insertion.
if (isFull()) {
return false;
}
// Appending preserves arrival order.
queue.push_back(value);
return true;
}
// Remove the front value and compact the array.
bool deQueue() {
// An empty queue has no removable value.
if (isEmpty()) {
return false;
}
// Front removal shifts every later value left.
queue.erase(queue.begin());
return true;
}
// Return the oldest stored value.
int Front() {
// An empty queue has no front value.
if (isEmpty()) {
return -1;
}
return queue[0];
}
// Return the newest stored value.
int Rear() {
// An empty queue has no rear value.
if (isEmpty()) {
return -1;
}
return queue[queue.size() - 1];
}
// Check for an empty queue.
bool isEmpty() {
return queue.empty();
}
// Check for a full queue.
bool isFull() {
return queue.size() == capacity;
}
};
// Driver code
int main() {
Solution obj(3);
cout << boolalpha << obj.enQueue(1) << "\n";
cout << boolalpha << obj.enQueue(2) << "\n";
cout << boolalpha << obj.enQueue(3) << "\n";
cout << boolalpha << obj.deQueue() << "\n";
cout << boolalpha << obj.enQueue(4) << "\n";
cout << obj.Rear() << "\n";
return 0;
}

Complexity Analysis

Time Complexity: O(k), each deQueue operation can shift up to k - 1 values; insertion takes amortized constant time, and access or state checks take constant time.

Space Complexity: O(k), the dynamic array stores at most k queue values.

Optimal Approach

A normal array queue may shift every value after deleting the front element. This shifting takes extra time. A circular queue avoids this problem by moving the front index instead of moving the stored values.

  • Using front and rear

    • front points to the first value of the queue.

    • rear points to the last inserted value.

    • During deletion, move front forward.

    • During insertion, move rear forward.

  • Using Modulo

    • An index may reach the end of the array while empty positions exist at the beginning.

    • Use % capacity to move the index back to 0.

    • This allows previously freed positions to be reused.

  • Tracking the Queue Size

    • The positions of front and rear alone may not clearly show whether the queue is empty or full.

    • Maintain a separate size counter.

    • size == 0 means the queue is empty.

    • size == capacity means the queue is full.

Algorithm

  • Create an array of size k to store the queue values. Set front = 0, rear = -1, and size = 0 because the queue is initially empty.

  • Before insertion, check whether size == k. Return false when both values are equal because the queue has no empty position.

  • For a successful Insertion:

    • Move rear using (rear + 1) % k so the index can wrap back to the beginning.

    • Store the new value at queue[rear].

    • Increment size because one new value has been added.

    • Return true.

  • Before deletion, check whether size == 0. Return false because an empty queue has no front value to remove.

  • For a successful Deletion:

    • Move front using (front + 1) % k instead of shifting the array values.

    • Decrement size because one value has been removed.

    • Return true.

  • For Front(), return queue[front] because front points to the first queue value. Return -1 when the queue is empty.

  • For Rear(), return queue[rear] because rear points to the last queue value. Return -1 when the queue is empty.

  • For isEmpty(), return size == 0. For isFull(), return size == k.

Dry Run

Circular Queue Optimal

Circular Queue Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
vector<int> queue;
int capacity;
int front;
int rear;
int size;
public:
// Initialize circular-array state with fixed capacity.
Solution(int k) {
queue.resize(k);
capacity = k;
front = 0;
rear = -1;
size = 0;
}
// Insert a value at the next circular rear position.
bool enQueue(int value) {
// Full capacity prevents another insertion.
if (isFull()) {
return false;
}
// Modulo reuses the first position after the array end.
rear = (rear + 1) % capacity;
queue[rear] = value;
size++;
return true;
}
// Remove the front value without shifting stored values.
bool deQueue() {
// An empty queue has no removable value.
if (isEmpty()) {
return false;
}
// Modulo advances the front across the array boundary.
front = (front + 1) % capacity;
size--;
return true;
}
// Return the oldest stored value.
int Front() {
// An empty queue has no front value.
if (isEmpty()) {
return -1;
}
return queue[front];
}
// Return the newest stored value.
int Rear() {
// An empty queue has no rear value.
if (isEmpty()) {
return -1;
}
return queue[rear];
}
// Check for an empty queue.
bool isEmpty() {
return size == 0;
}
// Check for a full queue.
bool isFull() {
return size == capacity;
}
};
// Driver code
int main() {
Solution obj(3);
cout << boolalpha << obj.enQueue(1) << "\n";
cout << boolalpha << obj.enQueue(2) << "\n";
cout << boolalpha << obj.enQueue(3) << "\n";
cout << boolalpha << obj.deQueue() << "\n";
cout << boolalpha << obj.enQueue(4) << "\n";
cout << obj.Rear() << "\n";
return 0;
}

Complexity Analysis

Time Complexity: O(1) per queue operation because every operation performs a constant number of comparisons, index calculations, or array accesses; construction takes O(k) time to create the fixed storage.

Space Complexity: O(k), the fixed array stores exactly k positions and the remaining state uses constant auxiliary space.

Interview follow-up Questions

A circular queue wraps the rear index to the beginning after free positions appear near index 0. A linear array queue can leave such positions unused unless values are shifted.

Queue
Comments0