Abstract Data Type

Deque

Deque stands for a “double-ended queue”. It is an Abstract Data Type that generalizes a Queue, for which elements can be added to or removed from either the front or back.

→ Think the power of Stacks and Stacks and Queues combined

Implementation

The built-in deque implementation is actually a little complicated, I don’t understand it yet.

Think of it like a Circular buffer of objects

The STL use a circular buffer of Pointers.

Python collections.deque

We use the deque library to implement Stacks and Queues in Python. Check out documentation for functions.

→ Deque $O(1)$ is preferred over list $O(n)$ for the time complexity advantages on append and pop operations.

from collections import deque
d = collections.deque()
 
# Adding Elements
d.append(4) 
d.appendleft(6)
# Removing Elements
d.pop()
d.popleft()
 
d[-1] # last element
d[0] # first element
len(d) == 0 # isEmpty
 

C++ Deque

Dynamic array in C++ that extends upon the C++ Vector by also including push_front and pop_front. Check reference.

deque<int> d;
//Adding Elements
d.push_back(5); // [5]
d.push_back(2); // [5,2]
d.push_back(3); // [5,2,3]
d.push_front() // this also exists
//Check elements
d.front() // 5
d.back() // 3
//Removing elements
d.pop_front(); // [2,3]
d.pop_back(); // [2]