ADT : Stack

• Stacks : Overview
  • hold ordered list of elements
  • a last-in, first-out ordering
  • The term "stack" is based on the concept of stacking new elements one on top of another as they arrive, and processing whatever is on the top of the stack when we get the opportunity.
• Stack ADT
  • need to include the type of data being stacked
  • plus the typical stack operations. These include:
    • constructors to create an empty stack
    • destructors to clean up a stack once finished with it
    • a method which takes a new element and adds it to the stack, typically called push
    • a method to look at the element on the top of the stack, typically called top
    • a method to remove and discard the top stack element, typically called pop
    • a method which checks if the stack is full
    • a method which checks if the stack is empty
  • Note that, by convention, we can only examine the top stack element.
• Stack applications
  • language-parsing operations: evaluating computations, trying to derive meaning from text or from source code, etc
  • in information storage during program execution: storing parameters, local variables, and other key data for subroutine calls
  • Examples:
    • a stack-based algorithm for printing a string of characters backwards:
    • a stack-based algorithm for seeing if all the brackets match in a source code file:

      while not end-of-file:
         get the next character
         if the character is a left (open) bracket, push it on the stack
         if the character is a right (close) bracket
            if the stack is empty, 
               generate an error message (unmatched closing bracket)
               and exit
            if the bracket type is different than the bracket type on the
               top of the stack, generate an error message 
               (unmatched closing bracket)
               and exit
            otherwise pop the top bracket off the stack
      
      if the stack is not empty, generate an error message 
         (unmatched opening bracket) and exit
      

• Array-based implementation
  • The header file: stack.h

    #include 
    using namespace std;
    #ifndef STACK_H
    #define STACK_H
    
    // DEFAULTMAX --- default maximum stack size
    const int DEFAULTMAX = 128;
    
    // StackElement is used to determine the type of
    // data stored in the stack
    typedef char StackElement;
    
    // defaultelement can be used as a default
    // stack element value
    const char defaultelement = '\0';
    
    // Stack class, using an array-based implementation,
    // where the constructor dynamically allocates
    // the array using either the DEFAULTMAX size or
    // a size specified by passing a positive integer
    // parameter to the constructor
    //
    // the usual stack operations are available:
    //    top, pop, push, isempty, and isfull
    //
    class stack {
       public:
          stack();           // default constructor
          stack(int size);   // constructor for passed size
          ~stack();          // destructor
          // push new data on stack
          void push(StackElement data);
          void pop();        // remove top stack element
          // get copy of top stack element
          StackElement top(); 
          bool isempty(); // return True iff stack is empty
          bool isfull();  // return True iff stack is full
       private:
          StackElement *sptr;
          int maxsize;
          int currentsize;
    };
    #endif
    

  • The stack implementation: stack.cpp

    #include "stack.h"
    //   privately accessible data fields
    //   for the stack class:
    //      StackElement *sptr;
    //      int maxsize;
    //      int currentsize;
    
    // default constructor, the maximum stack size is 
    //    determined by DEFAULTMAX const in stack.h
    stack::stack()
    {
       maxsize = DEFAULTMAX;
       currentsize = 0;
       sptr = new StackElement[maxsize];
    }
    
    // constructor using the passed size
    // as the maximum stack size
    // if the passed size is a positive integer, 
    // otherwise uses DEFAULTMAX
    stack::stack(int size)
    {
       if (size > 0) maxsize = size;
       else maxsize = DEFAULTMAX;
       currentsize = 0;
       sptr = new StackElement[maxsize];
    }
    
    // destructor - deallocate stack space
    stack::~stack()
    {
       delete [] sptr;
    }
    
    // push new data on stack
    void stack::push(StackElement data)
    {
       // check to ensure stack is not already full
       if (currentsize < maxsize) {
          // add new element to top space on stack
          // and increment size counter
          // (index of top element)
          sptr[currentsize++] = data;
       } else {
          cerr << "Cannot push onto a full stack" << endl;
       }
    }
    
    // remove top stack element
    void stack::pop()
    {
       // check to ensure stack is not already empty
       if (currentsize > 0) {
          // decrement size counter
          // (which is also index of top element)
          currentsize--;
       } else {
          cerr << "Cannot pop from an empty stack"
               << endl;
       }
    }
    
    // get copy of top stack element
    StackElement stack::top()
    {
       // check to ensure stack is not currently empty
       if (currentsize > 0) {
          // return copy of top element
          return (sptr[currentsize-1]);
       } else {
          cerr << "Cannot examine top of empty stack, "
               << "returning default value" << endl;
          return defaultelement;
       }
    }
    
    // return True iff stack is empty
    bool stack::isempty()
    {
       return (currentsize == 0);
    }
    
    // return True iff stack is full
    bool stack::isfull()
    {
       return (currentsize == maxsize);
    }
    

• Stack Application Example
  • This application takes a series of command line arguments and prints each argument backwards, using a stack to reverse the characters in each string:

    #include "stack.h"
    using namespace std;
    // this program takes each of it's command line
    // arguments and uses a stack to print the argument
    // out backwards
    
    void printbackwards(char *str);
    
    int main(int argc, char *argv[])
    {
       for (int i = 0; i < argc; i++) {
           printbackwards(argv[i]);
           cout << " ";
       }
       cout << endl;
       return 0;
    }
    
    void printbackwards(char *str)
    {
       int index = 0;
       int length;
       stack *mystack;
    
       // allocate a stack just a little bigger
       // than you need
       length = strlen(str);
       mystack = new stack(length+1);
    
       // push the string contents onto the stack
       // one character at a time until you hit
       // the end of the string
       while (index < length) {
          mystack->push(str[index]);
          index++;
       }
    
       // pop the stack contents off and print them
       // one at a time until the stack is empty
       while (mystack->isempty() == False) {
          cout << mystack->top();
          mystack->pop();
       }
    
       delete mystack;
    }
    

• Stack Application Example
  • This application takes a series of command line arguments and determines whether or not each is a palindrome (i.e. is spelled the same way forward and backwards) using a stack to check the characters in each string:

    
    #include "stack.h"
    using namespace std;
    // this program takes each of it's command line
    // arguments and uses a stack to determine
    // if the argument is a palindrome
    
    bool ispalindrome(char *str);
    
    int main(int argc, char *argv[])
    {
       for (int i = 0; i < argc; i++) {
           cout << argv[i];
           if (ispalindrome(argv[i])) {
              cout << " is a palindrome" << endl;
           } else {
              cout << " is not a palindrome" << endl;
           }
       }
       return 0;
    }
    
    bool ispalindrome(char *str)
    {
       int index = 0;
       int length;
       stack *mystack;
    
       length = strlen(str);
       mystack = new stack(length+1);
    
       // push the string contents onto the stack
       // one character at a time until you
       // hit the end of the string
       while (str[index] != '\0') {
          mystack->push(str[index]);
          index++;
       }
    
       // pop the stack contents off and compare them
       // to the string contents one at a time until
       // you find a difference orthe stack is empty
       index = 0;
       while (!(mystack->isempty())) {
          if (mystack->top() != str[index++]) {
             delete mystack;
             return false;
          } else {
             mystack->pop();
          }
       }
    
       delete mystack;
       return true;
    }