How Does Deque Work in Python

Question

I am having trouble understanding how the deque works in the snippet of code below, while trying to recreate a queue and a stack in Python.

Stack Example - Understood

stack = ["a", "b", "c"]

# push operation
stack.append("e")
print(stack)

# pop operation
stack.pop()
print(stack)

As expected when pushing and popping, the "e" goes Last In, First Out (LIFO). My question is with the example below.

Queue Example - Not Understanding

from collections import deque

dq = deque(['a','b','c'])
print(dq)

# push
dq.append('e')
print(dq)

# pop
dq.pop()
print(dq)

When pushing and popping, the "e" goes Last In, First Out (LIFO). Shouldn't it be First In, First Out (FIFO)?

Mortensen

You should check out the deque documentation. You might be looking for dq.popleft() (or .appendleft()). In either case, the "de" in dequeue stands for "double-ended". – Joe

Why should it be any different? – Malaguena

Answer 1

A deque is a generalization of stack and a queue (It is short for "double-ended queue").

Thus, the pop() operation still causes it to act like a stack, just as it would have as a list. To make it act like a queue, use the popleft() command. Deques are made to support both behaviors, and this way the pop() function is consistent across data structures. In order to make the deque act like a queue, you must use the functions that correspond to queues. So, replace pop() with popleft() in your second example, and you should see the FIFO behavior that you expect.

Deques also support a max length, which means when you add objects to the deque greater than the maxlength, it will "drop" a number of objects off the opposite end to maintain its max size.

Aeromancy

Answer 2

I'll add my two cents as I was searching for this exact question but more from the time complexity involved and what should be the preferred choice for a queue implementation in Python.

As per the docs:

Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

This means you can use dequeues as a stack(Last in First out) and queue(First in First out) implementation with pop() or popleft() operation in O(1).

Again from docs

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

However, using the list as a queue requires popping from the 0th index which will cause data to be shifted resulting in O(N) operation. So if you want to use a queue for a time sensitive operation (production code or competitive programming) always use dequeue for queue implementation.

Biscuit