Double-Ended Queue (Deque)

Introduction to the deque

The double-ended queue, or deque (pronounced “deck”) is a linear collection of elements that supports the insertion and removal of elements at both endpoints and that is the main advantage of the deque. For that reason, the Deque interface is considered to be a richer abstract data type than both stack and queue. Naturally, it implements both stack and queue simultaneously.

In Java, ArrayDeque is one of the general-purpose implementations of a class, similar to the LinkedList class. Both are comparable in terms of efficient operations and flexibility, and we’ll learn more about that in a bit.

Before that, we’ll quickly go through Python code, creating a deque. We’ve seen examples of queues and the ordered collection of items. We have the ordered collection in the deque, which has two ends—a front and a rear. One characteristic that has made this interface unique is that there’s no restriction in adding and removing items. New items can be added either at the front or at the rear.

In the same way, we can remove any item from the front or from the end. In a sense, this hybrid linear data structure provides all the capabilities of stacks and queues under one roof.

Although it combines stacks and queues, it never assumes the LIFO or FIFO orderings that stacks and queues usually possess.

In the following Python ...