Stacks and queues - Data Structures and Problem Solving Using Java - page 615

double-ended queues

16.5

A double-ended queue ( deque ) is like a queue, except that access is allowed
at both ends. Exercise 14.15 describes an application of the deque. Rather
than the terms enqueue and dequeue , the terms used in the literature are
addFront , addRear , removeFront , and removeRear .
A deque can be implemented using an array in much the same way as a
queue. The implementation is left as Exercise 16.5. However, using a singly
linked list does not work cleanly because it is difficult to remove the last item
in a singly linked list.
Java 6 adds the Deque interface to package java.util . This interface
extends Queue , thus automatically providing methods such as add , remove ,
element , size , and isEmpty . It also adds the familiar methods getFirst , getLast ,
addFirst , addLast , removeFirst , and removeLast that we know are part of
java.util.LinkedList . Indeed, in Java 6, LinkedList extends Deque . Addition-
ally, Java 6 provides a new class, ArrayDeque , that implements Deque . The
ArrayDeque uses an efficient array implementation of the type described in this
chapter and may be somewhat faster for queue operations than LinkedList .

A double-ended
queue ( deque )
allows access at
both ends.

summary

In this chapter we described implementation of the stack and queue classes.
Both classes can be implemented by using a contiguous array or a linked list.
In each case, all operations use constant time; thus all operations are fast.

key concepts

circular array implementation The use of wraparound to implement a queue.
(601)
double-ended queue (deque) A queue that allows access at both ends. (615)
wraparound Occurs when front or back returns to the beginning of the array
when it reaches the end. (601)

common errors

Using an implementation that does not provide constant-time access is a
bad error. There is no justification for this inefficiency.

1.