The Queue

This chapter covers the Queue ADT, a collection where items leave in the same order they arrived. We implement it twice, as LinkedQueue and as ArrayQueue built on a circular array, and compare the two.

After reading this chapter, you should be able to:

  • Describe the Queue ADT: the enqueue, dequeue, front, and isEmpty operations, the first-in, first-out rule, and the documented exception behavior
  • Implement and trace LinkedQueue, with the front at the head and the back at the tail, and ArrayQueue, with a circular array and a size field to tell empty from full
  • Explain how a circular array removes the shifting that a straightforward array queue needs on either enqueue or dequeue
  • Compare the two implementations in time and memory

You can download the accompanying code for this chapter: starter and solution.

Sections

  1. Sharing a Printer
  2. The Queue ADT
  3. Queue ADT Specification
  4. Using a Linked List to Implement a Queue
  5. The LinkedQueue Class
  6. Implementing front, dequeue, and enqueue
  7. Tracing the LinkedQueue
  8. Using an Array to Implement a Queue
  9. The Circular Array
  10. Designing the ArrayQueue
  11. The ArrayQueue Class
  12. Implementing enqueue
  13. Tracing the ArrayQueue
  14. Two Queues, Side by Side