Deque (Double Ended Queue)

Deque (Double ended queue)

[Deque] [ Hello. This is Rachel Cardell-Oliver from the University of Western Australia]

The Deque Interface

Usually pronounced asdeck, a deque is a double-ended-queue. A double-ended-queue is a linear collection of elements that supports the insertion and removal of elements at both end points. TheDequeinterface is a richer abstract data type than both StackandQueuebecause it implements both stacks and queues at the same time. TheDequeinterface, defines methods to access the elements at both ends of theDequeinstance. Methods are provided to insert, remove, and examine the elements. Predefined classes like ArrayDequeandLinkedList implement theDequeinterface.

Note that theDequeinterface can be used both as last-in-first-out stacks and first-in-first-out queues. The methods given in theDequeinterface are divided into three parts:

Insert

TheaddfirstandofferFirstmethods insert elements at the beginning of theDequeinstance. The methodsaddLastand offerLastinsert elements at the end of theDequeinstance. When the capacity of theDequeinstance is restricted, the preferred methods areofferFirstandofferLastbecauseaddFirstmight fail to throw an exception if it is full.

Remove

TheremoveFirstandpollFirstmethods remove elements from the beginning of theDequeinstance. TheremoveLast andpollLastmethods remove elements from the end. The methodspollFirstandpollLastreturnnullif theDequeis empty whereas the methodsremoveFirstandremoveLastthrow an exception if theDequeinstance is empty.

Retrieve

The methodsgetFirstandpeekFirstretrieve the first element of theDequeinstance. These methods don’t remove the value from theDequeinstance. Similarly, the methodsgetLastandpeekLastretrieve the last element. The methodsgetFirstandgetLastthrow an exception if thedequeinstance is empty whereas the methodspeekFirstandpeekLastreturnNULL.

The 12 methods for insertion, removal and retieval of Deque elements are summarized in the following table:

Deque Methods
Type of Operation / First Element (Beginning of theDequeinstance) / Last Element (End of theDequeinstance)
Insert / addFirst(e)
offerFirst(e) / addLast(e)
offerLast(e)
Remove / removeFirst()
pollFirst() / removeLast()
pollLast()
Examine / getFirst()
peekFirst() / getLast()
peekLast()

In addition to these basic methods to insert, remove and examine aDequeinstance, theDequeinterface also has some more predefined methods. One of these isremoveFirstOccurence, this method removes the first occurrence of the specified element if it exists in theDequeinstance. If the element does not exist then theDequeinstance remains unchanged. Another similar method isremoveLastOccurence; this method removes the last occurrence of the specified element in theDequeinstance. The return type of these methods isboolean, and they returntrueif the element exists in theDequeinstance.

[This talk is taken from the Java tutorials. See http://docs.oracle.com/javase/tutorial/collections/interfaces/deque.html for more information]