Queue Implementation Using Array in DSA C

Mental Model

A queue is like a line where the first person in is the first person out. We use an array to hold the line and two markers to track the front and back.

Analogy: Imagine a queue at a ticket counter. People join at the end and leave from the front. The array is the waiting area, front is the person served next, rear is the last person who joined.

front -> [ ] [ ] [ ] [ ] [ ] ← rear
indexes  0   1   2   3   4
Initially: front = -1, rear = -1, array empty

Dry Run Walkthrough

Input: Queue with size 5, enqueue 10, enqueue 20, dequeue, enqueue 30

Goal: Show how elements enter and leave the queue using array indexes front and rear

Step 1: enqueue 10: move rear forward and add 10

front = 0, rear = 0
10 -> null

Why: First element added, front and rear both point to index 0

Step 2: enqueue 20: move rear forward and add 20

front = 0, rear = 1
10 -> 20 -> null

Why: Add element at next position, rear moves to index 1

Step 3: dequeue: remove element at front and move front forward

front = 1, rear = 1
20 -> null

Why: Remove first element (10), front moves to index 1

Step 4: enqueue 30: move rear forward and add 30

front = 1, rear = 2
20 -> 30 -> null

Why: Add new element at index 2, rear moves forward

Result:

front = 1, rear = 2
20 -> 30 -> null

Annotated Code

DSA C

#include <stdio.h>
#define SIZE 5

typedef struct {
    int arr[SIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = -1;
    q->rear = -1;
}

int isFull(Queue* q) {
    return q->rear == SIZE - 1;
}

int isEmpty(Queue* q) {
    return q->front == -1 || q->front > q->rear;
}

void enqueue(Queue* q, int value) {
    if (isFull(q)) {
        printf("Queue is full\n");
        return;
    }
    if (q->front == -1) {
        q->front = 0; // set front to first element
    }
    q->rear++;
    q->arr[q->rear] = value; // add value at rear
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return -1;
    }
    int value = q->arr[q->front];
    q->front++; // move front forward
    return value;
}

void printQueue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty\n");
        return;
    }
    for (int i = q->front; i <= q->rear; i++) {
        printf("%d", q->arr[i]);
        if (i < q->rear) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    printQueue(&q);

    dequeue(&q);
    printQueue(&q);

    enqueue(&q, 30);
    printQueue(&q);

    return 0;
}

if (q->front == -1) { q->front = 0; }

initialize front when first element is enqueued

q->rear++; q->arr[q->rear] = value;

advance rear and insert new element

if (isEmpty(q)) { return -1; }

check if queue is empty before dequeue

int value = q->arr[q->front]; q->front++;

remove element at front and move front forward

for (int i = q->front; i <= q->rear; i++) { print elements }

print all elements from front to rear

Output

10 -> 20 -> null

20 -> null

20 -> 30 -> null

Complexity Analysis

Time: O(1) for enqueue and dequeue because we only move front or rear pointers once per operation

Space: O(n) because we use a fixed size array of size n to store elements

vs Alternative: Compared to linked list queue, array queue is simpler but fixed size; linked list can grow dynamically but uses extra memory for pointers

Edge Cases

enqueue when queue is full

prints 'Queue is full' and does not add element

DSA C

if (isFull(q)) { printf("Queue is full\n"); return; }

dequeue when queue is empty

prints 'Queue is empty' and returns -1

DSA C

if (isEmpty(q)) { printf("Queue is empty\n"); return -1; }

dequeue last element makes queue empty

front moves beyond rear, isEmpty returns true

DSA C

return q->front == -1 || q->front > q->rear;

When to Use This Pattern

When you need a first-in-first-out order with fixed size and fast access, use array queue pattern because it uses two pointers to track front and rear efficiently.

Common Mistakes

Mistake: Not initializing front to 0 on first enqueue, causing incorrect empty checks
Fix: Set front to 0 when first element is enqueued (front == -1 case)

Mistake: Not checking if queue is full before enqueue, causing overflow
Fix: Add isFull check before adding new element

Mistake: Not updating front after dequeue, causing stale front pointer
Fix: Increment front after removing element

Summary

Implements a queue using a fixed size array with front and rear pointers.

Use when you want a simple queue with known maximum size and fast enqueue/dequeue.

Remember to move front and rear pointers correctly and handle empty/full states.

Practice

1. What is the main characteristic of a queue implemented using an array?

easy

A. It follows First-In-First-Out (FIFO) order

B. It follows Last-In-First-Out (LIFO) order

C. It allows random access to elements

D. It stores elements in sorted order

Solution

1. Step 1: Understand queue behavior

   A queue is a data structure where the first element added is the first one to be removed, which is FIFO.

2. Step 2: Compare with options

   It follows First-In-First-Out (FIFO) order correctly states FIFO order. It follows Last-In-First-Out (LIFO) order is LIFO (stack), C allows random access (array), D stores sorted (not queue).

3. Final Answer:

   It follows First-In-First-Out (FIFO) order -> Option A

4. Quick Check:

   Queue = FIFO [OK]

Hint: Queue always removes the oldest element first [OK]

Common Mistakes:

• Confusing queue with stack (LIFO)
• Thinking queue allows random access
• Assuming queue sorts elements automatically

2. Which of the following is the correct way to declare a queue array of size 5 in C?

easy

A. queue int[5];

B. int queue[5];

C. int queue();

D. int queue = new int[5];

Solution

1. Step 1: Recall C array declaration syntax

   In C, arrays are declared as type name[size], e.g., int queue[5];

2. Step 2: Check each option

   int queue[5]; matches correct syntax. queue int[5]; is invalid syntax. int queue(); declares a function, not an array. int queue = new int[5]; is Java-style syntax.

3. Final Answer:

   int queue[5]; -> Option B

4. Quick Check:

   C array declaration = int name[size] [OK]

Hint: C arrays use type name[size] syntax [OK]

Common Mistakes:

• Using Java or other language syntax
• Confusing function declaration with array
• Missing semicolon or brackets

3. Consider this C code snippet for a queue implemented using an array of size 3:

int queue[3];
int front = -1, rear = -1;

// Enqueue 10
rear++;
queue[rear] = 10;
if(front == -1) front = 0;

// Enqueue 20
rear++;
queue[rear] = 20;

// Dequeue
int val = queue[front];
front++;

// Enqueue 30
rear++;
queue[rear] = 30;

// Current queue elements from front to rear?

medium

A. 30 -> null

B. 10 -> 20 -> 30 -> null

C. 20 -> 30 -> null

D. 10 -> 30 -> null

Solution

1. Step 1: Trace enqueue and dequeue operations

   Initially front = -1, rear = -1. Enqueue 10: rear=0, queue[0]=10, front=0. Enqueue 20: rear=1, queue[1]=20. Dequeue: val=queue[front]=queue[0]=10, front=1. Enqueue 30: rear=2, queue[2]=30.

2. Step 2: Identify current queue elements

   front=1, rear=2, so elements are queue[1]=20 and queue[2]=30. Hence queue is 20 -> 30 -> null.

3. Final Answer:

   20 -> 30 -> null -> Option C

4. Quick Check:

   After dequeue, front moves forward; queue = 20, 30 [OK]

Hint: After dequeue, front moves forward; queue shows elements from front to rear [OK]

Common Mistakes:

• Not updating front after dequeue
• Including dequeued elements in output
• Confusing front and rear indices

4. Identify the error in this queue enqueue function using array in C:

void enqueue(int queue[], int *rear, int size, int value) {
    if (*rear == size) {
        printf("Queue is full\n");
        return;
    }
    (*rear)++;
    queue[*rear] = value;
}

medium

A. rear should be compared with size - 1, not size

B. rear should be incremented after inserting value

C. Function should return int instead of void

D. queue array should be dynamically allocated

Solution

1. Step 1: Analyze the full condition

   The check if(*rear == size) is wrong. Array indices are 0 to size-1, so full when *rear == size-1 before incrementing. Current check allows overflow.

2. Step 2: Compare options

   rear should be compared with size - 1, not size identifies the correct fix: compare with size-1, not size. Others are incorrect.

3. Final Answer:

   rear should be compared with size - 1, not size -> Option A

4. Quick Check:

   Full: *rear == size-1 [OK]

Hint: Full check: rear == size - 1 [OK]

Common Mistakes:

• Comparing rear == size instead of size-1
• Incorrect overflow condition
• Ignoring zero-based indexing

5. You have a queue implemented using an array of size 4 with front = 1 and rear = 3. After dequeuing two elements and enqueuing one element, what will be the correct front and rear values if you implement a circular queue?

hard

A. front = 2, rear = 0

B. front = 3, rear = 1

C. front = 0, rear = 1

D. front = 3, rear = 0

Solution

1. Step 1: Understand initial state and operations

   Initial: front=1, rear=3, size=4. Dequeue twice: front moves forward twice. Since circular, front = (1 + 2) % 4 = 3.

2. Step 2: Enqueue one element

   rear moves forward by one circularly: rear = (3 + 1) % 4 = 0.

3. Final Answer:

   front = 3, rear = 0 -> Option D

4. Quick Check:

   Circular queue uses modulo for front and rear [OK]

Hint: Use modulo to wrap front and rear in circular queue [OK]

Common Mistakes:

• Not using modulo for circular increment
• Updating front or rear incorrectly
• Confusing front and rear positions