• 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

#ifndef edu_jmu_cs_Stack_h
#define edu_jmu_cs_Stack_h

const int maxstack = 10;

/**
 * A simple implementation of a stack ADT.
 *
 */
class Stack {
 public:
  /**
   * Default constructor
   */
  Stack();

  /**
   * Is the stack empty?
   *
   * @return  true if the stack is empty and false otherwise
   */
  bool isEmpty();

  /**
   * Return and remove the top item on ths stack.
   *
   * @return  The item if one exists and -1 if the stack is empty
   */
  int pop();

  /**
   * Add an element to the top of the stack
   *
   * @param item  The item to push
   * @return true if the push was successful and false if the stack was full
   */
  bool push(int item);

 private:
  // The number of items on the stack
  int count;

  // The array containing the items
  int entry[maxstack];
};

#endif
        

cppexamples/arraystack/Stack.cpp

#include "Stack.h"

Stack::Stack() {
  count = 0;
}

bool Stack::isEmpty() {
  bool outcome = true;

  if (count > 0)
    outcome = false;

  return outcome;
}

int Stack::pop() {
  int outcome = 0;

  if (count == 0) {
    outcome = -1;
  } else {
    outcome = entry[count - 1];
    --count;
  }

  return outcome;
}

bool Stack::push(int item) {
  bool outcome = true;

  if (count >= maxstack) {
    outcome = false;
  } else {
    entry[count] = item;
    count++;

    // What do you think about:
    // entry[count++] = item;
  }
  return outcome;
}

        

cppexamples/arraystack/Example.cpp

#include <iostream>
#include "Stack.h"
using namespace std;

/**
 * An example that uses a stack
 */
int main(void) {
  int item, n;
  Stack numbers;

  cout << "\n\n Enter the size of the stack: ";

  // Read the size of the stack
  cin >> n;

  // Read the individual numbers
  for (int i = 0; i < n; i++) {
    cout << " Enter a number: ";
    cin >> item;
    numbers.push(item);
  }

  cout << "The numbers in reverse order: " << endl << endl;

  // Print the contents of the stack
  while (!numbers.isEmpty()) {
    cout << numbers.pop() << endl;
  }
  cout << endl;

  return 1;
}
        

• 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