Deque

Deque or double-ended queue is almost the same as the queue. But, the main difference is that it provides possibility to add and remove elements from both sides of the queue. In other words it combines FIFO and LIFO principles.

deque

Double-ended queues are not heavily used in practice, but they can be useful in such task, as browser history. Let say, the browser history must contain last 10 visited URL’s. To do that we can add every visited URL to the front of the deque. Once, we are going to add 11th URL we remove URL from the back.

Operations with deque

There are four basic operations:

  1. Push back – adds a new element to the back of the deque.
  2. Push front – adds a new element to the front of the deque.
  3. Pop back – removes element from the back.
  4. Pop front – removes element from the front.
Implementation

The most effective way to implement double-ended queue is using doubly-linked list or array.

Let’s start from doubly-linked list:

https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/LinkedListDeque.java

Array based implementation:

https://github.com/alexvolov/algorithms-and-data-structures/blob/master/src/main/java/com/alexvolov/ads/ds/impl/ArrayDeque.java

Complexity

All deque operations mentioned in this post have O(1) complexity.

Leave a Reply