Implement a Queue Using an Array
Solve this ProblemEasy15 min
Topics
BasicsQueue
Companies
TCSInfosysWipro
Implement a queue and run a list of operations on it.
ops[i] is one of "enqueue" (add args[i] at the back), "dequeue" (remove and report the front item, or −1 if empty), "front" (report the front item without removing it, or −1), "isEmpty" (report 1 or 0) and "size". Return everything reported, in order — "enqueue" reports nothing.
A queueQueueA first-in, first-out (FIFO) collection: items join at the back and leave from the front. works like a line of people: the first to arrive is the first served. Storing it in an array raises a practical question — what happens to the empty slot at the front after a dequeue? Shifting everything left is easy but slow; moving a head indexHead IndexAn index that marks where the front of a queue currently is inside its array. instead makes every operation O(1).
Test Case 1:
Input:ops = ["enqueue","enqueue","dequeue","front","size"], args = [5, 8, 0, 0, 0]
Output:[5, 8, 1]
Explanation:dequeue returns 5 (first in), front is then 8, and one item is left.
Test Case 2:
Input:ops = ["dequeue","isEmpty"], args = [0, 0]
Output:[-1, 1]
Explanation:Removing from an empty queue gives −1; the queue is empty.
Constraints
- ◆
1 ≤ ops.length ≤ 1000 - ◆
ops[i] is one of "enqueue", "dequeue", "front", "isEmpty", "size" - ◆
args[i] is the value for "enqueue" and 0 otherwise
Try the Dry Run
Approach & Solutions
Remove from the Front of a ListBrute
Keep the queue in a list with the front at index 0: enqueue appends at the end, dequeue removes index 0. It is simple, but removing the first element makes every remaining element shift one place left, so each dequeue costs O(n). Every operation except enqueue adds one value to the output.
Time
O(n) per dequeueSpace
O(n)Java
class Solution {
public int[] queueOps(String[] ops, int[] args) {
List<Integer> queue = new ArrayList<>();
List<Integer> out = new ArrayList<>();
for (int i = 0; i < ops.length; i++) {
if (ops[i].equals("enqueue")) {
queue.add(args[i]);
} else if (ops[i].equals("dequeue")) {
out.add(queue.isEmpty() ? -1 : queue.remove(0));
} else if (ops[i].equals("front")) {
out.add(queue.isEmpty() ? -1 : queue.get(0));
} else if (ops[i].equals("isEmpty")) {
out.add(queue.isEmpty() ? 1 : 0);
} else if (ops[i].equals("size")) {
out.add(queue.size());
}
}
return out.stream().mapToInt(Integer::intValue).toArray();
}
}Moving Front IndexOptimal
Never shift anything. Store items in an array and keep two indexes: head points at the front item and tail at the next free slot. Enqueue writes at tail and moves tail on; dequeue reads at head and moves head on. The size is tail − head, and the queue is empty when they meet.
Time
O(1) per operationSpace
O(n)Java
class Solution {
public int[] queueOps(String[] ops, int[] args) {
int[] data = new int[ops.length];
int head = 0, tail = 0;
List<Integer> out = new ArrayList<>();
for (int i = 0; i < ops.length; i++) {
if (ops[i].equals("enqueue")) {
data[tail++] = args[i];
} else if (ops[i].equals("dequeue")) {
out.add(head < tail ? data[head++] : -1);
} else if (ops[i].equals("front")) {
out.add(head < tail ? data[head] : -1);
} else if (ops[i].equals("isEmpty")) {
out.add(head == tail ? 1 : 0);
} else if (ops[i].equals("size")) {
out.add(tail - head);
}
}
return out.stream().mapToInt(Integer::intValue).toArray();
}
}