/**/ //////////// //stack.h /////////////// /
////////////////////////////////////////////////
#ifndef?stack_h_
#define ?stack_h_
#include? < iostream >
using ? namespace ?std;

template? < class ?T > ? class ?stack
{
public :
???? virtual ? void ?push( const ?T? & x) = 0 ;
???? virtual ? void ?pop() = 0 ;
???? virtual ?T?Top()? const ? = ? 0 ;
???? virtual ? bool ?IsEmpty()? const ? = 0 ;
???? virtual ? bool ?IsFull()? const = 0 ;

} ;

#endif

/**/ //////////// segstack.cpp ///////////////
///////// 數組組織代碼 ////////////////////////

#include? " stack.h "

template? < class ?T > ? class ?SegStack:? public ?stack < T >
{
public :
????SegStack( int ?mSize);
???? ~ SegStack();
???? bool ?IsEmpty()? const ;
???? bool ?IsFull()? const ;
???? void ?push( const ?T? & x);
???? void ?pop();
????T?Top()? const ;
???? // friend?ostream&?operator?<<?(ostream&?out,const?SegStack<T>&?seg);
????template? < ? class ?T > ?friend?ostream & ? operator ? << ?(ostream & ? out , const ?SegStack < T >& ?seg);?
???? void ?output(ostream & ? out )? const ;

private :
????T? * s;
???? int ?maxSize;
???? int ?top;
} ;

template? < class ?T > ?SegStack < T > ::SegStack( int ?mSize):top( - 1 )
{
????maxSize = mSize;
????s? = ? new ?T[maxSize];

}
template? < class ?T > ?SegStack < T > :: ~ SegStack()
{
????delete?[]s;
}

template? < class ?T > ? bool ?SegStack < T > ::IsFull()? const
{????????
???? return ?(top == (maxSize - 1 ));
}

template? < class ?T > ? bool ?SegStack < T > ::IsEmpty()? const
{
???? return ?(top ==- 1 );
}

template? < class ?T > ? void ?SegStack < T > ::push( const ?T? & x)
{
???? if (IsFull())
???? {
????????cout << " The?stack?is?full " << endl;
????} else
???? {
????????s[ ++ top] = x;
????}
}

template? < class ?T > ? void ?SegStack < T > ::pop()
{
???? if (IsEmpty())
???? {
????????cout << " The?stack?is?empty " << endl;
????} else ????
???? {
????????top -- ;
????}
}
template? < class ?T > ?T?SegStack < T > ::Top()? const
{
???? return ?s[top];
}

template? < class ?T > ? void ?SegStack < T > ::output(ostream & ? out )? const
{
???? out << " The?stack?list?is: " ;
???? for ( int ?i( 0 );i <= top;i ++ )
???????? out << " ? " << s[i];
???? // out<<endl;
}

template? < class ?T > ?ostream & ? operator ? << ?(ostream & ? out , const ?SegStack < T >& ?seg)
{
???? out << " The?stack?list?is: " ;
???? for ( int ?i( 0 );i <= seg.top;i ++ )
???????? out << " ? " << seg.s[i];
???? // out<<endl;
???? // seg.output(out);
???? return ? out ;
}

/**/ /////////////// linkstack.cpp ////////////
//////////// //鏈表實現 ///////////////////// //
#include? " stack.h "

template? < class ?T1 > ? struct ?Element
{
????T1?content;
????Element * ?next;
} ;
template? < class ?T1 > ? class ?LinkStack:? public ?stack < T1 >
{
public :
????LinkStack();
???? ~ LinkStack();
???? bool ?IsEmpty()? const ;
???? bool ?IsFull()? const ;
???? void ?push( const ?T1? & x);
???? void ?pop();
????T1?Top()? const ;
????template? < class ?T > ?friend?ostream & ? operator << (ostream & ? out ,? const ?LinkStack < T1 >& ?linkstack);
???? void ?output(ostream & ? out )? const ;

private :

????Element < T1 >* ?top;
} ;
template? < class ?T1 > ? bool ?LinkStack < T1 > ::IsEmpty()? const
{
???? if (top == NULL)
???????? return ? true ;
???? else
???????? return ? false ;
}
template? < class ?T1 > ? bool ?LinkStack < T1 > ::IsFull()? const
{
???? return ? false ;
}
template? < class ?T1 > ?LinkStack < T1 > ::LinkStack():top(NULL)
{
}
template? < class ?T1 > ?LinkStack < T1 > :: ~ LinkStack()
{
???? while (top != NULL)
???? {
????????Element < T1 >* ?temp;
????????temp = top;
????????top = top -> next;
????????delete?temp;
????}
}

template? < class ?T1 > ? void ?LinkStack < T1 > ::push( const ?T1? & x)
{
????Element < T1 >* ?temp = new ?Element < T1 > ;
????temp -> content = x;
????temp -> next = top;
????top = temp;
}
template? < class ?T1 > ? void ?LinkStack < T1 > ::pop()
{
???? if (top != NULL)
???? {
????????Element < T1 >* ?temp;
????????temp = top;
????????top = top -> next;
????????delete?temp;
????}
????
}

template? < class ?T1 > ?T1?LinkStack < T1 > ::Top()? const
{
???? return ?top -> content;
????
}
template? < class ?T1 > ?ostream & ? operator << (ostream & ? out ,? const ?LinkStack < T1 >& ?linkstack)
{
????Element < T1 >* ?temp;
????temp = linkstack.top;

???? out << " The?stack?list?is: " ;
???? while (temp != NULL)
???? {
???????? out << temp -> content << ' ? ' ;
????????temp = temp -> next;
????}

???? return ? out ;
}
template? < class ?T1 > ? void ?LinkStack < T1 > ::output(ostream & ? out )? const
{
????Element < T1 >* ?temp;
????temp = top;

???? out << " The?stack?list?is: " ;
???? while (temp != NULL)
???? {
???????? out << temp -> content << ' ? ' ;
????????temp = temp -> next;
????}
}