Queue ADT; linear array queue and its wasted-space problem

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Why is 3 1 2 impossible as a stack permutation of 1 2 3? from Lesson 3.2.3
• In an array stack, what are the empty and full conditions? from Lesson 3.2.1
• Why can a function change the elements of an array argument? from Lesson 1.5.1

1 · The Hook

🎣

At a railway ticket counter, people join at the back and are served at the front. Nobody who arrived later is served earlier. Printers, call centres and network routers all serve their work this way: first come, first served.

2 · Predict First

🤔

A linear array queue of size 5 is filled with 5 items, then 2 are served. Can a new item be added? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

With the naive version, no: rear has reached the last index, so the queue reports “full” even though 2 slots at the front are now empty.

Output

10 20 full | front=2 rear=4

The queue ADT

A queue adds at one end (the rear) and removes at the other (the front): FIFO, first in first out.

All operations are O(1) in a good implementation.

Linear array implementation

Keep two indices: front (first item) and rear (last item). Start with front = 0, rear = −1. Enqueue: q[++rear] = x. Dequeue: return q[front++]. Empty when front > rear; full when rear == MAX − 1.

#define MAX 5
int q[MAX];
int front = 0, rear = -1;          /* front: first item, rear: last item */

int enqueue(int x)
{
    if (rear == MAX - 1) { printf("full "); return 0; }
    q[++rear] = x;
    return 1;
}

int dequeue(void)
{
    if (front > rear) { printf("empty "); return -1; }
    return q[front++];
}

int main(void)
{
    int i;
    for (i = 1; i <= 5; i++) enqueue(i * 10);
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    enqueue(60);                   /* two slots are free, yet ... */
    printf("| front=%d rear=%d\n", front, rear);
    return 0;
}

The wasted-space problem

Both indices only move forward. After some dequeues, the slots before front are empty but can never be used again: rear hits the end and the queue reports full while it has free room. Shifting all items back to the start on every dequeue fixes it but makes dequeue O(n). The real fix is to let the indices wrap around — the next lesson.

4 · Visual

After enqueue 10…50 and two dequeues: slots 0 and 1 are free, yet rear = 4 = MAX − 1, so the linear queue says “full”.

Ticket counter (FIFO):

   served <- [ 10 | 20 | 30 | 40 | 50 ] <- join
             front                rear

operation      array               front  rear
start          _  _  _  _  _          0    -1
enqueue x5     10 20 30 40 50         0     4
dequeue        __ 20 30 40 50         1     4   -> 10
dequeue        __ __ 30 40 50         2     4   -> 20
enqueue 60     rear == MAX-1  -> "full", although two slots are free

Indices that only move forward waste the slots behind front.

5 · Worked Examples

Example 1 Easy

Starting empty: enqueue A, B, C; dequeue; enqueue D; dequeue. What has been dequeued, and what is at the front?

Solution

Dequeued A then B. Front is C (queue: C, D).

Example 2 Medium

What does this print?

#define MAX 5
int q[MAX];
int front = 0, rear = -1;          /* front: first item, rear: last item */

int enqueue(int x)
{
    if (rear == MAX - 1) { printf("full "); return 0; }
    q[++rear] = x;
    return 1;
}

int dequeue(void)
{
    if (front > rear) { printf("empty "); return -1; }
    return q[front++];
}

int main(void)
{
    int i;
    for (i = 1; i <= 5; i++) enqueue(i * 10);
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    enqueue(60);                   /* two slots are free, yet ... */
    printf("| front=%d rear=%d\n", front, rear);
    return 0;
}

Solution

Five enqueues fill indices 0–4. Two dequeues return 10 and 20 (front = 2). The next enqueue sees rear == 4 and reports full.

Output

10 20 full | front=2 rear=4

Example 3 GATE

A linear array queue of size 8 (front = 0, rear = −1 at start) performs: enqueue ×6, dequeue ×4, enqueue ×3. How many of the last three enqueues succeed, and how many items are in the queue?

Solution

After 6 enqueues rear = 5; after 4 dequeues front = 4 (2 items). Enqueues can use indices 6 and 7 only: 2 succeed, the third fails although 4 slots are free. Items: 4.

6 · GATE Traps

⚠️

• FIFO: the oldest item leaves first (unlike a stack).
• In the linear version a “full” queue may have free slots before front.
• Empty condition for front = 0, rear = −1 start: front > rear.
• Number of items = rear − front + 1 in the linear version.
• Different books start front/rear differently; read the question’s convention.

8 · Memory Hook

🧠

“Ticket counter: join at the back, leave from the front.” In a straight corridor the queue slowly walks towards the wall and gets stuck, even with the corridor behind it empty.

9 · Connect the Dots

Lesson 3.2.1 built a stack with one index; a queue needs two, and in a plain array they waste space. Next lesson answers: how can the array be treated as a ring so that freed slots at the front are reused, and how do we tell a full ring from an empty one?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markFIFO

Enqueue 5, 7, 9; dequeue; enqueue 11; dequeue. Which value is dequeued second?

• (A) 7
• (B) 5
• (C) 11
• (D) 9

Q2NAT1 markCount

In a linear queue with front = 3 and rear = 7 (front = first item, rear = last item), how many items are there?

Numerical answer: ________

Q3MCQ2 marksOutput

What does this print?

#define MAX 5
int q[MAX];
int front = 0, rear = -1;          /* front: first item, rear: last item */

int enqueue(int x)
{
    if (rear == MAX - 1) { printf("full "); return 0; }
    q[++rear] = x;
    return 1;
}

int dequeue(void)
{
    if (front > rear) { printf("empty "); return -1; }
    return q[front++];
}

int main(void)
{
    int i;
    for (i = 1; i <= 5; i++) enqueue(i * 10);
    printf("%d ", dequeue());
    printf("%d ", dequeue());
    enqueue(60);                   /* two slots are free, yet ... */
    printf("| front=%d rear=%d\n", front, rear);
    return 0;
}

• (A) 10 20 | front=2 rear=5
• (B) 10 20 full | front=2 rear=4
• (C) 40 50 full | front=2 rear=4
• (D) 10 20 | front=2 rear=0

Q4MSQ1 markQueue facts

Which are true?

• (A) Enqueue adds at the front.
• (B) Dequeue removes the oldest item.
• (C) A linear array queue can report full while having free slots.
• (D) A queue is first-in, first-out.

Q5NAT2 marksWasted space

Linear queue of size 10 (front = 0, rear = −1): enqueue ×10, dequeue ×7. How many more enqueues succeed before it reports full?

Numerical answer: ________

11 · Rule Card

• Queue = FIFO: enqueue at rear, dequeue at front.
• Linear array: front = 0, rear = −1; q[++rear] = x; q[front++]; empty front > rear; full rear == MAX − 1.
• Items = rear − front + 1.
• Problem: slots before front are wasted; the next lesson bends the array into a ring.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

queue ADTFIFOenqueuedequeuefrontrearlinear array queue

13 · Answer Vault