清华大学：《数据结构》课程电子教案（PPT课件讲稿）第四章 栈与队列

a栈( Stack) 队列( Queue 优先队列( Priority Queue)

栈( 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 ); //断言 }

top→b to p top→空栈 →a进栈 b进栈 to p to p- edcb Eeacb 进栈示例 进栈 Z进栈溢出

进栈示例

to p edcba top-d top- b dcbg 退栈 e退栈 d退栈 b 退栈示例 top→a退栈tp→空栈

退栈示例

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--]; //退出栈顶元素 }

template Type stack:: GetTop oi assert(! EMpty());∥先决条件断言 return elements[tp]l;∥取出栈顶元素 双栈共享一个栈空间 maxSize-1 V 6[0 t[0 t[1] b1

template Type stack:: GetTop ( ) { assert ( !IsEmpty ( ) ); //先决条件断言 return elements[top]; //取出栈顶元素 }

多栈处理栈浮动技术 n栈共享一个数组空间vml a设立栈顶指针数组t+1和 栈底指针数组bn+1l 和b分别指示第个栈的栈顶与栈底 bm作为控制量,指到数组最高下标 各栈初始分配空间s=Lm/n」 指针初始值40]=b0=-1bl=m-1 t[i=b=b[-1]+s,i=1,2,…,n-1