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.
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.
Minimal Required Functionalities
The double ended queue has six basic operations.
Function Name* Provided Functionality
Adds element i to the tail of the queue
Adds element i to the head of the queue
Removes the element at the tail of the queue
Removes the element at the head of the queue
Returns the element at the tail of the queue
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.
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.
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?
How are double ended queues different from regular queues?A1. The
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.
Sample Python Implementation Using a List
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
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
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:
|Operation||Doubly Linked List||Dynamic Array|
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.
There are two typical ways to implement a double-ended queue, using dynamic arrays and using linked lists. In general, it may seem as though using a linked list is a no-brainer because of the increased speed in many of the essential double-ended queue operations. However, there is one specific area where using a dynamic array is useful.
Which of the following operations will be significantly easier if you implement a double-ended queue using a dynamic array as opposed to a linked list?
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.