Deque
Aka double-ended queue, it allows for insertion and removal from front or back of the collection.
| Pros | Cons |
|---|---|
| Provides more flexibility than a queue | Depending on implementation, it will share the same cons as a dynamic array or a linked list |
Implementations
C++: deque
std::deque<int> d = {1, 2, 3};
d.push_back(4); // {1, 2, 3, 4}
d.push_front(0); // {0, 1, 2, 3, 4}d.pop_back(); // {0, 1, 2, 3}
d.pop_front(); // {1, 2, 3, 4}
Python: deque
d = deque([1, 2, 3]) # [1, 2, 3]
d.append(4) # [1, 2, 3, 4]
d.appendLeft(0) # [0, 1, 2, 3, 4]d.pop() # [0, 1, 2, 3]
d.popLeft() # [1, 2, 3]
Java: Deque
Deque<Integer> d = new LinkedList<>();
d.addFirst(2); // {2}
d.addLast(3); // {2, 3}
d.addFirst(1); // {1, 2, 3}
d.addFirst(0); // {0, 1, 2, 3}
d.addLast(4); // {0, 1, 2, 3, 4}d.removeLast(); // {0, 1, 2, 3}
d.removeFirst(); // {1, 2, 3}
| Operations | Worst | Average |
|---|---|---|
| Delete (Beginning) | O(1) | O(1) |
| Delete (End) | O(1) | O(1) |
| Insert (Beginning) | O(1) | O(1) |
| Insert (End) | O(1) | O(1) |
