Stacks

A stack is a linked list in which insertion and deletion are restricted to one end, usually the front. (There are in principle two types of stack, the front stack and the rear stack.)  Stacks are sometimes referred to by other names: push-down list, nesting store, first-in, last-out (FILO) list, and last-in, first-out(LIFO) list.  The stack is a commonly used mechanism in programming languages.

The classic example from the real world is a plate warmer/stacker in a restaurant, where plates are placed on a spring-loaded device so that the height of the top plate in the stack is at a constant height. This is partly a safety measure to prevent plates from piling too high, and also to try and ensure that all of the plates are in the heated zone.

stack

As plates are added then the load on the spring is increased and the top plate stays at a constant height. As plates are removed, the load on the spring is removed and the lower plates move up.

Note that this implementation of a stack satisfies the following conditions:

  • Plates can only be added to the top
  • Plates can only be removed from the top
  • There is no access to any other plate.

In order to provide a computer model of this behaviour, we need to provide operations that mimic the real world behaviour. These are known as stack operations and we’ll look at them later.

Next: Queues