Double-Ended Queues

One variation on the queue is a double-ended queue, also called a deque (pronounced like the word deck). The key property of a deque is that entries can be quickly inserted and removed at both ends. This differs from a stack (which uses only one end) and an ordinary queue (in which things enter at one end and leave at the other). The ends of the deque are called front and back, but these designations are arbitrary since the same operations can occur at both ends.

In Java, deques are an interface (java.util.Deque) that includes all of the queue interface plus additional methods such as addFirst (to add an element to the front end) and removeLast (to remove an element from the back end). The key methods of the Deque interface are shown in Figure 7.11.

The most straightforward implementations of a deque are similar to the queue implementations that we have seen using a circular array or linked listbut a special technique must be used for a linked list. See if you can guess that special technique before looking at the answers to the Self-Test Exercises.

Figure 7.11 Key Methods of the Java Deque Interface

These are the key methods of the java.util.Deque interface, which depends on the generic type parameter E.

Operation	At the front end use ...	At the back end use ...
add an element	void push(E element) or void addFirst(E element)	void add(E element) or void addLast(E element)
remove an element and return a reference to the removed element	E remove( ) or E pop( ) or E removeFirst( )	E removeLast( )
retrieve an element without removing it	E peek( ) or E peekFirst( )	E peekLast( )

_______________________________________

1. Using a heap, implement the priority queue ADT from Section 7.4. You can store the heap in arrays, similar to the solution to Self-Test Exercise 1. To have FIFO behavior for elements with equal priority, you should have a third array called entered. The value of entered[i] tells when the data in node number i entered the priority queue. For example, the first element added has an entered value of 1, the second element has an entered value of 2, and so on. When you are comparing two elements with equal priority, use the entered value to break the tie (so that if two elements have the same priority number, then the one with the earlier entered value will come out of the priority queue first). Make sure you keep track of how many elements are in the heap so that if the size of the heap reaches the size of the arrays, you can increase the size of the arrays.