## Stacks

### External interface

- Create (stack S)

- stacktype Top (stack S)

- stacktype Pop (stack S)

- Push (stacktype item, stack S)

- boolean Empty (stack S)

### Implementations

Stacks are a limited form of lists (where all insert and delete operations
take place at one end, called the top of the stack),
so all implementations for lists apply.

- Implement stack in terms of list operations.
- Avoid O(N) Insert operations in array implementation!

- Use array implementation, with top of stack at the end of the
array, and the stack grows downward.
- Push and Pop are O(1)
- Limits maximum size of stack