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