Originally published on August 6, 2022 at https://rivea0.github.io/blog
Two of the abstract data types that you are most likely to have encountered before are stacks and queues. One important aspect is that each of them has different principles when it comes to their behavior when inserting and removing elements — LIFO (last in, first out) for stacks, FIFO (first in, first out) for queues. With a stack, the last item inserted is the first to go out, so, we push and pop from one end of the stack. With a queue, the first item inserted is going to be removed first, similar to a queue in real life, so, enqueue and dequeue operations are done from the opposite ends of the queue.
With a "double-ended queue", or a deque—pronounced as "deck"—, we can enqueue or dequeue, or, push and pop items from both ends at any time. Implemented as a doubly-linked list under the hood, insertion and deletion operations will take O(1), constant time. This is also another reason why a deque is great — you can imagine that we can also use a Python list for the same goal, but in that case, if we want to insert and remove from the beginning (say, from the left end), the operation will take O(n) time, which is, well, not so good.
Let's take a look at it. Using a list, you might have seen a stack as implemented as such*:
class Stack:
"""Stack implementation as a list."""
def __init__(self):
"""Create new stack."""
self._items = []
def is_empty(self):
"""Check if the stack is empty."""
return not bool(self._items)
def push(self, item):
"""Add an item to the stack."""
self._items.append(item)
def pop(self):
"""Remove an item from the stack."""
return self._items.pop()
def peek(self):
"""Get the value of the top item in the stack."""
return self._items[-1]
def size(self):
"""Get the number of items in the stack."""
return len(self._items)
And, a queue like this:
class Queue:
"""Queue implementation as a list."""
def __init__(self):
"""Create new queue."""
self._items = []
def is_empty(self):
"""Check if the queue is empty."""
return not bool(self._items)
def enqueue(self, item):
"""Add an item to the queue."""
self._items.insert(0, item)
def dequeue(self):
"""Remove an item from the queue."""
return self._items.pop()
def size(self):
"""Get the number of items in the queue."""
return len(self._items)
Since we want to use a deque here instead of a list, let's take a simple look at it.
We can initialize a deque object with optionally passing an iterable as argument. It is in the collections module, so we also have to import it:
from collections import deque
d = deque([7, 3, 0, 1])
print(d) # deque([7, 3, 0, 1])
empty_d = deque()
print(empty_d) # deque([])
Also, remember that strings are sequences, in that case, our deque would look like this:
d = deque('hey')
print(d) # deque(['h', 'e', 'y'])
We can also provide a maxlen argument to specify the maximum length of items we want our deque to have — to make it bounded.
This is a trivial example, but let's get a sense of how it is working:
from collections import deque
d = deque([4, 5, 3, 1, 8], maxlen=3)
print(d) # deque([3, 1, 8], maxlen=3)
d = deque([4, 5, 3, 1, 8], maxlen=4)
print(d) # deque([5, 3, 1, 8], maxlen=4)
As the items in the iterable are appended from one end, removing the other items (in the case of maxlen=3 example, 4 and 5) will be from the opposite end.
Of course, the efficiency of a deque also comes from its appendleft() and popleft() methods, which are aptly named, and better than a list in terms of time complexity.
from collections import deque
d = deque([7, 11])
d.appendleft(3)
print(d) # deque([3, 7, 11])
d.appendleft(1)
print(d) # deque([1, 3, 7, 11])
first_i = d.popleft()
print(first_i) # 1
print(d) # deque([3, 7, 11])
We also have the append() and pop() methods which do their operations to/from the right — like a regular list:
from collections import deque
d = deque([2, 4, 6])
d.append(8)
print(d) # deque([2, 4, 6, 8])
first_popped = d.pop()
second_popped = d.pop()
print(f'Popped {first_popped} first, then {second_popped} second.')
# -> Popped 8 first, then 6 second.
print(d) # deque([2, 4])
Now that we have seen the append and pop operations from both sides, let's implement a queue first, similar to the list version at the beginning of the article:
from collections import deque
class Queue:
"""Queue implementation as a deque."""
def __init__(self):
"""Create new queue."""
self._items = deque()
def is_empty(self):
"""Check if the queue is empty."""
return not bool(self._items)
def enqueue(self, item):
"""Add an item to the queue."""
self._items.append(item)
def dequeue(self):
"""Remove an item from the queue."""
return self._items.popleft()
def size(self):
"""Get the number of items in the queue."""
return len(self._items)
For the stack version, as we need to append and pop from the same end, append() and pop() methods using a list might seem okay at first, too. But, let's modify the previous stack version above to implement it as a deque:
from collections import deque
class Stack:
"""Stack implementation as a deque."""
def __init__(self):
"""Create new stack."""
self._items = deque()
def is_empty(self):
"""Check if the stack is empty."""
return not bool(self._items)
def push(self, item):
"""Add an item to the stack."""
self._items.append(item)
def pop(self):
"""Remove an item from the stack."""
return self._items.pop()
def peek(self):
"""Get the value of the top item in the stack."""
return self._items[-1]
Nothing much seems different, but you can also imagine using the other end, using appendleft() together with popleft() as well.
We have explored a very simple way to create stacks and queues using a deque, but of course, there is a lot more to dive into. The official documentation is the first place to go, and you can also check out a Real Python article on the subject. As with many things, it is up to you what you want to achieve, and a double-ended queue is just another tool in your toolkit to consider.
* The examples of stack and queue implementations as a list are from Brad Miller and David Ranum's wonderful book on algorithms and data structures.
Top comments (0)