A stack is a data structure which stores items in sequence, providing access at only one end. That is, we add items at the top of the stack, and we remove items from the top of the stack.

Notice that the items are thus available in reverse order. Stacks are sometimes referred to as "Last In, First Out" (LIFO) or "First In, Last Out" (FILO) structures.

The idea of a stack is easy to visualize. Imagine a set of plates in a kitchen, arranged one on top of another. When someone wants a plate, he or she takes one from the top, and when someone washes and dries a plate, the plate is put back on top of the other plates. (This is why the plates get uneven wear and tear.)

The data stored in a stack may be of various kinds: integers, characters, strings, floating-point numbers, structs, etc., or pointers to items stored elsewhere. If we use the idea of a template class, we can create a stack which works for various types of data. (See the web page on "template functions and classes".)

Stack operations

Suppose we have a stack of integers. The operations normally provided for a stack are the following:

• Initialize

  Create a new stack.

• Dispose

  Get rid of a stack.

• Push

  Insert an int at the top of the stack.

• Pop

  Remove an int from the top of the stack.

• Peek

  Look at the int at the top of the stack.

• Empty

  Return true if the stack is empty and false otherwise.

• Full

  Return true if the stack is full and false otherwise.

Optionally, we may also have a counter of the number of items in the stack; the counter would be incremented and decremented as needed by the Push and Pop operations. If we have a counter, we probably also have a function to give us the value of the counter.

Normally, the user will check the Empty function before attempting to use the Pop operation, and likewise check the Full function before attempting to use the Push operation. (If we pop an empty stack or push an item onto a full stack, this is an error.)

The user does not need to know how the stack is implemented; he or she simply uses the stack operations, that is, the public interface.

How is a stack implemented?

A stack may be implemented in various ways:

• a fixed-size array
• a dynamically-sized array
• a linked list with a Head pointer

Depending on the choice, some operations may be slower or faster, or may use more or less memory.

We will usually implement the stack as a class, so the Initialize and Dispose operations will correspond to the constructor and destructor.

If we use a linked list or a dynamically-sized array, the Full function may simply always return false, as we can always enlarge the stack (as long as we do not run out of memory).