QUESTION 15

What is a queue’s removal rule?

2 marks

Answer

A queue follows first-in, first-out. enqueue adds at the rear and dequeue removes the earliest remaining item at the front.

Explain the queue ADT, operations, overflow, underflow and applications.

5 marks

Answer in brief

A queue preserves arrival order and exposes front/rear operations rather than arbitrary middle removal.

Operations

Create an empty queue.
enqueue(x) adds x at the rear if capacity permits.
dequeue returns and removes the front item if non-empty.
front or peek reads the front item without removing it.

Example

Enqueue 10, then 20 and 30. The first dequeue returns 10, leaving 20 at the front. This differs from a stack, which would remove 30 first. Queue values need not be sorted by magnitude or priority.

Overflow and underflow

A bounded array queue overflows when its capacity is exhausted. A linked queue can fail when node allocation fails. Underflow occurs when an empty queue is asked to remove or expose a front element. Return a status separately from the data value.

Applications

Queues model printer jobs, arrival-order service requests, buffered work and BFS traversal. A priority queue is a different contract that chooses by priority rather than ordinary FIFO arrival order.

Array choices and complexity

A naive linear array can waste released front positions until reset or shifting occurs. A circular array reuses them with wraparound and gives O(1) enqueue/dequeue in the shown implementation. Printing n queued values takes O(n). Capacity c requires O(c) storage, with O(1) counters.

Diagram or flowchart

CodeBhavya illustration of queue — Explain the queue ADT, operations, overflow, underflow and applications. · Download diagram

Complete C example

main.c

Download main.c

/* CodeBhavya | Data Structures AR25 | Learning example */
#include <stdio.h>
#define CAP 3
struct Queue { int data[CAP]; int front, count; };
int enqueue(struct Queue *q, int value)
{
    if (q->count == CAP) { return 0; }
    q->data[(q->front + q->count) % CAP] = value; ++q->count; return 1;
}
int dequeue(struct Queue *q, int *out)
{
    if (q->count == 0) { return 0; }
    *out = q->data[q->front]; q->front = (q->front + 1) % CAP; --q->count; return 1;
}

int main(void)
{
    struct Queue q = {{0}, 0, 0}; int value;
    if (!enqueue(&q, 10) || !enqueue(&q, 20) || !enqueue(&q, 30)) { return 1; }
    if (dequeue(&q, &value)) { printf("Removed = %d\n", value); }
    if (!enqueue(&q, 40)) { return 1; }
    while (dequeue(&q, &value)) { printf("%d\n", value); }
    return 0;
}

Sample input and output

The example uses values in the code.

Output

Removed = 10
20
30
40