Past exam question: 2079 Ashwin (Back), Q3
Open in the Padhaiko appHow do you implement array to represent queue as list?
Solution
Conceptual Foundation: Queue as an Ordered List: A queue is a linear ordered list where access is governed by the First-In, First-Out (FIFO) discipline.
- Elements are inserted exclusively at the tail/end called
rear. - Elements are removed exclusively at the head/beginning called
front.
To implement this list using a contiguous 1D array of fixed capacity MAX, two integer indices are maintained:
front: stores the array index of the current head element.rear: stores the array index of the most recently inserted tail element.
C Data Structure Representation:
#define MAX 100
typedef struct {
int items[MAX];
int front;
int rear;
} QueueList;
// Initialization routine: sets queue to an empty state
void initQueue(QueueList *q) {
q->front = -1;
q->rear = -1;
}Implementation Methods: Linear Shift vs. Circular Wrap-around: When implementing an array-based queue list, two primary strategies exist:
- Linear Contiguous List with Element Shifting:
- The
frontpointer is permanently pinned at index0. - On
enqueue(x): Append element atrear + 1( time). - On
dequeue(): Removeitems[0], then shift all subsequent elementsitems[1 ... rear]one position to the left ( time) and decrementrear. - Limitation: The shifting overhead makes dequeue inefficient for large lists.
- The
- Pointer Advancement with Circular Modulo (Recommended Standard):
- Both
frontandrearpointers move dynamically through the array. - To prevent the "false overflow" problem where freed memory at the front of the array cannot be reused, indices wrap around using modulo arithmetic:
- Both
- Both
enqueue()anddequeue()execute in optimal constant time with no element shifting.
Core Operation Mechanics (Circular List Implementation):
- Enqueue (Insert at List Rear): Check
(q->rear + 1) % MAX == q->front. If true, list capacity is exhausted (Queue Overflow). Otherwise, ifq->front == -1, setq->front = q->rear = 0; elseq->rear = (q->rear + 1) % MAX. Then setq->items[q->rear] = val. - Dequeue (Delete from List Front): Check
q->front == -1. If true, list is empty (Queue Underflow). Otherwise, readval = q->items[q->front]. Ifq->front == q->rear, resetq->front = q->rear = -1; elseq->front = (q->front + 1) % MAX. Returnval.
An array implements a queue list by maintaining contiguous storage items[MAX] along with two index pointers:
frontindicating the head of the list for deletions (dequeues).rearindicating the tail of the list for insertions (enqueues).
Using circular wrapping (), both insertion and deletion operate in strict constant time without the element-shifting overhead of static linear arrays.