Simple stack classes

Stacks are described as a LIFO structure (last in first out), meaning you do inserts and removes from the same end of what is otherwise a very list-like structure.

The conceptual idea is that you have a pile, or stack, of items and you are either putting new items on the top of it or removing the top item from it.

The most common operations are called push (for pushing a new item onto the top) or pop (for removing the current item from the top).

Other common operations include top (for looking at the contents of the top item without removing it from the stack), isempty (to check if the stack is currently empty), and sometimes isfull (to check if the stack is currently full).

The two programs below implement very simple stacks. The first program uses a linked list style of implementation, while the second uses an array-based implementation.

They each have a simple main routine that pushes all the command line arguments onto the stack, then goes through and pops them all off and displays them (so the user sees the arguments displayed in reverse order).


Version 1 (linked-list style)

#include <iostream>
#include <string>
using namespace std;

class Stack {
   public:
      Stack();  // initialize an empty stack
      ~Stack(); // delete all stack contents

      // push s onto the stack, return true iff successful
      bool push(string s); 

      // if the stack is empty return false,
      // otherwise copy the top string into s,
      //    remove and delete the element, and return true
      bool pop(string &s);

      // if the stack is empty return false, 
      // otherwise copy the top string into s and return true
      bool top(string &s);

      // return true iff the stack is currently empty
      bool isempty();

   private:
      // the stack is a collection of nodes, each with
      // a pointer to the next node (i.e. the one below it)
      struct node {
         string data;
         node*  next;
      };

      // access the stack contents through a pointer to the top node
      node *topOfStack;
};

// create an empty stack,
// push all the command line arguments into it
// then pop them off and display them one at a time
int main(int argc, char *argv[])
{
   Stack S;
   string s;
   for (int i = 1; i < argc; i++) S.push(argv[i]);
   while (S.top(s)) {
      S.pop(s);
      cout << s << endl;
   }
   return 0;
}

// create an empty stack
Stack::Stack()
{ 
   topOfStack = NULL;
}

// delete all the nodes in the stack
Stack::~Stack()
{
   string s;
   while (topOfStack!= NULL) pop(s);
}

// create and push a new node on the stack,
// return true iff successful
bool Stack::push(string s)
{
   node *n = new node;
   if (!n) return false;
   n->data = s;
   n->next = topOfStack;
   topOfStack = n;
   return true;
}

// copy the top string out of the stack,
// return true iff successful
bool Stack::top(string &s)
{
   if (!topOfStack) return false;
   s = topOfStack->data;
   return true;
}

// copy the top string out of the stack,
// remove and deallocate the node,
// return true iff successful
bool Stack::pop(string &s)
{
   if (!topOfStack) return false;
   node *victim = topOfStack;
   s = victim->data;
   delete victim;
   topOfStack = topOfStack->next;
   return true;
}

// return true iff the stack is currently empty
bool Stack::isempty()
{
   if (!topOfStack) return true;
   else return false;
}


Version 2 (array based)

#include <iostream>
#include <string>
using namespace std;

class Stack {
   public:
      // establish a default maximum size for the stack
      static const int DefaultSize = 20;
      
      // initialize an empty stack with a maximum
      //   size as specified by the parameter
      Stack(int size = DefaultSize);
      ~Stack(); // delete all stack contents

      // push s onto the stack, return true iff successful
      bool push(string s); 

      // if the stack is empty return false,
      // otherwise copy the top string into s,
      //    remove and delete the element, and return true
      bool pop(string &s);

      // if the stack is empty return false, 
      // otherwise copy the top string into s and return true
      bool top(string &s);

      // return true iff the stack is currently empty
      bool isempty();

      // return true iff the stack is currently full
      bool isfull();

   private:
      // store the stack contents using an array
      string *arr;

      // remember the size of the allocated array
      int stackSize;

      // array position of the current top stack element
      // (-1 when the stack is empty)
      int topOfStack;
};

int main(int argc, char *argv[])
{
   // create a stack of size argc
   Stack *S = new Stack(argc);
   if (S == NULL) return 0;

   string s;
   for (int i = 1; i < argc; i++) S->push(argv[i]);
   while (S->top(s)) {
      S->pop(s);
      cout << s << endl;
   }
   return 0;
}

// initialize an empty stack with a maximum
//   size as specified by the parameter
Stack::Stack(int size)
{
   // allocate the array and remember the size allocated 
   arr = new string[size];
   if (arr == NULL) stackSize = 0;
   else stackSize = size;

   // for empty stacks the top of stack array position is -1
   topOfStack = -1;
}

// delete all stack contents
Stack::~Stack()
{
   // deallocate the array
   delete [] arr;
}

// push s onto the stack, return true iff successful
bool Stack::push(string s)
{
   // cannot push if the stack is full
   if (isfull()) return false;

   // increment the top of stack position in the array
   //   and then store the value
   topOfStack++;
   arr[topOfStack] = s;
   return true;
}

// if the stack is empty return false, 
// otherwise copy the top string into s and return true
bool Stack::top(string &s)
{
   // cannot take the top of an empty stack
   if (isempty()) return false;

   // copy the data out of the current top position in the array
   s = arr[topOfStack];
   return true;
}

// if the stack is empty return false,
// otherwise copy the top string into s,
// remove and delete the element, and return true
bool Stack::pop(string &s)
{
   // cannot pop from an empty stack
   if (isempty()) return false;

   // copy the data out of the current top position in the array
   // then decrement the top position
   s = arr[topOfStack];
   topOfStack--;
   return true;
}

// return true iff the stack is currently empty
bool Stack::isempty()
{
   // the stack is empty when the top of stack 
   //     position is set at -1
   if (topOfStack == -1) return true;
   else return false;
}

// return true iff the stack is currently full
bool Stack::isfull()
{
   // the stack is full if the top element is in
   //     the last position in the array
   if (topOfStack == (stackSize-1)) return true;
   else return false;
}