Deque

push · pop both ends O(1)

A deque (double-ended queue) is a queue open at both ends: you can push and pop at the front and at the back, each in constant time. It generalises both the stack and the queue, and is handy for sliding-window algorithms and work-stealing schedulers.

Deque
Press ▶ to run
Edit the input and press Play

How it works

  1. pushFront / pushBack add a value at the front or the back.
  2. popFront / popBack remove a value from the front or the back.
  3. Use one end like a stack, both ends like a queue — whatever the algorithm needs.

Pseudocode

1pushFront(v):  items.prepend(v)            # O(1)2pushBack(v):   items.append(v)             # O(1)34popFront():    return items.removeFirst()  # O(1)5popBack():     return items.removeLast()   # O(1)