Problem Statement
Implement a Queue using an array supporting:
enqueue(x)
dequeue()
getFront()
getRear()
Following FIFO:
First In First Out
Brute Force Intuition
Use:
ArrayList
Insert at end.
Remove from front.
But removing from front causes shifting.
Moving Towards the Array Approach
Maintain:
size
Insert:
arr[size++] = x;
Delete:
Shift all elements left.
Pattern Recognition
Queue
=> Array + Front Removal
Optimal Java Solution
class myQueue {
int[] arr;
int size;
public myQueue(int n) {
arr = new int[n];
size = 0;
}
public boolean isEmpty() {
return size == 0;
}
public boolean isFull() {
return size == arr.length;
}
public void enqueue(int x) {
if (!isFull()) {
arr[size++] = x;
}
}
public void dequeue() {
if (!isEmpty()) {
for (int i = 0; i < size - 1; i++) {
arr[i] = arr[i + 1];
}
size--;
}
}
public int getFront() {
return isEmpty() ? -1 : arr[0];
}
public int getRear() {
return isEmpty() ? -1 : arr[size - 1];
}
}
Dry Run
enqueue(10)
enqueue(20)
enqueue(30)
Queue:
10 20 30
dequeue()
Queue:
20 30
Front:
20
Rear:
30
Complexity Analysis
| Operation | Complexity |
|---|---|
| Enqueue | O(1) |
| Dequeue | O(N) |
| Front | O(1) |
| Rear | O(1) |
Interview One-Liner
Insert at rear and shift elements during deletion to maintain FIFO ordering.