A Stack is a list in which the Insert and Remove operations operate only
at the "top" of the list.
Insertions are done by using the member function Push().
Removals are done by using the member function Pop().
Note: Pop() does not return the top element. It returns void after popping
the stack. To gain access to the top element, you must use Top().
Top() simply returns the top element without popping the Stack.
Pop_And_Top() first pops the stack, then returns the top element.
24.1 List implementation of Stack
template <class T> class Stack; // forward declaration of Stack
template <class Etype>
class Node
{
protected:
Etype Element;
Node *Next;
Node ( Etype E = 0, Node *N = NULL )
: Element( E ), Next( N ) {}
friend class Stack;
};
template <class Element_Type>
class Stack
{
private:
// The stack is a linked list with no header node
Node<Element_Type> *Stack_Top;
public:
// Default stack size is meaningless.
Stack( unsigned int Max_Size = 100 ) : Stack_Top ( NULL ) {}
// copy constructor
Stack( Stack & Value );
// destructor
~Stack( );
const Stack & operator = ( const Stack & Value );
void Push( const Element_Type & X );
void Pop( );
Element_Type Pop_And_Top( );
const Element_Type & Top( ) const;
int Is_Empty( ) const
{ return Stack_Top == NULL; }
};
QUESTION: Why not use the linkedlist implementation of List to
implement a Stack?
? ANSWER:
QUESTION: Why is there no Is Full function for listbased Stacks?
ANSWER:
24.2 Array Implementation of Stack
In the array implementation, an array of fixed and predetermined size is allocated during construction. The Top_Of_Stack cursor is always one less than the next available open slot. Thus, an empty stack has the Top_Of_Stack cursor set to 1. A full stack is indicated by the Top_Of_Stack cursor being equal to the highest index in the array (namely the cursor Full_Stack). To Push(), first increment the Top_Of_Stack cursor, then set array[Top_Of_Stack] to Element. The "top" of the stack is on the "right" of the array. To Pop(), simply decrement Top Of Stack.static const Default_Size = 100;
template <class Element_Type>
class Stack
{
private:
unsigned int Full_Stack;
int Top_Of_Stack;
Element_Type *Stack_Array;
public:
Stack( unsigned int Max_Size = Default_Size );
Stack( const Stack & Value );
~Stack( )
{ delete [ ] Stack_Array; }
const Stack & operator = ( const Stack & Value );
void Push( const Element_Type & X );
void Pop( );
const Element_Type & Pop_And_Top( );
const Element_Type & Top( ) const;
void Make_Empty( );
int Is_Empty( ) const
{ return Top_Of_Stack == 1; }
int Is_Full( ) const
{ return Top_Of_Stack == Full-Stack 1;}
};
24.3 Comparison of Array and List
Implementations of Stack
Because a pointer (in list implementation) or a cursor (in array implementation) is kept to the top of stack, all operations can be done in O(1) (constant) time. The big difference between the array and list implementations is that the array has a fixed size that cannot be changed. There is therefore the possibility of stack overflow with arrays, but not with lists.