How is a stack implemented with a fixed-size array?

Elements fill the array from left to right, and a variable t holds the index of the top element (−1 when empty); push increments t and writes S[t], pop decrements t and returns the element that was at the old top, and size() is t + 1.

* pop only moves t back; the old value stays in the cell and is simply ignored. *

Algorithm size()
  return t + 1

Algorithm push(o)
  if t = S.length − 1 then
    throw IllegalStateException     { array is full }
  else
    t ← t + 1
    S[t] ← o

Algorithm pop()
  if isEmpty() then
    return null
  else
    t ← t − 1
    return S[t + 1]

The single index t is the whole bookkeeping. The stack occupies S[0..t], the top is S[t], and everything to the right is free. Pushing and popping at the right end is what makes it cheap: nothing ever shifts.

Note the order inside pop: t is decremented first, so the element to return is at the old position, S[t + 1]. The value is not erased from the array. It is simply outside the stack now and will be overwritten by the next push.

Go deeper:

• Stack visualisation, array-based (USF) — watch t and the cells change with each push and pop.