Deque Implementation

Most languages have built-in deques:

• C++: deque<T> with push_front, push_back, pop_front, pop_back
• Python: collections.deque with appendleft, append, popleft, pop
• Java: ArrayDeque or LinkedList implementing Deque interface

Never implement a deque from scratch in contests.

Use the standard library. Focus on the algorithm. Time: $O(1)$. Space: $O(n)$.