• So far, our implementations of stacks have been limited to a pre-specified number of elements
• Dynamic memory allocation makes it possible for us to develop much more flexible implementations
• We could use dynamic memory allocation with contiguous implementations or linked implementations
• We'll discuss a linked implementation here

cppexamples/linkedstack/int/Node.h

#ifndef edu_jmu_cs_Node_h
#define edu_jmu_cs_Node_h

#include <stdlib.h>

/**
 * An int Node in a singly-linked (endogenous) structure
 *
 * @author  Prof. David Bernstein, James Madison University
 */
class Node {
 public:
  int element;
  Node *next;

  /*
   * Default Constructor.
   */
  Node();

  /*
   * Explicit Value Constructor.
   *
   * @param item     The "content" of the Node
   */
  explicit Node(int item);
};
#endif
        

cppexamples/linkedstack/int/Node.cpp

#include "Node.h"

Node::Node() {
  element = -1;
  next = NULL;
}

Node::Node(int item) {
  element = item;
  next = NULL;
}
        

cppexamples/linkedstack/int/Stack.h

#ifndef edu_jmu_cs_Stack_h
#define edu_jmu_cs_Stack_h

#include "Node.h"
#include <stdlib.h>

/**
 * A linked implementation of a Stack of int
 *
 * @author  Prof. David Bernstein, James Madison University
 */
class Stack {
 public:
  /*
   * Default Constructor.
   */
  Stack();

  /*
   * Copy Constructor.
   *
   * @param original   The Stack to be copied
   */
  Stack(const Stack &original);

  /*
   * Destructor.
   */
  ~Stack();

  /*
   * Is this Stack empty?
   */
  bool isEmpty() const;

  /*
   * Removes the top element from the stack and "returns" it
   * in the output parameter item.
   *
   * @param item   The "returned" item
   * @return       underflow if the stack is empty; success otherwise
   */
  bool pop(int &item);

  /*
   * Adds an item to the top of the stack.
   *
   * @param item   The item to be added to the stack
   * @return       overflow if dynamic memory is exhausted; otherwise success
   */
  bool push(const int &item);

 private:
  Node *topNode;
};
#endif
        

cppexamples/linkedstack/int/Stack.cpp

#include "Node.h"
#include "Stack.h"

Stack::Stack() {
  topNode = NULL;
}

Stack::Stack(const Stack &original) {
  Node *newCopy, *originalNode;

  originalNode = original.topNode;

  if (originalNode == NULL) {
    topNode = NULL;
  } else {    //  Duplicate the linked nodes
    topNode = newCopy = new Node(originalNode->element);

    while (originalNode->next != NULL) {
      originalNode = originalNode->next;
      newCopy->next = new Node(originalNode->element);
      newCopy = newCopy->next;
    }
  }
}

Stack::~Stack() {
  while (!isEmpty()) {
    Node *oldTop;

    oldTop = topNode;
    topNode = oldTop->next;

    delete oldTop;
  }
}

bool Stack::isEmpty() const {
  return (topNode == NULL);
}

bool Stack::pop(int &item) {
  Node *oldTop;

  oldTop = topNode;

  if (topNode == NULL)
    return false;

  item = topNode->element;
  topNode = oldTop->next;

  delete oldTop;
  return true;
}

bool Stack::push(const int &item) {
  Node *newTop;

  newTop = new Node(item);

  if (newTop == NULL)
    return false;

  newTop->next = topNode;
  topNode = newTop;

  // Should we delete newTop before returning?
  return true;
}
        

• The current implementation can only contain int values
• We would need to create a different Stack class for every different type of element

cppexamples/linkedstack/templated/Node.h