In this chapter, we gave a linked list implementation of a queue. This implementation used two references, called front and rear, to refer to the front and the rear nodes of the queue (linked list). A circular linked list is similar to a regular linked list, except that the link field in the “last node” refers back to the “first node.” (Of course, after this change, it is no longer clear which node, if any, is intrinsically “first.”) If we use a circular linked list, then we need only one reference to implement a queue since the front node and the rear node are adjacent nodes, as at the top of the next column.

In the diagram, we have called the single reference rear because it refers to the last node in the queue. It turns out that this gives a more efficient implementation than having it refer to the first node in the queue. Redo the queue class using a circular linked list.

Transcribed Image Text:

rear Third item Second item Fourth item Front item