CS 455 Lecture Notes

Week Eleven, Thursday: Queues (continued)

Last time we saw some examples of queues in real life and in computer applications, and how they are particularly useful in process simulation. In this lecture we look at how to implement queues.

Queue ADT Implementation

You are now probably beginning to recognize a pattern in data structure ADT implementations: we given a choice between an array implementation and a linked list implementation. This was true for the bag ADT, the list ADT, and the stack ADT. So it is with the queue ADT.

Array Implementation

The array was a very natural way to implement a stack: just push and pop items at the end of the array. With a queue, we need to do operations at both ends, so this complicates the implementation quite a bit.

In a language that doesn't support pointers, such as Fortran, if you want to port a program that uses pointers, you have to simulate pointers with array indices. The array implementation of the queue ADT is actually an example of how this is done. It uses index variables to point to the front and rear elements of the array. Because the used portion of the array moves along to the right as the queue is used, it must eventually "wrap around" into a circular topology (as shown on page 368 of MS). This suggests that a linked list "ring" implementation might be a more natural way to implement a queue ADT.

However, one word of caution on terminology: an array used in such a way that indices (simulated pointers) wrap around is called a "circular array" but it is still identical in "structure" to an ordinary array. A linked list ring is actually implemented differently than a regular linked list. Note that the linked list implementation in MS does not use a ring.

Linked List Implementation

Priority Queues

Priority Queue Implementation

This page established November 8, 1999; last updated November 10, 1999.