PUSH and POP on an array-backed stack (CLRS, 1-indexed)
PUSH and POP on an array-backed stack (CLRS, 1-indexed)
Answer
PUSH(S, x): S.top = S.top + 1 S[S.top] = x POP(S): S.top = S.top - 1 return S[S.top + 1]
PUSH increments top then stores; POP decrements then returns the slot just above the new top. Both are O(1) — a stack is among the cheapest structures there is.