■映射公式:1 ocation(i)=i-1 element 1 2 3 4 MaxSize-1 52481 length=5 bottom top 栈顶元素→e1 ement[ length-1] ■栈底元素→ element[0] 山东大学计算机科学与技术学院数据结构第5章堆栈
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 11 ◼ 栈顶元素 → element[length-1] ◼ 栈底元素 → element[0] 5 2 4 8 1 element 0 1 2 3 4 MaxSize-1 length=5 bottom top ◼ 映射公式：location(i）=i-1
Program 5.1 template <class t> class stack: private LinearList <T> public Stack (int MaxStackSize= 10): LinearListT>(MaxStackSize)t bool isEmptyo const ireturn LinearList<T>: IsEmpty0; bool isFullo const return ( Length(==GetMaxSize)i] T TopO const tif (Isempty o throw OutofBoundso; T X; Find(length, x); return X;] Stack<T>& add const T& x INsert (Length, x); return *this; 1 Stack <T>& delete(T& x) LLinearList<T>: Delete Length, X) return *this, y 山东大学计算机科学与技术学院数据结构第5章堆栈 12
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 12 template<class T> class Stack : private LinearList <T> { public: Stack(int MaxStackSize = 10) : LinearList<T> (MaxStackSize) {} bool IsEmpty() const {return LinearList<T> :: IsEmpty();} bool IsFull() const {return (Length() == GetMaxSize());} T Top() const {if (IsEmpty()) throw OutOfBounds(); T x; Find(Length(), x); return x;} Stack<T>& Add(const T& x) {Insert(Length(), x); return *this;} Stack<T>& Delete(T& x) {LinearList<T>::Delete(Length(), x); return *this;} }; Program 5.1
Private inherence The public and protected member of linearlist become private to stack, but the private member of linearlist are not accessible to members of Stack The constructor for Stack simply invokes the linear list constructor processing to it the desired stack size maxStackSize. When object of type stack are to be destroyed the destructor for LinearList will be invoked automatically 山东大学计算机科学与技术学院数据结构第5章堆栈
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 Private inherence ◼ The public and protected member of linearList become private to Stack, but the private member of LinearList are not accessible to members of Stack. ◼ The constructor for Stack simply invokes the linear list constructor processing to it the desired stack size MaxStackSize. When object of type Stack are to be destroyed, the destructor for LinearList will be invoked automatically
The isEmpty function is simply a call to the corresponding function for a linear list, we use the scope resolution operator to distinguish between functions and members that have the same name in the base and derived class a Since max size is private in linearlist we add a protect function GetMaxSizeo in Stack to acess the value of maxsize 山东大学计算机科学与技术学院数据结构第5章堆栈
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 ◼ The IsEmpty function is simply a call to the corresponding function for a linear list, we use the scope resolution operator :: to distinguish between functions and members that have the same name in the base and derived class. ◼ Since MaxSize is private in LinearList, we add a protect function GetMaxSize() in Stack to acess the value of MaxSize
template <class t> class linear list i public protected: int GetMax Size const return MaxSize; y private: int length int MaxSize T *element: 山东大学计算机科学与技术学院数据结构第5章堆栈 15
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 15 template <class T> class LinearList { public: …… protected: int GetMaxSize() const {return MaxSize;} private: int length; int MaxSize; T *element; };