Java Reference
In-Depth Information
Queue, Deque, and
Priority Queue
Implementations
Chapter
11
Contents
A Linked Implementation of a Queue
An Array-Based Implementation of a Queue
A Circular Array
A Circular Array with One Unused Location
A Vector-Based Implementation of a Queue
Circular Linked Implementations of a Queue
A Two-Part Circular Linked Chain
Java Class Library: The Class
AbstractQueue
A Doubly Linked Implementation of a Deque
Possible Implementations of a Priority Queue
Prerequisites
Chapter
2
Bag Implementations That Use Arrays
Chapter
3
A Bag Implementation That Links Data
Chapter 6
Stack Implementations
Chapter
10
Queues, Deques, and Priority Queues
Objectives
After studying this chapter, you should be able to
•
Implement the ADT queue by using either a chain of linked nodes, an array, or a vector
•
Add or delete nodes at either end of a chain of doubly linked nodes
•
Implement the ADT deque by using a chain of doubly linked nodes
•
Implement the ADT priority queue by using either an array or a chain of linked nodes
T
he implementations of the ADT queue that are in this chapter use techniques
like the ones we used to implement the ADT bag and the ADT stack. We will use
either a chain of linked nodes, an array, or an instance of
Vector
to store the
queue's entries. Although the stack implementations we saw in Chapter 6 were
quite simple, the implementations of a queue are a bit more involved.
