Stack

Stack Data Structure in C Plus Plus

// stack.cc
// Jesse B. Dooley
// 21 OCT 1996

// template single linked stack class

// The following overloaded operator is
// assumed for the S data type.
// =  assignment

// Overloaded >> and << ARE PROVIDED FOR
// STREAMING I/O



#IFNDEF STACK_CC
#DEFINE STACK_CC

#INCLUDE <IOSTREAM.H>  // UNIX

// prototype class
template <CLASS S> class stack;
// prototype input function

template <CLASS S> istream& operator >> (istream&, stack<S>&);
// prototype output function

template <CLASS S> ostream& operator << (OSTREAM&, STACK<S>& );


template<CLASS S> class stack {

   struct stacknode {
      S StackData;
      stacknode *next;
   };

   stacknode *first;

   unsigned long m_ulPopulation;

friend istream& operator >> (istream &IS , stack<S> &A);

friend ostream& operator << (OSTREAM &OS , STACK<S>& A );

public:

stack()
// first = current = last = 0, m_population = 0
{
   first = NULL;
   m_ulPopulation = 0;
}

stack(const stack<S> &P)
// copy stack P to stack *this
{
     if( P.first )
     {
         erase();
         first = new stacknode;
         first->StackData = P.first->StackData;
         stacknode *currL = NULL;
         stacknode *Pcurr = P.first->next;
         first->next = currL;
         while( Pcurr )
         {
                currL = new stacknode;
                currL->StackData = Pcurr->StackData;
                Pcurr = Pcurr->next;
                currL = currL->next;
         }
     }
     else
     {
         first = NULL;
     }
     m_ulPopulation = P.m_ulPopulation;
}

~stack()
// deletes and frees stack nodes from first to last
{
   while (first)
   {
      stacknode *ptr = first;
      first = first->next;
      delete ptr;
   }
   first = NULL;
}


S top ( )
{
    stacknode *newnode = new stacknode;

    if (first != NULL)
    {
        newnode->StackData = first->StackData;
    }
    return newnode->StackData;
}


stack<S> operator=( const stack<S> &P )
{
     if( P.first )
     {
         erase();
         first = new stacknode;
         first->StackData = P.first->StackData;
         stacknode *currL = NULL;
         stacknode *Pcurr = P.first->next;
         first->next = currL;
         while( Pcurr )
         {
                currL = new stacknode;
                currL->StackData = Pcurr->StackData;
                Pcurr = Pcurr->next;
                currL = currL->next;
         }
     }
     else
     {
         first = NULL;
     }
     m_ulPopulation = P.m_ulPopulation;
     return *this;
} // =


unsigned long census()
{
    return m_ulPopulation;
}

int push( S d )
{
    stacknode *newnode = new stacknode;

    if (newnode == NULL)
        return 0;

    if( first == NULL )
    {
        newnode->next = NULL;
    }
    else
    {
        newnode->next = first;
    }

    first = newnode;

    newnode->StackData = d;

    m_ulPopulation++;

    return 1;
} // push( S d )


S pop()
{
    stacknode *newnode = new stacknode;
    
    if (first == NULL)
        return newnode->StackData;
        
    newnode->next = first;
    newnode->StackData = first->StackData;

    first = first->next;
    
    delete newnode->next;
    m_ulPopulation--;

    return newnode->StackData;
}

void erase()
{
   while (first)
   {
      stacknode *ptr = first;
      first = first->next;
      delete ptr;
   }
   first = NULL;
} // erase()


int isempty ()
{
    return (first == NULL);
}
};

template <CLASS S> istream& operator >> (istream &IS , stack<S> &A)
{
     if( IS )
     {
         S D;
         IS >> D;
         A.push( D );
     }
     return IS;
}

template <CLASS S> ostream& operator << (OSTREAM &OS , STACK<S>& A )
{
    stacknode *ptr = A.first;
    while ( ptr )
    {
          OS << PTR->StackData
          ptr = ptr->next;
    }
    return OS;
}
#endif // stack.cc

Internal Links

Parent Article: Programming Portfolio