用链表实现堆栈

#include "stdafx.h"
#include
#include
using namespace std;

/*******************
*堆栈的链表实现
*******************/
template
struct nodeType
{
 Type info;
 nodeType *link;
};
template
class linkedStackType
{
 friend ostream& operator<< <>(ostream& os,const linkedStackType& otherStack)
 {
  assert(otherStack.stackTop!=NULL);
  nodeType *temp;
  temp=otherStack.stackTop;
  while(temp!=NULL)
  {
   os<info<<" ";
   temp=temp->link;
   
  }
  return os;
 }
public:
 const linkedStackType& operator=(const linkedStackType&);
 //overload the assignment operator
 void initStack();
 //function to initialize the stack using stackTop=0
 bool isEmpty();
 //funtion to determine whether the stack is empty
 bool isFull();
 //funtion to determine whether the stack is full
 void destroyStack();
 //remove all the elements of the stack
 void push(const Type& newItem);
 //funtion to add new element to the stack
 Type top();
 //function to return the top element of the stack
 void pop();
 //function to remove the top element of the stack
 linkedStackType();
 linkedStackType(const linkedStackType& otherStack);
 //copy constructor
 ~linkedStackType();
 //remove all the elements from the stack

private:
 nodeType *stackTop;//pointer to the stack

 void copyStack(const linkedStackType& otherStack);
 //private:only use this funtion to implement the copy constructor and to overload
 //the assignment operator
};
/*template
ostream& operator<<(ostream& os,const linkedStackType& otherStack)
{
 assert(otherStack.stackTop>0 && otherStack.stackTop for(int i=0;i  os< return os;
}*/
//initialize the stack
template
void linkedStackType::initStack ()
{
 destroyStack();
}
//destroy the stack
template
void linkedStackType::destroyStack()
{
 nodeType *temp;
 while(stackTop!=NULL)
 {
  temp=stackTop;
  stackTop=stackTop->link;
  delete temp;
 }
}
//is the stack empty?
template
bool linkedStackType::isEmpty ()
{
 return (NULL==stackTop);
}
//is the stack full?
template
bool linkedStackType::isFull ()
{
 return false;
 //堆栈内存动态分配，故堆栈永远不会满
}
//push node into stack
template
void linkedStackType::push (const Type& newItem)
{
 nodeType *newNode;
 newNode=new nodeType;
 assert(newNode!=NULL);
 newNode->info =newItem;
 newNode->link =stackTop;
 stackTop=newNode;
}

//return the top element
template
Type linkedStackType::top ()
{
 assert(stackTop!=NULL);
 return stackTop->info;
}
//pop
template
void linkedStackType::pop ()
{
 nodeType *temp;
 if(stackTop!=NULL)
 {
  temp=stackTop;
  stackTop=stackTop->link ;
  delete temp;
 }
 else
  cerr<<"there is no node in the stack"<}
//copy a stack
template
void linkedStackType::copyStack (const linkedStackType& otherStack)
{
 
 if(stackTop!=NULL)
  destroyStack();
 linkedStackType st;
 nodeType *top=otherStack.stackTop ;
 while(top!=NULL)
 {
  st.push (top->info);
  top=top->link ;
 }

 nodeType *newNode;
 nodeType *temp=st.stackTop ;
 while(temp !=NULL)
 {
  newNode=new nodeType;
  assert(newNode!=NULL);
  newNode->info =temp->info ;
  newNode->link =stackTop;
  stackTop=newNode;

  temp=temp->link;

 }
}
/*****************************
*constructor & destructor
*****************************/
template
linkedStackType::linkedStackType()
{
 stackTop=NULL;
}
template
linkedStackType::~linkedStackType ()
{
 destroyStack();
 //free the memory occupied by the array
}
//copy constructor
template
linkedStackType::linkedStackType (const linkedStackType& otherStack)
{
 stackTop=NULL;//it's not safe to delete [] list if list!=NULL at the beginning of copyStack()
 copyStack(otherStack);
}
//overload the assignment operator
template
const linkedStackType& linkedStackType::operator =(const linkedStackType& otherStack)
{
 //avoid self-copy
 if(this!=&otherStack)
 {
  copyStack(otherStack);
 }
 return *this;
}
//program to test varios operations of the stack
int main()
{
 linkedStackType st1;
 linkedStackType tempst;
 st1.push (23);
 st1.push (45);
 st1.push (38);
 st1.push (67);

 cout<

 tempst=st1;
 cout<<"The top element of tempst:"< cout<

 linkedStackType st2(st1);//copy constructor
 cout< cout< return 0;
}