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.