← DSA I

Stack execution laboratory

Stack Lab

0/4 traced

Push

Add an element to the top of the stack.

worst case O(1) time O(1) space
1void push(Stack& s, int value) {
2 if (s.size == s.capacity) return;
3 // Resize logic if dynamic
4 s.slots[s.size] = value;
5 s.size++;
6}
top index2
size3
capacity5
readIndexnull
writeIndexnull

Buffer · pushes and pops happen at the top

4 ·
3 ·
2 30 ← top
1 20
0 10
TopIn stack SpareRead / 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

oldCapacitynull

inull

readIndexnull

writeIndexnull

headnull

currentnull

newNodenull

resultnull

resultIndexnull

nodes

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

Variables after line

size3

capacity5

oldCapacitynull

inull

readIndexnull

writeIndexnull

headnull

currentnull

newNodenull

resultnull

resultIndexnull

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. Push writes into slot size (array) or relinks head (list) — a fixed number of operations.
  2. Nothing depends on how many elements are already on the stack.
  3. A bounded primitive count is O(1) time and O(1) auxiliary space.
Assumptions behind this claim
  • Stack is not full
  • Each displayed read, write, comparison, allocation, or copy is one counted primitive.
  • Trace construction and visualization bookkeeping are excluded from the algorithm count.
Step 1 of 3 · push-check Check capacity

size is below capacity, so there is a free slot at index size.

About this implementation

A stack is LIFO: push and pop touch only the top. A fixed array overflows when full; a dynamic array doubles (one push becomes O(n), but amortized O(1)); a linked stack never resizes. Search is O(n) because only the top is directly reachable.

1 / 3