Implement a Circular Queue
Solve this ProblemEasy15 min
Topics
BasicsQueue
Companies
TCSInfosysWipro
Implement a queue that can hold at most
capacity items and run the given operations. "enqueue" adds args[i] and reports 1, or reports 0 if the queue is full; "dequeue" removes and reports the front item (−1 if empty); "front" reports the front item (−1 if empty); "isEmpty" and "isFull" report 1 or 0. Return all reported values in order.
A circular queueCircular Queue (Ring Buffer)A fixed-size queue stored in an array whose indexes wrap around from the end back to 0, so freed slots are reused. solves the wasted-space problem of a simple array queue: when the back reaches the end of the array, it wraps around to the slots freed at the front. The moduloModulo WraparoundUsing % capacity so an index that passes the end of the array continues from 0. operator does the wrapping, giving O(1) operations with no shifting and no wasted space.
Test Case 1:
Input:capacity = 2, ops = ["enqueue","enqueue","enqueue","dequeue","enqueue","front"], args = [1, 2, 3, 0, 4, 0]
Output:[1, 1, 0, 1, 1, 2]
Explanation:The third enqueue fails (full: 0). After dequeuing 1, there is room again for 4; the front is now 2.
Test Case 2:
Input:capacity = 1, ops = ["isEmpty","enqueue","isFull"], args = [0, 9, 0]
Output:[1, 1, 1]
Explanation:Empty at first; after one enqueue the size-1 queue is full.
Constraints
- ◆
1 ≤ capacity ≤ 1000 - ◆
1 ≤ ops.length ≤ 1000 - ◆
ops[i] is one of "enqueue", "dequeue", "front", "isEmpty", "isFull" - ◆
args[i] is the value for "enqueue" and 0 otherwise
Try the Dry Run
Approach & Solutions
Fixed Array with ShiftingGood
Use an array of size capacity with the front always at index 0 and a count of items. Enqueue writes at index count if there is room (report 1) or reports 0 when full. Dequeue reads index 0 and shifts the rest left. Correct, but every dequeue moves up to capacity items.
Time
O(capacity) per dequeueSpace
O(capacity)Java
class Solution {
public int[] circularQueueOps(int capacity, String[] ops, int[] args) {
int[] data = new int[capacity];
int count = 0;
List<Integer> out = new ArrayList<>();
for (int i = 0; i < ops.length; i++) {
if (ops[i].equals("enqueue")) {
if (count < capacity) {
data[count++] = args[i];
out.add(1);
} else {
out.add(0);
}
} else if (ops[i].equals("dequeue")) {
if (count == 0) {
out.add(-1);
} else {
out.add(data[0]);
for (int j = 1; j < count; j++) {
data[j - 1] = data[j];
}
count--;
}
} else if (ops[i].equals("front")) {
out.add(count == 0 ? -1 : data[0]);
} else if (ops[i].equals("isEmpty")) {
out.add(count == 0 ? 1 : 0);
} else if (ops[i].equals("isFull")) {
out.add(count == capacity ? 1 : 0);
}
}
return out.stream().mapToInt(Integer::intValue).toArray();
}
}Ring Buffer with WraparoundOptimal
Treat the array as a ring. Keep head (the front index) and count. The back slot is (head + count) % capacity, so enqueue writes there and dequeue just advances head = (head + 1) % capacity. The % makes indexes wrap from the end of the array back to 0, so freed slots are reused and nothing is ever shifted.
Time
O(1) per operationSpace
O(capacity)Java
class Solution {
public int[] circularQueueOps(int capacity, String[] ops, int[] args) {
int[] data = new int[capacity];
int head = 0, count = 0;
List<Integer> out = new ArrayList<>();
for (int i = 0; i < ops.length; i++) {
if (ops[i].equals("enqueue")) {
if (count < capacity) {
data[(head + count) % capacity] = args[i];
count++;
out.add(1);
} else {
out.add(0);
}
} else if (ops[i].equals("dequeue")) {
if (count == 0) {
out.add(-1);
} else {
out.add(data[head]);
head = (head + 1) % capacity;
count--;
}
} else if (ops[i].equals("front")) {
out.add(count == 0 ? -1 : data[head]);
} else if (ops[i].equals("isEmpty")) {
out.add(count == 0 ? 1 : 0);
} else if (ops[i].equals("isFull")) {
out.add(count == capacity ? 1 : 0);
}
}
return out.stream().mapToInt(Integer::intValue).toArray();
}
}