Efficiency of Stack ■时间复杂性:略 从 Linearlist派生 Stack: n优点: ■大大减少了编码量 ■使程序的可靠性得到很大提高。 缺点 ■运行效率降低。例:向堆栈中添加一个元素。 n派生类 Stack也会受到 Linearlist本身所受限制的影响。 例如,必须为数据类型为T的成员定义操作符<<和 山东大学计算机科学与技术学院数据结构第5章堆栈
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 16 Efficiency of Stack ◼ 时间复杂性：略 ◼ 从LinearList派生Stack： ◼ 优点： ◼ 大大减少了编码量。 ◼ 使程序的可靠性得到很大提高 。 ◼ 缺点： ◼ 运行效率降低。例：向堆栈中添加一个元素。 ◼ 派生类Stack也会受到LinearList本身所受限制的影响。 例如，必须为数据类型为T的成员定义操作符<<和 ==
2.自定义 Customized stack template <class T> class Stack i public: Stack(int Max StackSize= 10) a Stackoi delete l stack;,) bool isempty o const i return top==-1; bool isFull const i return top == MaxTop; y T Topo const; Stack <T>& add(const t& x); / push Stack<T>& delete(& x) // pop private: int top; int MaxTop T*stack 山东大学计算机科学与技术学院数据结构第5章堆栈 17
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 17 2. 自定义 Customized Stack template<class T> class Stack { public: Stack(int MaxStackSize = 10); ~Stack() { delete [] stack; } bool IsEmpty() const { return top == -1; } bool IsFull() const { return top == MaxTop; } T Top() const; Stack<T>& Add(const T& x); // push Stack<T>& Delete(T& x); // pop private: int top; int MaxTop; T *stack; };
2.自定义 Stack stack 0 234 Maxlop 5248 top=4 堆栈容量: MaxTop+1 山东大学计算机科学与技术学院数据结构第5章堆栈 18
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 18 2. 自定义Stack 5 2 4 8 1 stack 0 1 2 3 4 MaxTop top=4 堆栈容量: MaxTop+1
stack 0 1 2 3 4 aXIo p template <class t> top Stack<T>: Stack( int maxstack size){//构造函数 MaxTop= MaxStackSize-1 stack new T[MaxStackSize] top=-1; template<class T>/return the element at the top T Stack<T>: Topo const i if(IsEmpty o) throw OutofBoundsO else return stack[top 山东大学计算机科学与技术学院数据结构第5章堆栈 19
山东大学计算机科学与技术学院 数据结构 第5章 堆栈 19 template<class T> Stack<T>::Stack(int MaxStackSize) { // 构造函数 MaxTop = MaxStackSize – 1; stack = new T[MaxStackSize]; top = -1; } template<class T>// return the element at the top T Stack<T>::Top() const { if (IsEmpty()) throw OutOfBounds(); else return stack[top]; } 5 2 4 8 1 stack 0 1 2 3 4 MaxTop top=4