《数据结构的算法在C++中的应用》（英文版）Chapter 5 Stack

Chapter 5 Stack

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 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 DK-top DCB B Btop A长 bottomA< bottom A长 bottom

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 AbstractData Type Stacki instances linear list of elements one end is called the bottom the other is the top operations Create: Create an empty stack; IsEmpty O: Return true if stack is empty, return false otherwise

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 o: 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(): Delete top element from stack and put it In X

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 012 top maxtop-l stack when Top==-1 is empty stack

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 Stack //LIFO objects publiC Stack(int MaxStackSize=10) Stackoi delete stack; 1 bool isemptyoconst return top==--1 bool IsFulloconst return top== Top; 1

5.3 Formula-based Representation • Formula-based class Stack template 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 TopOconst Stack & add(const T& x) Stack& delete& x) Private int top; /current top of a stack int MaxTop; //max value for top T* stack; /element array

5.3 Formula-based Representation T Top()const; Stack& Add(const T& x); Stack& 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 Stack Stack(int MaxStackSize) (//stack constructor MaxTop-MaxStack Size-l stack-new T[MaxStack Size top=-l

5.3 Formula-based Representation 1)constructor Stack template Stack::Stack(int MaxStackSize) {//stack constructor MaxTop=MaxStackSize-1; stack=new T[MaxStackSize]; top=-1; }

5.3 Formula-based Representation Get the top element Template T Stack: TopOconst f//return top element if(Is empty throw OutofBoundso else return stack[]

5.3 Formula-based Representation 2)get the top element Template T Stack::Top()const {//return top element if(IsEmpty())throw OutOfBounds(); else return stack[top]; }