Deques

What are Deques?

Deques are another very fundamental type of data structure. They are the same as Queues, except they are double-ended, meaning that you can add to the front and start of the Queue and remove from both the start and the end, making them possible alternatives to Queues.

Deque Implementation

In Python, we actually have a built-in module called collections that comes with a deque class. We can use this class to represent a Deque. As an example, type the following code into your file:

from collections import deque

d = deque()
    

In this example, we create an empty Deque using the deque class. We could've also passed in a list for the Deque to initialize from. We first import it from the collectins module and then we assign an empty Deque to the variable d.

Then, type the following code into your program:

d.append(5)
d.append("hi")
d.appendleft("more stuff")
print(d)
    

After running the code, you'll get
deque(['more stuff', 5, 'hi'])
printed out into the terinal.

Appending Left and Right

With Deques, we can do the same operations (adding and removing) as we can with a Queue, but we are able to add and pop from both sides of the Deque. As we already know, by adding to a Deque, it goes to the end. However, we can use another method on the Deque, called appendleft, to append to the left side of the Deque. Just using the bare append method appends the item to the right side of the Deque.

d.append("item goes to the right")
d.appendleft("item goes to the left")
    

Dequeuing Items

Also, similarily with Queues, we can also remove items. Because of the double-ended property of a Deque, we can remove items from both sides of the Deque. But, obviously, we won't be able to access items in the middle of the Deque.

With the deque class, we use the pop and popleft methods on the deque objects to do this.

from collections import deque
d = deque([1, 2, 3, 4])
print(d.pop())
print(d.popleft())
print(d)
    

The output of this code is:

4
1
deque([2, 3])

Deques in Competition

In a programming competition, Deques can be used whenever Queues are needed or used because Deques are the exact same as Queues, just double-ended.