The Deque

This chapter covers the Deque ADT, a collection where a client can add, remove, and look at items at either end. We implement it twice, as LinkedDeque built on a doubly linked list and as ArrayDeque built on a circular array, and compare the two.

After reading this chapter, you should be able to:

  • Describe the Deque ADT: the addFirst, addLast, removeFirst, removeLast, getFirst, getLast, and isEmpty operations, the two-ended access pattern, and the documented exception behavior
  • Explain how a deque can be used as a stack or as a queue, depending on which ends the client uses
  • Explain why a deque needs a doubly linked list where a singly linked list was enough for a queue
  • Implement and trace LinkedDeque, a doubly linked list with a sentinel node at each end
  • Implement and trace ArrayDeque, a circular array whose front index moves in both directions
  • Compare the two implementations in time and memory

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

Sections

  1. Double-Ended Queue (Deque)
  2. The Deque ADT
  3. Deque ADT Specification
  4. Using a Linked List to Implement a Deque
  5. The LinkedDeque Class
  6. Implementing addFirst and addLast
  7. Implementing getFirst, getLast, removeFirst, and removeLast
  8. Tracing the LinkedDeque
  9. Using an Array to Implement a Deque
  10. Designing the ArrayDeque
  11. The ArrayDeque Class
  12. Implementing addFirst, addLast, and grow
  13. Tracing the ArrayDeque
  14. Two Deques, Side by Side