Push Back
Add an element to the back of the deque.
1struct Deque {2int* arr;3int front;4int rear;5int size;6int capacity;7};89void push_back(Deque& q, int val) {10if (q.size == q.capacity) return;11// Resize logic if dynamic12q.arr[q.rear] = val;13q.rear = (q.rear + 1) % q.capacity;14q.size++;15}
0335mod capacityCircular buffer · both ends move modulo capacity, so neither end ever shifts.
size3
capacity5
readIndexnull
writeIndexnull
headnull
tailnull
currentnull
newNodenull
resultnull
nodes
slots[0]=10 · [1]=20 · [2]=30 · [3]=· · [4]=·
size3
capacity5
readIndexnull
writeIndexnull
headnull
tailnull
currentnull
newNodenull
resultnull
nodes
slots[0]=10 · [1]=20 · [2]=30 · [3]=· · [4]=·
operation-count.value 0 → 1 highlight
O(1) time · O(1) space
worstA bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.
- A deque touches only the front or rear index and updates size — modular arithmetic, no shifting.
- The number of operations does not depend on how many elements the deque holds.
- A bounded primitive count is O(1) time and O(1) auxiliary space.
Assumptions behind this claim
- Deque is not full (array)
- Each displayed read, write, comparison, allocation, or pointer update is one counted primitive.
- Trace construction and visualization bookkeeping are excluded from the algorithm count.
Verify deque is not full
About this implementation
A deque supports O(1) insertion and removal at both ends. A circular array moves front and back indices modulo capacity so neither end ever shifts; a doubly linked list relinks prev/next pointers at the chosen end. Peeks read an end without changing size.