Double Ended Queues

Double ended queues, called deques for short, are a generalized form of the queue. It is exactly like a queue except that elements can be added to or removed from the head or the tail.

In this image, there are currently 3 items in the double ended queue - the extra spaces on the sides are only there to show where new items can go. In a double ended queue, items can be added to or removed from both sides. So, prepending a 4 would result in a 4 appearing to the left of the 6. The head would then be on the 4. On the other hand, appending a 7 would make a 7 appear to the right of the 2. The tail would then be on the 7.

A deque with both a head and a tail

Doubled ended queues can be thought of as a line of people waiting at a restaurant. Like in a queue, people can be helped at the front of the line, and they join the line in the back. However, unlike a queue, two more things can happen. In this line, people at the end of the line can leave early if they're getting impatient, and people can come back to ask for condiments after they've already ordered. So, adding and removing people can happen at both ends of the line.

The double ended queue has six basic operations.

Function Name*	Provided Functionality
append(i)	Adds element i to the tail of the queue
prepend(i)	Adds element i to the head of the queue
delete_last()	Removes the element at the tail of the queue
delete_first()	Removes the element at the head of the queue
examine_last()	Returns the element at the tail of the queue
examine_first()	Returns the element at the head of the queue

*Exact names are not required. In fact, some functionality may be provided by a given language directly via special syntax.

Typically, these operations are implemented with a data structure like the linked list. Linked lists make it very easy to update linear abstract data types. Regardless of the data structure used, it is essential that references to the head and tail of the deque are constantly kept so that each operation can be performed.

Deque Questions

Consider a line of people being helped at a restaurant. The head of the line is in front. The tail of the line is in the back.

1. What double ended queue operation can describe someone leaving the end of the line out of impatience? What operation describes someone coming back for condiments to the front?

2. How are double ended queues different from regular queues?

Show Answer

A1. The delete_last function. The prepend function.

A2. With double ended queues, you are able to remove and add items from both the front and the back of the queue. In a queue, you can only add data to the back and remove it from the front.

The data structure list in Python is capable to implement a double ended queue, although inefficiently:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Deque:
    def __init__(self):
        self.queue = []
    def append(self, i):
        self.queue.append(i)
    def prepend(self, i):
        self.queue.insert(0, i)
    def delete_last(self):
        if len(self.qlist) == 0:
            return "Deque is empty"
        self.qlist.pop(-1)
    def delete_first(self):
        if len(self.qlist) == 0:
            return "Deque is empty"
        self.qlist.pop(0) 
    def examine_last(self):
        if len(self.qlist) == 0:
            return "Deque is empty"
        return self.qlist[-1]
    def examine_first(self):
        if len(self.qlist) == 0:
            return "Deque is empty"
        return self.qlist[0]

Let's look at this implementation in action.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

>>> dbl = Deque()
>>> dbl.append(3)
>>> dbl.queue
[3]
>>> dbl.append(2)
>>> dbl.queue
[3, 2]
>>> dbl.prepend(1)
>>> dbl.queue
[1, 3, 2]
>>> dbl.delete_last()
>>> dbl.queue
[1, 3]
>>> dbl.delete_first()
>>> dbl.queue
[3]
>>> dbl.examine_first()
3

The time complexity of deques depends on the type of the data structure used and the specific implementation built. Below is the complexity analysis for doubly linked lists and dynamic arrays:

For the array, you can still think about the dequeue like a line. If you get rid of the first person in line, then you have to move everyone forward, so the runtime is O(n). However, if you get rid of the last person in line - maybe they just leave the line - then you don't have to move anyone else. So, that runtime is O(1). The same logic goes for adding people to that line.

In the linked list implementation, everything is constant time. This is because, for any operation, all you have to do is modify the pointers to the element in question and to is neighbors. Linked list implementations will often have pointers to the tail of the deque. This makes the linked list implementation extremely fast.

Deques are useful in many different scenarios because they display the principles of both a stack and a queue. One example is in distributed computing and scheduling. If you have many computers trying to finish various jobs, each computer first starts by taking off the first job on their own list. If that job is completed, it is discarded, but if it is interrupted, it is pushed back to the front of their list. Then, if a single computer finished their list, they can take the last element off of another computer's list.

Another important application of queues is in networking. Like with queues, network data is processed in dequeus in a first come, first serve way. However, if a certain data packet has waited too long, then it can choose to leave and try somewhere different. In this way, the deque functionality of removing from both ends is very useful.