linkedstack.h

data+structures+using+c的源码

//Header File linkedStack.h


#ifndef H_StackType
#define H_StackType

#include <iostream>
#include <cassert>

using namespace std;

//Definition of the node
template <class Type>
struct nodeType
{
	Type info;
	nodeType<Type> *link;
};

template<class Type>
class linkedStackType
{
public:
    const linkedStackType<Type>& operator=
                                (const linkedStackType<Type>&); 
     	//Overload the assignment operator.
    void initializeStack();
	//Function to initialize the stack to an empty state. 
	//Postcondition: The stack elements are removed; 
 	//               stackTop = NULL.
    bool isEmptyStack();
	//Function to determine whether the stack is empty.
 	//Postcondition: Returns true if the stack is empty;
	//               otherwise, returns false.
    bool isFullStack();
	//Function to determine whether the stack is full;
	//Postcondition: Returns false.
    void push(const Type& newItem);
	//Function to add newItem to the stack.
	//Precondition: The stack exists and is not full.
	//Postcondition: The stack is changed and newItem 
	//               is added to the top of stack.

    Type top();
	//Function to return the top element of the stack.
	//Precondition: The stack exists and is not empty.
 	//Postcondition: If the stack is empty, the program 
 	//               terminates; otherwise, the top element
	//               of the stack is returned.

    void pop();
	//Function to remove the top element of the stack.
	//Precondition: The stack exists and is not empty.
	//Postcondition: The stack is changed and the top element 
      //               is removed from the stack.

    void destroyStack();
	//Function to remove all the elements of the stack,  	 
      //leaving the stack in an empty state.
 	//Postcondition: stackTop = NULL

    linkedStackType(); 
   	//default constructor
  	//Postcondition: stackTop = NULL
    linkedStackType(const linkedStackType<Type>& otherStack); 
  	//copy constructor
    ~linkedStackType();
	//destructor
	  //All the elements of the stack are removed from the stack.

private:
    nodeType<Type> *stackTop; //pointer to the stack

    void copyStack(const linkedStackType<Type>& otherStack); 
      //Function to make a copy of otherStack.
 	//Postcondition: A copy of otherStack is created and
 	//               assigned to this stack.
};


template<class Type> //default constructor
linkedStackType<Type>::linkedStackType()
{
	stackTop = NULL;
}

template<class Type>
void linkedStackType<Type>::destroyStack()
{
	nodeType<Type> *temp; //pointer to delete the node

	while(stackTop != NULL)  //while there are elements in the stack
	{
	   temp = stackTop;      //set temp to point to the current node
	   stackTop = stackTop->link; //advance stackTop to the next node
	   delete temp;     //deallocate memory occupied by temp
	}
}// end destroyStack

template<class Type>
void linkedStackType<Type>:: initializeStack()
{
    destroyStack();
}

template<class Type>
bool linkedStackType<Type>::isEmptyStack()
{
	return(stackTop == NULL);
}

template<class Type>
bool linkedStackType<Type>:: isFullStack()
{
   return false;
}

template<class Type>
void linkedStackType<Type>::push(const Type& newElement)
{
   nodeType<Type> *newNode; //pointer to create the new node

   newNode = new nodeType<Type>; //create the node
   assert(newNode != NULL);

   newNode->info = newElement;   //store newElement in the node
   newNode->link = stackTop;     //insert newNode before stackTop
   stackTop = newNode;          //set stackTop to point to the top node
} //end push


template<class Type>
Type linkedStackType<Type>::top()
{
	assert(stackTop != NULL);	//if stack is empty,
								//terminate the program
   	return stackTop->info; //return the top element 
}//end top

template<class Type>
void linkedStackType<Type>::pop()
{
   nodeType<Type> *temp;       //pointer to deallocate memory

   if(stackTop != NULL)
   {
   		temp = stackTop;            //set temp to point to the top node
   		stackTop = stackTop->link;  //advance stackTop to the next node
   		delete temp;	            //delete the top node
   }
   else
		cerr<<"Cannot remove from an empty stack."<<endl;
}//end pop

template<class Type>
void linkedStackType<Type>::copyStack(const linkedStackType<Type>& otherStack)
{
	cout<<"See Programming Exercise 1"<<endl;
}

template<class Type>   //copy constructor
linkedStackType<Type>::linkedStackType(
                       const linkedStackType<Type>& otherStack) 
{
	cout<<"See Programming Exercise 1"<<endl;
}//end copy constructor


template<class Type> //destructor
linkedStackType<Type>::~linkedStackType()
{
	cout<<"See Programming Exercise 1"<<endl;
}//end destructor


template<class Type>   //overloading the assignment operator
const linkedStackType<Type>& linkedStackType<Type>::operator=
    			  (const linkedStackType<Type>& otherStack)
{ 
 	cout<<"See Programming Exercise 1"<<endl;

	return *this; 
}//end operator=

#endif