A deque lets you add/remove items at both the front and the back in amortized O(1) time.
How it works (array-backed circular buffer): we keep two indices, head (first element) and tail (one past the last element). The elements logically occupy size contiguous positions in a circular index space. When we push_front, we decrement the head index modulo capacity and write there; for push_back, we write at tail and then increment tail modulo capacity. Pops adjust the corresponding index in the opposite direction. We shift the indices, not the elements—so no O(n) moves. If the buffer is full and resizing is enabled, we allocate a larger array and copy the size items once, re-laying them out from index 0..size-1.
Real-life intuition: a line where VIPs can enter at the front, a work queue that prioritizes urgent tasks, or sliding-window algorithms that push/pop from both ends.
We store elements in a fixed-size array and track three values:
head (index of the front element), tail (index one past the back element),
and size (number of elements). The array is treated circularly, so when an index reaches
the end it wraps to 0 using modulo arithmetic.
Invariant: tail = (head + size) mod capacity
push_back(x): write to A[tail], then tail ← (tail + 1) mod C, size++.push_front(x): head ← (head − 1 + C) mod C, write to A[head], size++.pop_front(): read/clear A[head], then head ← (head + 1) mod C, size--.pop_back(): tail ← (tail − 1 + C) mod C, read/clear A[tail], size--.front()/back() read ends in O(1).
No bulk shifting is needed; only head/tail move. That’s why end operations stay O(1).
size == 0, full ⇔ size == capacity.head == tail, full ⇔ (tail + 1) mod C == head.
When full, we can double capacity: allocate a larger array, copy the size items in logical order
to indices 0..size−1, then set head = 0 and tail = size. A single push may cost O(n),
but over many pushes the cost is still amortized O(1).
push_front(x), push_back(x)pop_front(), pop_back()peek_front(), peek_back()isEmpty(), size()| Operation | Array/Circular-buffer deque | Linked-list deque | Notes |
|---|---|---|---|
push_front(x) | Amortized O(1) | O(1) | Array may occasionally resize; circular indices |
push_back(x) | Amortized O(1) | O(1) | Same as above |
pop_front() | O(1) | O(1) | Advance head |
pop_back() | O(1) | O(1) | Retreat tail |
front()/back() | O(1) | O(1) | Read ends |
isEmpty()/size() | O(1) | O(1) | Maintain a count |
collections.deque (standard library)from collections import deque dq = deque() dq.append(10) # push_back dq.appendleft(5) # push_front x = dq.pop() # pop_back y = dq.popleft() # pop_front f, b = dq[0], dq[-1] # front, back n = len(dq)
class ArrayDeque:
def __init__(self, capacity=8):
self._a = [None]*capacity
self._cap = capacity
self._head = 0; self._tail = 0; self._size = 0
def _grow(self):
b = [None]*(self._cap*2)
for i in range(self._size):
b[i] = self._a[(self._head + i) % self._cap]
self._a, self._cap = b, self._cap*2
self._head, self._tail = 0, self._size
def push_back(self, x):
if self._size == self._cap: self._grow()
self._a[self._tail] = x
self._tail = (self._tail + 1) % self._cap
self._size += 1
def push_front(self, x):
if self._size == self._cap: self._grow()
self._head = (self._head - 1 + self._cap) % self._cap
self._a[self._head] = x
self._size += 1
def pop_front(self):
if self._size == 0: raise IndexError("empty")
v = self._a[self._head]; self._a[self._head] = None
self._head = (self._head + 1) % self._cap
self._size -= 1; return v
def pop_back(self):
if self._size == 0: raise IndexError("empty")
self._tail = (self._tail - 1 + self._cap) % self._cap
v = self._a[self._tail]; self._a[self._tail] = None
self._size -= 1; return v
def front(self):
if self._size == 0: raise IndexError("empty")
return self._a[self._head]
def back(self):
if self._size == 0: raise IndexError("empty")
return self._a[(self._tail - 1 + self._cap) % self._cap]
def isEmpty(self): return self._size == 0
def size(self): return self._size
ArrayDeque (standard library)import java.util.ArrayDeque; import java.util.Deque; Deque<Integer> dq = new ArrayDeque<>(); dq.addLast(10); // push_back dq.addFirst(5); // push_front int x = dq.removeLast(); // pop_back int y = dq.removeFirst(); // pop_front int f = dq.getFirst(); // front int b = dq.getLast(); // back int n = dq.size();
public class LinkedDeque<T> {
private static class Node<T>{ T v; Node<T> p,n; Node(T v){this.v=v;} }
private Node<T> head, tail; private int size;
public void pushFront(T x){ Node<T> a=new Node<>(x);
if(head==null){ head=tail=a; } else { a.n=head; head.p=a; head=a; } size++; }
public void pushBack(T x){ Node<T> a=new Node<>(x);
if(tail==null){ head=tail=a; } else { a.p=tail; tail.n=a; tail=a; } size++; }
public T popFront(){ if(size==0) throw new java.util.NoSuchElementException();
T v=head.v; head=head.n; if(head!=null) head.p=null; else tail=null; size--; return v; }
public T popBack(){ if(size==0) throw new java.util.NoSuchElementException();
T v=tail.v; tail=tail.p; if(tail!=null) tail.n=null; else head=null; size--; return v; }
public T front(){ if(size==0) throw new java.util.NoSuchElementException(); return head.v; }
public T back(){ if(size==0) throw new java.util.NoSuchElementException(); return tail.v; }
public int size(){ return size; } public boolean isEmpty(){ return size==0; }
}
std::deque (standard library)#include <deque>
#include <iostream>
int main(){
std::deque<int> dq;
dq.push_back(10); dq.push_front(5);
std::cout << dq.front() << " " << dq.back() << "\n";
dq.pop_front(); dq.pop_back();
}
#include <vector>
#include <stdexcept>
template<typename T> class ArrayDeque {
std::vector<T> a; size_t head=0, tail=0, cnt=0;
public:
explicit ArrayDeque(size_t cap=8): a(cap) {}
size_t capacity() const { return a.size(); }
size_t size() const { return cnt; }
bool empty() const { return cnt==0; }
void grow(){ std::vector<T> b(a.size()*2);
for(size_t i=0;i<cnt;i++) b[i]=a[(head+i)%a.size()];
a.swap(b); head=0; tail=cnt; }
void push_back(const T& x){ if(cnt==a.size()) grow(); a[tail]=x; tail=(tail+1)%a.size(); ++cnt; }
void push_front(const T& x){ if(cnt==a.size()) grow(); head=(head-1+a.size())%a.size(); a[head]=x; ++cnt; }
T pop_front(){ if(!cnt) throw std::runtime_error("empty"); T v=a[head]; head=(head+1)%a.size(); --cnt; return v; }
T pop_back(){ if(!cnt) throw std::runtime_error("empty"); tail=(tail-1+a.size())%a.size(); T v=a[tail]; --cnt; return v; }
const T& front() const { if(!cnt) throw std::runtime_error("empty"); return a[head]; }
const T& back() const { if(!cnt) throw std::runtime_error("empty"); return a[(tail-1+a.size())%a.size()]; }
};
C, why does tail = (head + size) mod C always hold?head and tail start in the middle? Why or why not?C = 8, head = 6, tail = 2, what is size?size? (Hint: sentinel gap or version bit.)