• Stacks are very straightforward
• Stacks be implemented in a number of different ways
• So, they are a good ADT to start with

• When you add a piece of paper to the box it gets put on the top
• The only piece of paper that can be removed is the top sheet (last-in-first-out or LIFO)

Stack

Values:	Homogeneous elements of any type.
Operations:	Name/Operator Arguments Returns Constructor A new instance. isEmpty true if the stack is empty and false o/w pop The element on the top of the stack push element The element to add to the top of the stack

In addition, if the stack has a "size limit", one could add an isFull() operation; some people add a peek() operation; and some people add a makeEmpty() operation.

• Approach:
  • Store elements in the array, starting at index 0
  • Keep track of the number of elements on the stack
• An Example:
  • Push on a 1:

    1

    .

    .

  • Push on a 2:

    1

    2

    .

Code for this Implementation

cppexamples/arraystack/Stack.h cppexamples/arraystack/Stack.cpp cppexamples/arraystack/Example.cpp

• How could we change pop() to make it return a bool indicating the status but still have it "return" the top item?
• Which methods should be declared const?
• How could we make this implementation "generic" (i.e., make the carrier set elements of any type)?

• There are many other ways to implement a stack with an array
• We'll develop some in "real time" in lecture