Page 54 - Data Structures Interactive Book

6.2.1 Queue Using Arrays

An array-based queue uses a fixed-size array to store elements, with two indices: front

and rear. The front index points to the first element, while the rear index points to the last

element. When an element is enqueued, it is added at the rear, and when dequeued, it is

removed from the front.

However, a simple array queue suffers from wasted space. Once elements are
removed from the front, those positions cannot be reused unless the queue is reset. To solve

this, circular queues are introduced, where the rear wraps around to the beginning of the

array when space is available. This ensures efficient memory utilization.
Example:

6.2.2 Queue Using Linked Lists

A linked list-based queue uses nodes to store elements dynamically. Each node

contains data and a pointer to the next node. The front pointer indicates the first element,

and the rear pointer indicates the last element.

This implementation avoids the fixed size limitation of arrays and allows the queue to
grow or shrink as needed. However, it requires extra memory for pointers and slightly more

complex operations. Linked list queues are particularly useful when the maximum size of the

queue is unknown or when flexibility is required.

54