Stack operations

A stack is last in, first out: you only ever push onto the top, look at the top, or pop the top. On an array that's one index, top — push moves it right and writes, pop just moves it left. Every operation is O(1).

The stack has its bottom on the left; push and pop happen at the top, on the right. arr is the array behind it: arr[0..top] is the stack, and slots past top are free.