Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Queue using Array

EASYProblemSolveExternal Links

Description

Implement a queue data structure using a fixed-size array. The array has a maximum capacity of n elements, and the queue must follow the FIFO (First In, First Out) principle — the element that is inserted first is the first one to be removed.

Your implementation must support the following operations:

  1. enqueue(x): Insert element x at the rear of the queue. If the queue is already full, do nothing.
  2. dequeue(): Remove the element from the front of the queue. If the queue is empty, do nothing.
  3. getFront(): Return the front element without removing it. If the queue is empty, return -1.
  4. getRear(): Return the rear element without removing it. If the queue is empty, return -1.
  5. isEmpty(): Return true if the queue contains no elements, otherwise return false.
  6. isFull(): Return true if the queue has reached its maximum capacity n, otherwise return false.

You will be given a sequence of queries. Each query calls one of the above operations. Implement the functions, and the driver code will handle the output.

Examples

Example 1

Input: n = 3, queries = [[1, 5], [1, 3], [1, 4], [3], [2], [5], [4]]

Output: [5, false, 4]

Explanation:

  • enqueue(5): Queue becomes [5]. Element 5 enters at the rear.
  • enqueue(3): Queue becomes [5, 3]. Element 3 joins behind 5.
  • enqueue(4): Queue becomes [5, 3, 4]. Element 4 joins at the end. Queue is now full.
  • getFront(): The front element is 5 (first in), so return 5.
  • dequeue(): Remove the front element 5. Queue becomes [3, 4].
  • isEmpty(): The queue still has elements 3 and 4, so return false.
  • getRear(): The rear element is 4 (last in), so return 4.

Example 2

Input: n = 2, queries = [[4], [1, 3], [1, 7], [6]]

Output: [-1, true]

Explanation:

  • getRear(): Queue is empty, no rear element. Return -1.
  • enqueue(3): Queue becomes [3].
  • enqueue(7): Queue becomes [3, 7]. Queue is now full (capacity 2).
  • isFull(): Queue contains 2 elements and capacity is 2. Return true.

Constraints

  • 1 ≤ n ≤ 10^3
  • 1 ≤ q ≤ 10^3
  • 0 ≤ x ≤ 10^5

Editorial

Brute Force

Intuition

Imagine a line of people at a ticket counter. When a new person arrives, they join at the end — that is straightforward. But when the person at the front gets their ticket and leaves, everyone behind them must shuffle one step forward to close the gap.

This is exactly how the brute force array-based queue works. We keep all queue elements packed into indices 0 through count - 1. Enqueue simply places the new element at arr[count] and increments the counter. But dequeue is expensive: after removing arr[0], we must shift every remaining element one position to the left so that the new front is again at index 0.

Enqueue is O(1), but dequeue costs O(n) because of this shifting. The root cause is a rigid design choice: insisting that the front of the queue always sits at index 0.

Step-by-Step Explanation

Let's trace through Example 1 with n = 3, queries: enqueue(5), enqueue(3), enqueue(4), getFront(), dequeue(), isEmpty(), getRear():

Step 1: Initialize: arr = [0, 0, 0], count = 0. All elements will occupy indices 0 through count - 1.

Step 2: enqueue(5): Place 5 at arr[0]. count = 1. arr = [5, 0, 0]. O(1).

Step 3: enqueue(3): Place 3 at arr[1]. count = 2. arr = [5, 3, 0]. O(1).

Step 4: enqueue(4): Place 4 at arr[2]. count = 3. arr = [5, 3, 4]. Queue is full. O(1).

Step 5: getFront(): Return arr[0] = 5. O(1).

Step 6: dequeue(): Remove arr[0] = 5. Now we must shift all remaining elements left:

  • arr[0] = arr[1] = 3 (shift element at index 1 to index 0)
  • arr[1] = arr[2] = 4 (shift element at index 2 to index 1)
  • count = 2. arr = [3, 4, 0]. This took 2 shifts — O(n) work.

Step 7: isEmpty(): count = 2 ≠ 0. Return false.

Step 8: getRear(): Return arr[count - 1] = arr[1] = 4.

Result: Output: [5, false, 4]. The dequeue operation was the bottleneck — it required shifting all elements.

Brute Force Queue — Element Shifting on Dequeue — Watch how every dequeue forces all remaining elements to shift one position left, making it an O(n) operation while enqueue remains O(1).

Algorithm

  1. Initialize an array arr of size n and set count = 0.
  2. enqueue(x):
    • If count == capacity, the queue is full — do nothing.
    • Otherwise, set arr[count] = x and increment count.
  3. dequeue():
    • If count == 0, the queue is empty — do nothing.
    • Save arr[0]. Shift all elements from index 1 to count-1 one position left. Decrement count.
  4. getFront():
    • If count == 0, return -1.
    • Otherwise, return arr[0].
  5. getRear():
    • If count == 0, return -1.
    • Otherwise, return arr[count - 1].
  6. isEmpty(): Return count == 0.
  7. isFull(): Return count == capacity.

Code

class MyQueue {
    int arr[1000];
    int count;
    int capacity;

public:
    MyQueue(int n) {
        capacity = n;
        count = 0;
    }

    void enqueue(int x) {
        if (count < capacity) {
            arr[count] = x;
            count++;
        }
    }

    void dequeue() {
        if (count == 0) return;
        for (int i = 1; i < count; i++) {
            arr[i - 1] = arr[i];
        }
        count--;
    }

    int getFront() {
        if (count == 0) return -1;
        return arr[0];
    }

    int getRear() {
        if (count == 0) return -1;
        return arr[count - 1];
    }

    bool isEmpty() {
        return count == 0;
    }

    bool isFull() {
        return count == capacity;
    }
};
class MyQueue:
    def __init__(self, n):
        self.arr = [0] * n
        self.capacity = n
        self.count = 0

    def enqueue(self, x):
        if self.count < self.capacity:
            self.arr[self.count] = x
            self.count += 1

    def dequeue(self):
        if self.count == 0:
            return
        for i in range(1, self.count):
            self.arr[i - 1] = self.arr[i]
        self.count -= 1

    def getFront(self):
        if self.count == 0:
            return -1
        return self.arr[0]

    def getRear(self):
        if self.count == 0:
            return -1
        return self.arr[self.count - 1]

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.capacity
class MyQueue {
    private int[] arr;
    private int count;
    private int capacity;

    public MyQueue(int n) {
        arr = new int[n];
        capacity = n;
        count = 0;
    }

    public void enqueue(int x) {
        if (count < capacity) {
            arr[count] = x;
            count++;
        }
    }

    public void dequeue() {
        if (count == 0) return;
        for (int i = 1; i < count; i++) {
            arr[i - 1] = arr[i];
        }
        count--;
    }

    public int getFront() {
        if (count == 0) return -1;
        return arr[0];
    }

    public int getRear() {
        if (count == 0) return -1;
        return arr[count - 1];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == capacity;
    }
}

Complexity Analysis

Time Complexity:

  • enqueue: O(1) — direct placement at arr[count].
  • dequeue: O(n) — shifts up to n - 1 elements left after removing the front.
  • getFront / getRear: O(1) — direct index access.
  • isEmpty / isFull: O(1) — single comparison.

For q queries where d are dequeues, the worst-case total time is O(n × d + (q - d)). With n and q both up to 10^3, the maximum work is around 10^6 — tolerable for these constraints but fundamentally inefficient.

Space Complexity: O(n)

We use a fixed-size array of n elements and one integer counter. No additional data structures.

Why This Approach Is Not Efficient

The brute force pays an O(n) cost on every dequeue because it insists that the front of the queue must always be at index 0. After removing the front element, every remaining element shifts left — a chain of writes that touches the entire occupied portion of the array.

With n = 10^3 and frequent dequeues, thousands of array writes happen per operation. For larger inputs, this becomes a serious bottleneck.

The fundamental question is: why must the front stay at index 0? It doesn't. If we let the front "float" by tracking its position with a pointer variable, the front simply moves forward on dequeue — no elements need to shift at all. This is the same insight that turned our brute force stack into an optimal one: maintain state instead of rediscovering it.

By adding a front pointer alongside a rear pointer, every single operation — enqueue, dequeue, getFront, getRear, isEmpty, and isFull — becomes O(1).

Optimal Approach - Front and Rear Pointers

Intuition

Think of a conveyor belt at an airport baggage claim. When a bag is picked up from the front, the belt does not shift all remaining bags forward — the collection point simply moves to the next bag. The belt keeps rolling; it is the pointer to the front that advances, not the bags themselves.

We apply the same principle to our array-based queue. Instead of keeping the front pinned at index 0, we maintain two index variables:

  • front: Points to the index of the first element in the queue.
  • rear: Points to the index of the last element in the queue.

When we enqueue, we increment rear and place the element. When we dequeue, we simply increment front — no shifting, no moving elements, just advancing a pointer. A separate count variable tracks the number of elements for isEmpty and isFull checks.

This eliminates the O(n) shifting entirely. Every operation becomes a direct array access plus a pointer increment — O(1) across the board.

Step-by-Step Explanation

Let's trace through Example 1 with n = 3, queries: enqueue(5), enqueue(3), enqueue(4), getFront(), dequeue(), isEmpty(), getRear():

Step 1: Initialize: arr = [0, 0, 0], front = 0, rear = -1, count = 0.

Step 2: enqueue(5): Increment rear to 0, set arr[0] = 5, count = 1. O(1).

Step 3: enqueue(3): Increment rear to 1, set arr[1] = 3, count = 2. O(1).

Step 4: enqueue(4): Increment rear to 2, set arr[2] = 4, count = 3. Queue is full. O(1).

Step 5: getFront(): Return arr[front] = arr[0] = 5. No pointers change. O(1).

Step 6: dequeue(): Save arr[front] = arr[0] = 5. Increment front to 1, count = 2. Return 5. O(1) — no shifting! Index 0 is now unused, and the front has moved to index 1.

Step 7: isEmpty(): count = 2 ≠ 0. Return false. O(1).

Step 8: getRear(): Return arr[rear] = arr[2] = 4. O(1).

Result: Output: [5, false, 4]. Every operation was O(1). The dequeue that cost O(n) with shifting now costs O(1) with a pointer increment.

Optimal Queue — Front and Rear Pointers Eliminate Shifting — Watch how front and rear pointers give O(1) access to both ends of the queue. Dequeue simply advances the front pointer — no element shifting needed.

Algorithm

  1. Initialize an array arr of size n. Set front = 0, rear = -1, count = 0.
  2. enqueue(x):
    • If count == capacity, the queue is full — do nothing.
    • Increment rear. Set arr[rear] = x. Increment count.
  3. dequeue():
    • If count == 0, the queue is empty — do nothing.
    • Increment front. Decrement count.
  4. getFront():
    • If count == 0, return -1.
    • Return arr[front].
  5. getRear():
    • If count == 0, return -1.
    • Return arr[rear].
  6. isEmpty(): Return count == 0.
  7. isFull(): Return count == capacity.

Code

class MyQueue {
    int arr[1000];
    int frontIdx;
    int rearIdx;
    int count;
    int capacity;

public:
    MyQueue(int n) {
        capacity = n;
        frontIdx = 0;
        rearIdx = -1;
        count = 0;
    }

    void enqueue(int x) {
        if (count < capacity) {
            rearIdx++;
            arr[rearIdx] = x;
            count++;
        }
    }

    void dequeue() {
        if (count > 0) {
            frontIdx++;
            count--;
        }
    }

    int getFront() {
        if (count == 0) return -1;
        return arr[frontIdx];
    }

    int getRear() {
        if (count == 0) return -1;
        return arr[rearIdx];
    }

    bool isEmpty() {
        return count == 0;
    }

    bool isFull() {
        return count == capacity;
    }
};
class MyQueue:
    def __init__(self, n):
        self.arr = [0] * n
        self.capacity = n
        self.front = 0
        self.rear = -1
        self.count = 0

    def enqueue(self, x):
        if self.count < self.capacity:
            self.rear += 1
            self.arr[self.rear] = x
            self.count += 1

    def dequeue(self):
        if self.count > 0:
            self.front += 1
            self.count -= 1

    def getFront(self):
        if self.count == 0:
            return -1
        return self.arr[self.front]

    def getRear(self):
        if self.count == 0:
            return -1
        return self.arr[self.rear]

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.capacity
class MyQueue {
    private int[] arr;
    private int frontIdx;
    private int rearIdx;
    private int count;
    private int capacity;

    public MyQueue(int n) {
        arr = new int[n];
        capacity = n;
        frontIdx = 0;
        rearIdx = -1;
        count = 0;
    }

    public void enqueue(int x) {
        if (count < capacity) {
            rearIdx++;
            arr[rearIdx] = x;
            count++;
        }
    }

    public void dequeue() {
        if (count > 0) {
            frontIdx++;
            count--;
        }
    }

    public int getFront() {
        if (count == 0) return -1;
        return arr[frontIdx];
    }

    public int getRear() {
        if (count == 0) return -1;
        return arr[rearIdx];
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == capacity;
    }
}

Complexity Analysis

Time Complexity: O(1) per operation

Every operation performs a fixed number of steps:

  • enqueue: one increment + one array write + one count increment = O(1)
  • dequeue: one increment + one count decrement = O(1)
  • getFront / getRear: one comparison + one array read = O(1)
  • isEmpty / isFull: one comparison = O(1)

For q queries, the total time is O(q) — optimal since each query must be processed at least once.

Space Complexity: O(n)

We use a fixed-size array of n elements plus three integer variables (front, rear, count). The extra variables are O(1) space, so overall space is O(n) — the same as the brute force. The improvement is purely in time complexity, achieved by spending three extra integers of space to track the queue boundaries.

Note: This linear approach consumes array space as elements are dequeued (indices before front become unused). For the given constraints (n ≤ 10^3, q ≤ 10^3), the array is large enough. For scenarios requiring space reuse, a circular queue (using modular arithmetic on front and rear) would reclaim dequeued slots.