栈( Stack) ■只允许在一端插入和删除的顺序表 允许插入和删除进栈 退栈 (压入 弹出) 的一端称为栈顶 (op),另一端称 n-1 为栈底( bottom) an-2 特点 后进先出(LIFO 01 lo botton→
栈的抽象数据类型 template class Stack i public: Stack( int=10); /构造函数 void push( const Type&item);∥选进 ype Pop o ∥/出栈 ype GetTop (; 取栈顶元素 void MakeEmpty();∥空栈 int IsEmpty( const;/,空否 int IsFull( const; /栈满否
template class Stack { public: Stack ( int=10 ); //构造函数 void Push ( const Type & item); //进栈 Type Pop ( ); //出栈 Type GetTop ( ); //取栈顶元素 void MakeEmpty ( ); //置空栈 int IsEmpty ( ) const; //判栈空否 int IsFull ( ) const; //判栈满否 }
栈的数组表示一顺序栈 include class Stack i public: Stack( int=10); /构造函数 Stack({ delete[] elements;}∥析构函数 void push( const Type& item);∥进栈 Type Pop (; ∥/出栈 Type GetTop o: 取栈顶元素 void MakeEmpty(){top=-1;}∥空栈 int IsEmpty( const i return top==-1; j
#include template class Stack { public: Stack ( int=10 ); //构造函数 ~Stack ( ) { delete [ ] elements; }//析构函数 void Push ( const Type & item ); //进栈 Type Pop ( ); //出栈 Type GetTop ( ); //取栈顶元素 void MakeEmpty ( ) { top=-1; } //置空栈 int IsEmpty ( ) const { return top == -1; }
int IsFull( const f return top=- maxSize-1; 3 private int tops /顶数组指针 Type elements;/|数组 int maxSize; 最大容量 template Stack. Stack(int s): top(1), maxSize(s)i elements- new Typel l; assert( elements!=0);∥断言
int IsFull ( ) const { return top == maxSize-1; } private: int top; //栈顶数组指针 Type *elements; //栈数组 int maxSize; //栈最大容量 } template Stack:: Stack ( int s ) : top (-1), maxSize (s) { elements = new Type[maxSize]; assert ( elements != 0 ); //断言 }
template void Stack:: Push( const Type item)& assert(!sFull (); /先决亲件断言 elements[++top]=iem;∥加入新元素 template Type Stack:: Popoi aert(! IsEmpty());∥先决条件断言 return elements[op-;∥出栈顶元素
template void Stack:: Push ( const Type & item ) { assert ( !IsFull ( ) ); //先决条件断言 elements[++top] = item; //加入新元素 } template Type Stack:: Pop ( ) { assert ( !IsEmpty ( ) ); //先决条件断言 return elements[top--]; //退出栈顶元素 }