JMU
An Introduction to Stacks
With Examples in C++


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu


Motivation
An Analogy: A Box of Paper
A Definition of a 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.

One Array-based Implementation
One Array-based Implementation (code)

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;
}
        
Things to Think About
Other Array-based Implementations