A double-ended queue, or Deque, is a linear collection of data that takes the concept of Queue into a step further. Deque is very similar to Queue, however, it complements Queue with some more useful operations. Deque allows adding items to both ends and removing items from both ends as well. This behavior enables functioning as Deque and Stack simultaneously.
Deque provides four main operations — offerFirst(), offerLast(), pollFirst() and pollLast(). The operations — offerFirst() and offerLast() add a new item to the head, or beginning of the storage, in our case — storage = list, and the tail or end of the list respectively; pollFirst() and pollLast() remove the head, or the beginning of the list, and the tail, or the end of the list, respectively. Time complexities of operations are as follows:
OfferFirst — O(1)
OfferLast — O(1)
PollFirst — O(1)
PollLast — O(1)
As deque is linearly structured, its inner storage can be implemented using Array or DoublyLinkedList. Since DoublyLinkedLists provide more efficient operations of adding to and removing items from the both ends, it is preferable to use DoublyLinkedLists. Why is DoublyLinkedList preferred over Array? — Leave your answers in comments.
Let’s discuss all the operations one by one.
OfferFirst(item) — another name for an adding operation. Adding a new item is possible only to one position — to the head of the storage, or beginning. A newly added item becomes the head. For more clarity — see the above illustration.
OfferLast(item) — another adding operation provided by Deque. OfferLast — enables adding only to the tail or beginning. A newly added item becomes the tail. OfferLast is the same as Enqueue provided by Queue. For more clarity — see the above illustration.
PollFirst() — another name for removal operation. PollFirst enables removing the first item from the storage — head. If only offerFirst() and pollFirst() are applied, the Deque functions in the same way as Stack does. For more clarity — see the above illustration.
PollLast — the other operation of removal. PollLast enables removing item only from the tail or the end. For clarity — see the above illustration.
As we have discussed, deque is pretty straightforward and a combination of Stack and Queue. Deque has found its application in Work Stealing Algorithm.
Work Stealing Algorithm implements task scheduling for several processors. A separate deque with threads to be executed is maintained for each processor. To execute the next thread, the processor gets the first element from the deque (using the “pollFirst”). If the current thread forks, it is put back to the front of the deque (“offerFirst”) and a new thread is executed. When one of the processors finishes execution of its own threads (i.e. its deque is empty), it can “steal” a thread from another processor: it gets the last element from the deque of another processor (“offerLast”) and executes it. The work stealing algorithm is used by Intel’s Threading Building Blocks (TBB) library for parallel programming.
The next awaiting topic is OrderedList — a data structure used in specific cases.
If you are curious to dive deeper and play around with the Deque, I recommend to implement the discussed operations by yourself and test.
The following are the links for:
