Implement a Queue Using an Array

71.2k
0

Design a queue data structure using a fixed-capacity array of size capacity. The queue must support push(x), pop(), peek(), empty(), and size().

  • push(x) inserts x at the rear when the queue is not full.

  • pop() removes and returns the front value.

  • peek() returns the front value without removing it.

  • empty() returns whether the queue contains no values.

  • size() returns the current number of stored values.

When the queue is full, push(x) performs no insertion. When the queue is empty, pop() and peek() return -1.

Example 1

Input: Operations = push(10), push(20), push(30), peek(), pop(), peek(), empty()
Output: 10, 10, 20, false
Explanation: Values enter in order 10, 20, 30. The first front lookup gives 10, removal also returns 10, and the next front value becomes 20.

Example 2

Input: Operations = pop(), push(5), pop(), empty()
Output: -1, 5, true
Explanation: The first removal happens on an empty queue. After value 5 is inserted and removed, the queue becomes empty again.

Brute Force Approach

The simplest array queue keeps the front value at index 0. New values are added after the last stored value, so peek() remains simple.

The main cost appears during pop(). After removing the front value, every remaining value shifts one position left to place the next queue value at index 0.

Algorithm

  • Initialize a fixed-capacity array and set size = 0.

  • For push(value):

    • Return without insertion when size == capacity, because the queue is full.

    • Store the new value at index size.

    • Increase size by one.

  • For pop():

    • Return -1 when size == 0.

    • Store the value at arr[0].

    • Shift every remaining value one position left.

    • Decrease size by one.

    • Return the stored value.

  • For peek():

    • Return -1 when size == 0.

    • Return arr[0].

  • For empty():

    • Return whether size == 0.

Dry Run

queue-using-array-brute-force

queue-using-array-brute-force

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
vector<int> arr;
int capacity;
int size;
public:
// Initializes a fixed-size array queue.
Solution(int maxSize) {
capacity = maxSize;
size = 0;
arr.resize(capacity);
}
// Adds a value at the rear of the queue.
void push(int x) {
// A full array has no free rear position.
if (size == capacity) {
return;
}
arr[size] = x;
size++;
}
// Removes and returns the front value.
int pop() {
// An empty queue has no removable front value.
if (size == 0) {
return -1;
}
int frontValue = arr[0];
// Remaining values shift left to keep the front at index zero.
for (int index = 1; index < size; index++) {
arr[index - 1] = arr[index];
}
size--;
return frontValue;
}
// Returns the front value without removal.
int peek() {
// An empty queue has no front value.
if (size == 0) {
return -1;
}
return arr[0];
}
// Checks whether the queue has no values.
bool empty() {
return size == 0;
}
};
// Driver code
int main() {
Solution obj(4);
obj.push(10);
obj.push(20);
obj.push(30);
cout << obj.peek() << " ";
cout << obj.pop() << " ";
cout << obj.peek() << " ";
cout << boolalpha << obj.empty();
return 0;
}

Complexity Analysis

Time Complexity: O(N), because pop() may shift up to N - 1 values. push(), peek(), and empty() take O(1) time.

Space Complexity: O(CAP), where CAP is the given queue capacity. The array stores at most CAP queue values, and no additional data structure grows with the queue size.

Optimal Approach

Shifting values after every removal is unnecessary. The front index can simply move to the next position.

The array works like a circle. Modulo arithmetic moves front and rear back to index 0 after reaching the last index.

A removed value may still remain physically inside the array, but the value becomes stale after front moves forward. Queue operations read only active positions tracked by front, rear, and size, so stale values are never used. A future push() safely overwrites a stale value when rear reaches the same position again.

Algorithm

  • Initialize the array, front, rear, size, and capacity.

  • For push(value):

    • Return without insertion when size == capacity, because the queue is full.

    • Store the value at index rear.

    • Move rear to (rear + 1) % capacity.

    • Increase size by one.

    • Any stale value at rear gets overwritten because the position no longer belongs to an active queue element.

  • For pop():

    • Return -1 when size == 0.

    • Store the value at index front.

    • Move front to (front + 1) % capacity.

    • Decrease size by one.

    • Return the stored value.

  • For peek():

    • Return -1 when size == 0.

    • Return the value at index front.

  • For empty():

    • Return whether size == 0.

  • For full():

    • Return whether size == capacity.

Dry Run

Queue Using Array Optimal

Queue Using Array Optimal

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
vector<int> arr;
int capacity;
int size;
int front;
int rear;
public:
// Initializes a circular array queue.
Solution(int maxSize) {
capacity = maxSize;
size = 0;
front = 0;
rear = 0;
arr.resize(capacity);
}
// Adds a value at the rear of the queue.
void push(int x) {
// A full circular queue has no reusable slot.
if (size == capacity) {
return;
}
arr[rear] = x;
// Rear wraps around to reuse freed positions.
rear = (rear + 1) % capacity;
size++;
}
// Removes and returns the front value.
int pop() {
// An empty queue has no removable front value.
if (size == 0) {
return -1;
}
int frontValue = arr[front];
// Front advances to the next oldest value.
front = (front + 1) % capacity;
size--;
return frontValue;
}
// Returns the front value without removal.
int peek() {
// An empty queue has no front value.
if (size == 0) {
return -1;
}
return arr[front];
}
// Checks whether the queue has no values.
bool empty() {
return size == 0;
}
};
// Driver code
int main() {
Solution obj(3);
obj.push(10);
obj.push(20);
obj.push(30);
cout << obj.pop() << " ";
obj.push(40);
cout << obj.peek() << " ";
cout << boolalpha << obj.empty();
return 0;
}

Complexity Analysis

Time Complexity: O(1), because push, pop, peek, and empty use only direct array access and constant-time index updates.

Space Complexity: O(CAP), where CAP is the given queue capacity. The array can store at most CAP values, while only a fixed number of extra variables are used.

Interview follow-up Questions

Yes. A fixed-capacity array queue becomes full after capacity successful insertions without enough removals. A size == capacity check prevents writing outside the array.

Stack

Read Similar Blogs

Stack

Sum of Subarray Minimums

Given an integer array arr , consider every contiguous, non-empty subarray. Find the minimum value in each subarray and return the sum of all such minimum values modulo 10 9 + 7 . Inp...

116.5k
Stack

Introduction to Stack

Imagine a stack of plates in a kitchen. Whenever you add a new plate, you place it on the top. When you need a plate, you also take it from the top. You never remove a plate from the...

69.3k
Two PointerStackString

Reverse Every Word in a String

Given a string s , reverse every word individually. The spaces should remain in the same positions, and the order of words should not change. A word is a continuous group of non-space characters. I...

83.2k
Comments0