PadhaikoAll subjects

Past exam question: 2079 Ashwin (Back), Q3

Data Structure and Algorithms · 4 marks

Open in the Padhaiko app

Topic: Queues

Question

How 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.

To implement this list using a contiguous 1D array of fixed capacity MAX, two integer indices are maintained:

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:

  1. Linear Contiguous List with Element Shifting:
    • The front pointer is permanently pinned at index 0.
    • On enqueue(x): Append element at rear + 1 ( time).
    • On dequeue(): Remove items[0], then shift all subsequent elements items[1 ... rear] one position to the left ( time) and decrement rear.
    • Limitation: The shifting overhead makes dequeue inefficient for large lists.
  2. Pointer Advancement with Circular Modulo (Recommended Standard):
    • Both front and rear pointers 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:

Core Operation Mechanics (Circular List Implementation):

Answer:

An array implements a queue list by maintaining contiguous storage items[MAX] along with two index pointers:

  1. front indicating the head of the list for deletions (dequeues).
  2. rear indicating 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.

All past exam questions for Data Structure and Algorithms