9.13.1. Linked Queues¶

The linked queue implementation is a straightforward adaptation of the linked list. Here is the linked queue class declaration.

1 / 4 Settings

<<<>>>

Members front and rear are pointers to the front and rear queue elements, respectively.

null

5

10

25

front

rear

null

front

rear

Saving...
Server Error
Resubmit

1 / 5 Settings

<<<>>>

Let's look at how the enqueue operation works.

null

3

21

30

10

front

rear

Saving...
Server Error
Resubmit

9.13.2. Linked Dequeue¶

1 / 8 Settings

<<<>>>

Now for the dequeue operation.

it

null

3

21

30

front

rear

Saving...
Server Error
Resubmit

9.13.3. Comparison of Array-Based and Linked Queues¶

All member functions for both the array-based and linked queue implementations require constant time. The space comparison issues are the same as for the equivalent stack implementations. Unlike the array-based stack implementation, there is no convenient way to store two queues in the same array, unless items are always transferred directly from one queue to the other.