What is a double-ended queue (deque)?

A double-ended queue (deque) is a data structure in which elements can be added and removed from both sides: from the front and from the back.

#Main operations

• addFront(x): add an element to the front,
• addRear(x): add an element to the back,
• removeFront(): remove an element from the front,
• removeRear(): remove an element from the back,
• peekFront() and peekRear(): look at the elements without removing them.

#Difference from a regular queue

In a regular queue, additions happen only at the back, and removals only at the front. In a deque, both sides are equal.

#Uses

• implementing a stack and a queue in a single object,
• "window" problems (for example, the maximum in a sliding window),
• caching (LRU algorithms),
• symmetric data processing, where you need to work quickly with both ends.

All main deque operations run in O(1).