Push
Add an element to the top of the stack.
1void push(Stack& s, int value) {2if (s.size == s.capacity) return;3// Resize logic if dynamic4s.slots[s.size] = value;5s.size++;6}
235nullnullBuffer · pushes and pops happen at the top
size3
capacity5
oldCapacitynull
inull
readIndexnull
writeIndexnull
headnull
currentnull
newNodenull
resultnull
resultIndexnull
nodes
slots[0]=10 · [1]=20 · [2]=30 · [3]=· · [4]=·
size3
capacity5
oldCapacitynull
inull
readIndexnull
writeIndexnull
headnull
currentnull
newNodenull
resultnull
resultIndexnull
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.
- Push writes into slot size (array) or relinks head (list) — a fixed number of operations.
- Nothing depends on how many elements are already on the stack.
- 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.
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.