Chapter 5
Stack
5.1 definition of stack
Definition,
A stack is a linear list in which insertions
and deletions take place at the same
end.This end is called the top,The other end
of the list is called the bottom.
It is also called a LIFO(last-in-first-out) list,
5.1 definition of stack
Figure 5.1 stack configurations
E?top
D?top D
C C
B B B?top
A?bottom A?bottom A?bottom
5.2 ADT stack
AbstractDataType Stack{
instances
linear list of elements;one end is called the
bottom;the other is the top;
operations
Create():Create an empty stack;
IsEmpty():Return true if stack is empty,return false
otherwise
5.2 ADT stack
IsFull ():Return true if stack if full,return false
otherwise;
Top():return top element of the stack;
Add(x),add element x to the stack;
Delete(x):Delete top element from stack and put it
in x;
}
5.3 Formula-based Representation
We may use the Formula-based representation
when Top=-1 is empty stack
stack
0 1 2 top maxtop-1
5.3 Formula-based
Representation
? Formula-based class Stack
template<class T>
class Stack {
//LIFO objects
public:
Stack(int MaxStackSize=10);
~Stack(){delete [] stack;}
bool IsEmpty()const {return top==-1;}
bool IsFull()const{return top==MaxTop;}
5.3 Formula-based
Representation
T Top()const;
Stack<T>& Add(const T& x);
Stack<T>& Delete(T& x);
Private:
int top; //current top of a stack
int MaxTop; //max value for top
T* stack; //element array
};
5.3 Formula-based
Representation
1)constructor Stack
template<class T>
Stack<T>::Stack(int MaxStackSize)
{//stack constructor
MaxTop=MaxStackSize-1;
stack=new T[MaxStackSize];
top=-1;
}
5.3 Formula-based
Representation
2)get the top element
Template<class T>
T Stack<T>::Top()const
{//return top element
if(IsEmpty())throw OutOfBounds();
else return stack[top];
}
5.3 Formula-based
Representation
3)push an element
Template<class T>
Stack<T>&Stack<T>::Add(const T& x)
{//Add x to stack
if(IsFull()) throw NoMem();
stack[++top]=x;
return *this;
}
5.3 Formula-based
Representation
4)pop an element
template<class T>
Stack<T>& Stack<T>::Delete(T& x)
{//delete top element and put it in x
if(IsEmpty())throw OutOfBounds();
x=stack[top--];
return *this;
}
5.3 Formula-based
Representation
? It is wasteful of space when multiple stacks
are to coexist
? When there’s only two stacks,we can
maintain space and time efficiency by
pegging the bottom of one stack at position
0 and the bottom of the other at position
MaxSize-1,The two stacks grow towards
the middle of the array,
5.3 Formula-based
Representation
0 ArraySize-1
top1 top2
Stack1 Stack2
………
Two stacks in a array
5.4 Linked representation
Linked stack
^top Data link ……
5.4 Linked representation
Linked stack
template<class T>
class Node{
friend LinkedStack<T>;
private:
T data;
Node<T>*link;
};
5.4 Linked representation
template<class T>
class LinkedStack{
public:
LinkedStack(){top=0;}
~LinkedStack();
bool IsEmpty()const {return top==0;}
bool IsFull()const;
T Top()const;
LinkedStack<T>& Add(const T& x);
5.4 Linked representation
LinkedStack<T>& Delete(T& x);
Private:
Node<T>* top; //pointer to top node
};
5.4 Linked representation
1)destructor
Template<class T>
LinkedStack<T>::~LinkedStack()
{Node<T>*next;
While(top){
next=top->link;
delete top;
top=next;
}
}
5.4 Linked representation
2)get top element
template<class T>
T LinkedStack<T>::Top()const
{//return top element
if(IsEmpty())throw OutofBounds();
return top->data;
}
5.4 Linked representation
3)push an element
template<class T>
LinkedStack<T>& LinkedStack<T>::Add(const T& x)
{Node<T> *p= new Node<T>;
p->data=x;
p->link=top;
top=p;
return *this;
}
5.4 Linked representation
4) pop an element
Template<class T>
LinkedStack<T>& LinkedStack<T>::Delete(T& x)
{//Delete top element and put in x
if(IsEmpty())throw OutofBounds();
x=top->data;
Node<T>*p=top;
top=top->link;
delete p;
return *this;}
5.5 Applications
1.Parenthesis Matching
2.Expression Evaluation
3.Towers of Hanoi