---
title: "Dynamic implementation of queue"
subject: "Data Structure and Algorithm"
chapter: 4
key: "semester_4/data_structure_and_algorithm:dynamic-queue-linked-algorithm"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/dynamic-queue-linked-algorithm
site: BCT Engineering
---

# Dynamic implementation of queue

Data Structure and Algorithm · Chapter 4: Linked lists

- Asked in: 2068 Bhadra, 6+2 marks
- Video: [Data structures: Linked List implementation of Queue](https://www.youtube.com/watch?v=A5_XdiK4J8A) — mycodeschool
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/dynamic-queue-linked-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-4

## Question

Write an algorithm for the dynamic implementation of queue. Also verify your algorithm with necessary illustrations.

## Short answer

Use a linked list with front and rear pointers. Enqueue adds a node at the rear; dequeue removes a node from the front. When the queue becomes empty, both pointers become NULL. No fixed capacity; operations take O(1) time.

## Answer

In **dynamic implementation**, queue nodes are allocated from the heap with `malloc` when an element is inserted and released with `free` when removed. A singly linked list with pointers `front` (deletion end) and `rear` (insertion end) is used, so the queue has no fixed capacity.

```c
struct node { int info; struct node *next; };
struct node *front = NULL, *rear = NULL;
```

#### ENQUEUE(x)
1. Allocate node `p`; if NULL print "overflow" and stop.
2. `p->info = x; p->next = NULL`.
3. If `rear == NULL` (empty): `front = rear = p`.
4. Else: `rear->next = p; rear = p`.

#### DEQUEUE()
1. If `front == NULL` print "underflow" and stop.
2. `p = front; x = p->info`.
3. `front = front->next`.
4. If `front == NULL` then `rear = NULL`.
5. `free(p)`; return `x`.

```c
void enqueue(int x) {
    struct node *p = (struct node *)malloc(sizeof(struct node));
    if (!p) { printf("Overflow\n"); return; }
    p->info = x; p->next = NULL;
    if (rear == NULL) front = rear = p;
    else { rear->next = p; rear = p; }
}
int dequeue(void) {
    if (!front) { printf("Underflow\n"); return -1; }
    struct node *p = front; int x = p->info;
    front = front->next;
    if (!front) rear = NULL;
    free(p);
    return x;
}
```

#### Verification (illustration)
| Operation | Queue (front -> rear) | front | rear |
|---|---|---|---|
| start | empty | NULL | NULL |
| enqueue(10) | 10 | 10 | 10 |
| enqueue(20) | 10, 20 | 10 | 20 |
| enqueue(30) | 10, 20, 30 | 10 | 30 |
| dequeue() returns 10 | 20, 30 | 20 | 30 |
| dequeue() returns 20 | 30 | 30 | 30 |
| dequeue() returns 30 | empty | NULL | NULL |
| dequeue() | underflow message | NULL | NULL |

```text
after enqueue 10,20,30:
front                 rear
  |                     |
  v                     v
 [10|*]->[20|*]->[30|NULL]
```
Elements leave in the order they entered (FIFO). Both operations are O(1).

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What does dynamic implementation mean?
   A. A fixed array is used
   B. The queue is circular
   C. All nodes are allocated at start
   D. Nodes are allocated by malloc on insertion and freed on removal
   Answer: D. No fixed capacity exists. (Key point: Dynamic meaning)

2. When enqueuing into an empty queue, what is done?
   A. front = rear = p
   B. rear->next = p
   C. front = NULL
   D. free(p)
   Answer: A. First node is both front and rear. (Key point: Enqueue empty)

3. Why is rear set to NULL when front becomes NULL after dequeue?
   A. To make it circular
   B. The queue is empty, and rear must not point to the freed node
   C. To count nodes
   D. To free front
   Answer: B. Otherwise rear dangles. (Key point: Dequeue empty)

## Related in Data Structure and Algorithm

- [Static vs dynamic implementation of list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astatic-vs-dynamic-list-example) — Data Structure and Algorithm, chapter 3, asked 2×
- [Static vs dynamic implementation of stack](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-static-vs-dynamic) — Data Structure and Algorithm, chapter 2
- [Circular queue algorithm with conditions](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Acircular-queue-algorithm-conditions) — Data Structure and Algorithm, chapter 2
- [Linear queue using array](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Alinear-queue-array-implementation) — Data Structure and Algorithm, chapter 2, asked 2×
- [Stack and queue using linked list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Astack-queue-singly-linked-list) — Data Structure and Algorithm, chapter 4, asked 2×
- [Why choose static or dynamic list](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Achoose-static-or-dynamic-list) — Data Structure and Algorithm, chapter 3

## Related in other subjects

- [Dynamic physical model with example](https://www.bctengineer.com/question.md?key=semester_8%2Fsimulation_and_modeling%3Adynamic-physical-model) — Simulation and Modeling, chapter 2, asked 3×
- [Dynamic model of armature-controlled DC motor](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Adc-motor-de-dynamic-model) — Control Systems, chapter 2
- [Planning in dynamic environment; linked bar chart](https://www.bctengineer.com/question.md?key=semester_7%2Fproject_engineering%3Aplanning-necessary-dynamic-linked-bar) — Project Engineering, chapter 3
- [Cristian's algorithm](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acristian-algorithm) — Distributed System, chapter 5, asked 3×