Linked Stacks
With Examples in C++ |
Prof. David Bernstein |
Computer Science Department |
bernstdh@jmu.edu |
int
#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
#include "Node.h" Node::Node() { element = -1; next = NULL; } Node::Node(int item) { element = item; next = NULL; }
int
#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
#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; }
int
values
Stack
class
for every different type of element