← DSA I

Double-ended execution laboratory

Deque Lab

0/6 traced

Push Back

Add an element to the back of the deque.

worst case O(1) time O(1) space
1struct Deque {
2 int* arr;
3 int front;
4 int rear;
5 int size;
6 int capacity;
7};
8
9void push_back(Deque& q, int val) {
10 if (q.size == q.capacity) return;
11 // Resize logic if dynamic
12 q.arr[q.rear] = val;
13 q.rear = (q.rear + 1) % q.capacity;
14 q.size++;
15}
front index0
rear index3
size3
capacity5
indexingmod capacity

Circular buffer · both ends move modulo capacity, so neither end ever shifts.

0 10 F
1 20
2 30 B
3 ·
4 ·
FrontBack Free slotRead / write this line Deleted
Exact work through this line 1 +1 on this line
O(1) time O(1) auxiliary space 0 peak reported values
1comparisons
0reads
0writes
0pointer reads
0pointer writes
0swaps
0allocations
0deallocations
0node visits
0iterations
0calls
0returns
Variables before line

size3

capacity5

readIndexnull

writeIndexnull

headnull

tailnull

currentnull

newNodenull

resultnull

nodes

slots[0]=10 · [1]=20 · [2]=30 · [3]=· · [4]=·

Variables after line

size3

capacity5

readIndexnull

writeIndexnull

headnull

tailnull

currentnull

newNodenull

resultnull

nodes

slots[0]=10 · [1]=20 · [2]=30 · [3]=· · [4]=·

Reads, writes, and state changes on this line

operation-count.value 0 → 1 highlight

Why this bound?

O(1) time · O(1) space

worst
fixed readfixed writeInput may grow; this fixed-width work does not → 1
Auxiliary memory model
cursortemporarycounter

A bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.

  1. A deque touches only the front or rear index and updates size — modular arithmetic, no shifting.
  2. The number of operations does not depend on how many elements the deque holds.
  3. 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.
Step 1 of 4 · check-full Check capacity

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.

1 / 4