# 5.3 Queues with an Array

> First in, first out. Why a naive array queue makes dequeue O(n), how a front index makes it O(1), and the wasted-slot problem that leads to the circular queue.

Chapter: Stacks & Queues · ~40 min · easy
URL: https://dsa.fetehadin.com/learn/queue-array

## Mental model

A **queue** is a line at the bank. New people join at the **rear**. The person at the **front** is served and leaves. Whoever arrived first is served first: **FIFO**, First In, First Out.

| Operation | Meaning |
| --- | --- |
| `enqueue(x)` | add x at the rear |
| `dequeue()` | remove and return the front item |
| `front()` / `peek()` | look at the front item |
| `isEmpty()` / `isFull()` | the usual checks |

### Attempt 1: keep the front at index 0

Enqueue is easy: `q[++rear] = x`. But on dequeue, the front leaves and **everyone shuffles forward**: `q[0] = q[1]; q[1] = q[2]; …`. That is **n − 1 moves per dequeue, so O(n)**. It is like a line where every customer takes a step each time someone is served.

### Attempt 2: move the front instead

Keep a **`front`** index. Dequeue just returns `q[front++]`. No one moves, so it is **O(1)**. It is like the cashier walking down the line instead of the line walking up.

The catch: `front` and `rear` only ever move right. After a few dequeues, the slots before `front` are empty, but `rear` hits `MAX - 1` and the queue says **"full"**. Those slots are wasted forever.

The fix is to let the indices **wrap around** to 0. That is the **circular queue**, next.

## C++ code: queue-array.cpp

```cpp
#include <iostream>
using namespace std;

const int MAX = 6;

// Naive queue: dequeue shifts everything left -> O(n)
struct NaiveQueue {
    int q[MAX]; int rear = -1; int moves = 0;
    void enqueue(int x) { if (rear == MAX - 1) { cout << "Full\n"; return; } q[++rear] = x; }
    int dequeue() {
        if (rear == -1) { cout << "Empty\n"; return -1; }
        int x = q[0];
        for (int i = 0; i < rear; i++) { q[i] = q[i + 1]; moves++; }
        rear--;
        return x;
    }
};

// Front-index queue: dequeue just moves front -> O(1), but wastes slots
struct FrontQueue {
    int q[MAX]; int front = 0, rear = -1;
    void enqueue(int x) { if (rear == MAX - 1) { cout << "Full (front=" << front << ")\n"; return; } q[++rear] = x; }
    int dequeue() {
        if (front > rear) { cout << "Empty\n"; return -1; }
        return q[front++];
    }
};

int main() {
    NaiveQueue a;
    for (int i = 1; i <= 5; i++) a.enqueue(i);
    cout << "naive: ";
    for (int i = 0; i < 5; i++) cout << a.dequeue() << " ";
    cout << "| element moves: " << a.moves << "\n";

    FrontQueue b;
    for (int i = 1; i <= 6; i++) b.enqueue(i);
    cout << "front-index: " << b.dequeue() << " " << b.dequeue() << "\n";
    b.enqueue(7);   // "Full" although 2 slots at the front are free
}
```

Expected output:

```text
naive: 1 2 3 4 5 | element moves: 10
front-index: 1 2
Full (front=2)
```

## Complexity

| Case | Cost |
| --- | --- |
| enqueue (at rear) | O(1) |
| dequeue, naive (shift left) | O(n) |
| dequeue, with front index | O(1) |
| front / isEmpty | O(1) |

Space: O(MAX)

The front-index version is fast but **cannot reuse** the slots it leaves behind. The **circular queue** fixes that.

## Videos

- [Introduction to Queues](https://youtu.be/XuCbpw6Bj1U) (mycodeschool): The queue ADT, FIFO and real examples, before code.
- [Array implementation of Queue](https://youtu.be/okr-XE8yTO8) (mycodeschool): Builds the array queue, shows the wasted space, and then the circular fix.

## Exam lens

Likely questions:

- Define a queue and its operations. What does FIFO mean?
- Why is dequeue O(n) in a naive array queue? How does a front index make it O(1)?
- Show front, rear and the array after: enqueue 5, enqueue 3, dequeue, enqueue 8.
- Explain why a linear array queue can report "full" when it has free slots.

Common mistakes:

- Confusing front and rear (items enter at the rear, leave at the front).
- Dequeuing without checking for empty.
- With a front index, testing `rear == -1` for empty. The correct test is `front > rear`.
- Forgetting that the naive shift costs n − 1 moves on every dequeue.

## Quick check

1. enqueue 1, enqueue 2, enqueue 3, dequeue, enqueue 4. Which item is at the front?
   A. 1
   B. 2
   C. 3
   D. 4
   Answer: B. 1 left first, so 2 is the oldest item still waiting.

2. Why is naive dequeue O(n)?
   A. It searches for the item
   B. Every remaining item shifts one place left
   C. It sorts the queue
   D. It allocates memory
   Answer: B. Removing q[0] and keeping the front at index 0 means moving everything else.

3. MAX = 4 front-index queue: enqueue ×4, dequeue ×2, enqueue 9. Result?
   A. 9 is stored at index 0
   B. "Full", because rear is already MAX − 1
   C. 9 replaces the front
   D. it crashes
   Answer: B. The rear cannot move past MAX − 1, so slots 0 and 1 are wasted.

4. Which is a queue, not a stack?
   A. Undo
   B. Browser back button
   C. Printer jobs
   D. Function calls
   Answer: C. Print jobs are served in the order they arrive.

## Practice

**Trace by hand.** Naive queue, MAX = 5. enqueue 10, 20, 30, 40; dequeue; dequeue; enqueue 50. Write the array, rear, and the number of element moves after each dequeue.

Solution:

- after 4 enqueues: `[10,20,30,40]`, rear 3
- dequeue → 10, array `[20,30,40]`, rear 2, **3 moves**
- dequeue → 20, array `[30,40]`, rear 1, **2 moves**
- enqueue 50 → `[30,40,50]`, rear 2


**Implement it.** Add `int size()` and `void print()` to the front-index queue, and make `enqueue` reset `front = 0, rear = -1` whenever the queue becomes empty.

Hint: Size is `rear - front + 1`. The reset is a cheap trick that recovers space only when the queue empties completely.

**Problems:**

- [Number of Recent Calls](https://leetcode.com/problems/number-of-recent-calls/) (easy). Hint: Enqueue every ping time; dequeue from the front while it is older than `t - 3000`. Return the size.
- [Implement Queue using Stacks](https://leetcode.com/problems/implement-queue-using-stacks/) (easy). Hint: An `in` stack for push and an `out` stack for pop. Only move items from in to out when out is empty.

## Mastery checklist

- [ ] I can explain FIFO and name the front and rear.
- [ ] I can explain why naive dequeue is O(n) and a front index makes it O(1).
- [ ] I can trace front and rear through a sequence of operations.
- [ ] I can explain the wasted-slot problem.