Author at SyntaxFlow
At its core, this problem asks us to design a data structure that mimics a real-world queue (like a line of people waiting for a movie) using a standard array.
What is a Queue? A queue is a linear data structure that follows the FIFO principle.
What does FIFO mean? FIFO stands for First In, First Out. The first element you put into the queue is the very first one you take out. Imagine a checkout line at a grocery store: the first person to get in line is the first person to be served.
Input A series of operations:
push(x) (or enqueue): Insert an element x at the back of the queue.pop() (or dequeue): Remove the element from the front of the queue.front() (or peek): Look at the element at the front without removing it.Output
push(x) returns nothing.pop() returns the removed element.front() returns the front element.Constraints & Conditions
push an element but the queue is full.pop or get the front element, but the queue is completely empty.Small Example Assume Capacity = 5.
push(10)push(20)push(30)front()pop()front()Output:101020
Why is this output correct?
[10, 20, 30].front() looks at the earliest inserted element. It outputs 10.pop() removes and returns the earliest element. It outputs 10. The queue is now [20, 30].front() looks at the new front element, outputting 20.If we try to implement a queue just like a stack, we run into a major issue. Suppose we add elements at the end and remove them from the front
Suppose we use an array of size 5, and track elements using two pointers: front = 0 and rear = -1.
enqueue, we increment rear and insert.dequeue, we can either:front pointer instead of shifting: This is , but causes false overflow / memory waste.Index: 0 1 2 3 4
Array: [ X ][ X ][ X ][ ][ ]If we remove the first two elements, the array looks like this:
Index: 0 1 2 3 4
Array: [ _ ][ _ ][ X ][ ][ ]We have empty spaces at indices 0 and 1, but our "rear" of the queue is moving towards index 4. Eventually, we will hit the end of the array and trigger an "Overflow", even though there is perfectly good empty space at the beginning of the array.
The Solution: The Circular Array To fix this, we imagine the array is a circle. When the rear reaches the end of the array, it wraps around back to index 0. We achieve this using the modulo operator (%).
We need four variables:
arr: The array itself.front: Points to the index of the first element. Initializes to 0.rear: Points to the index of the last element. Initializes to -1.currentSize: Tracks the actual number of elements in the queue. Initializes to 0.currentSize is the source of truth for checking if the queue is empty (currentSize == 0) or full (currentSize == capacity). This saves us from complex pointer math.rear moves forward on Push: Insert at (rear + 1) % capacity.front moves forward on Pop: Remove at front, then update to (front + 1) % capacity.% prevents out-of-bounds errors and seamlessly loops pointers back to 0.These observations naturally lead to the circular array implementation because arrays provide access, and math (modulo) provides index wrapping.
Push(x)
currentSize == capacity, return an error.rear circularly: rear = (rear + 1) % capacity.arr[rear] = x.currentSize: currentSize = currentSize + 1.Pop()
currentSize == 0, return an error.arr[front] in a temporary variable.front circularly: front = (front + 1) % capacity.currentSize: currentSize = currentSize - 1.Front()
arr[front].isEmpty()
currentSize == 0.isFull()
currentSize == capacity.Let's simulate with Capacity = 3. Initial State: front = 0, rear = -1, currentSize = 0. Array: [_, _, _]
1. push(10)
rear = (-1 + 1) % 3 = 0. arr[0] = 10. currentSize = 1.[10, _, _]2. push(20)
rear = (0 + 1) % 3 = 1. arr[1] = 20. currentSize = 2.[10, 20, _]3. push(30)
rear = (1 + 1) % 3 = 2. arr[2] = 30. currentSize = 3.[10, 20, 30] (Queue is now full)4. pop()
arr[front] -> arr[0] (10).front = (0 + 1) % 3 = 1. currentSize = 2.10. Array logically: [_, 20, 30].5. push(40) (The Wrap Around)
rear = (2 + 1) % 3 = 0. (It wraps around!)arr[0] = 40. currentSize = 3.[40, 20, 30]. Array logically (from front to rear): 20 -> 30 -> 40.6. pop()
arr[front] -> arr[1] (20).front = (1 + 1) % 3 = 2. currentSize = 2.20. Array logically: [40, _, 30].#include <iostream>
using namespace std;
class Queue {
private:
int* arr; // Pointer to dynamic array
int capacity; // Maximum size of the queue
int frontIndex; // Index of the front element
int rearIndex; // Index of the rear element
int currentSize; // Current number of elements in the queue
public:
// Constructor to initialize the queue
Queue(int size) {
capacity = size;
arr = new int[capacity];
frontIndex = 0;
rearIndex = -1;
currentSize = 0;
}
// Destructor to free memory
~Queue() {
delete[] arr;
}
// Push (Enqueue) operation
void push(int x) {
if (currentSize == capacity) {
cout << "Queue Overflow!" << endl;
return;
}
// Move rear circularly using modulo
rearIndex = (rearIndex + 1) % capacity;
arr[rearIndex] = x;
currentSize++;
}
// Pop (Dequeue) operation
int pop() {
if (currentSize == 0) {
cout << "Queue Underflow!" << endl;
return -1; // Returning -1 as an error indicator
}
int poppedValue = arr[frontIndex];
// Move front circularly using modulo
frontIndex = (frontIndex + 1) % capacity;
currentSize--;
return poppedValue;
}
// Front (Peek) operation
int front() {
if (currentSize == 0) {
cout << "Queue is Empty!" << endl;
return -1;
}
return arr[frontIndex];
}
// Check if queue is empty
bool isEmpty() {
return currentSize == 0;
}
};Why does this circular array perfectly emulate a queue?
front and added at rear. Because front and rear only ever move in one direction (clockwise around the array), the oldest element is always exactly where front is pointing.currentSize < capacity, any physical empty space in the array will eventually be reached by rear.currentSize == capacity before pushes, rear can never overwrite front.push, pop, front, isEmpty). Mathematical operations (addition and modulo) and array access take constant time.front and rear will cycle through the array indefinitely without memory leaks.currentSize.front and rear will constantly sit at index 0.rear++ without modulo will cause a segmentation fault / index out-of-bounds error as soon as the queue reaches the end of the physical array.pop. This makes pop an operation instead of and will fail the interview.front and rear (e.g., (rear + 1) % capacity == front), but it requires creating a "dummy" space or complex logic. Using a currentSize variable is vastly simpler and less prone to bugs under pressure.Variables:
arr: The dynamically allocated underlying memory block.frontIndex & rearIndex: The active window of our circular structure.currentSize: The guardrail that prevents overlapping pointers.Important Lines:
rearIndex = (rearIndex + 1) % capacity; -> The "Wrap Around" logic for adding.frontIndex = (frontIndex + 1) % capacity; -> The "Wrap Around" logic for removing.
video reference:
reference video
problem link:
https://www.naukri.com/code360/problems/implement-queue-using-arrays_8390825