清华大学：《C++数据结构》第四章 栈和队列

第四章栈和队列 表达式求值 队列 优先队列

◼ 栈 ◼ 表达式求值 ◼ 队列 ◼ 优先队列

栈( Stack) 只允许在一端插入和删除的线性表 允许插入和删除 退栈 进栈 的一端称为栈顶 top),另一端称 top 为栈底( bottom) n-2 特点 0 后进先出(LIFO) bottom

◼ 只允许在一端插入和删除的线性表 ◼ 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) ◼ 特点 后进先出 (LIFO) 栈 ( Stack ) 退栈 进栈 a0 an-1 an-2  top bottom

栈的抽象数据类型 template class stack t public: Stack( int sz=10); /构造函数 void push(Type&item);∥进栈 Type pop o; ∥出栈 Type Get Top (; ∥取栈顶元素 void MakeEmpty (; 置空栈 int IsEmpty() const;W栈空否 int IsFull const /栈满否

template class Stack { public: Stack ( int sz = 10 ); //构造函数 void Push ( Type& item); //进栈 Type Pop ( ); //出栈 Type GetTop ( ); //取栈顶元素 void MakeEmpty ( ); //置空栈 int IsEmpty ( ) const; //判栈空否 int IsFull ( ) const; //判栈满否 } 栈的抽象数据类型

栈的数组表示一顺序栈 include template class Stack i private int top, ∥栈顶指针 ype relements, 栈元素数组 int maxSize. 最大容量 public Stack( int sz=10);/造函数 Stack(){ delete [ elements步楼 void Push( Type item ); /

#include template class Stack { private: int top; //栈顶指针 Type *elements; //栈元素数组 int maxSize; //栈最大容量 public: Stack ( int sz = 10 ); //构造函数 ~Stack ( ) { delete [ ] elements; } void Push ( Type & item ); //进栈 栈的数组表示 — 顺序栈

Type Pop (); ∥/出栈 Type GetTop () ∥取栈顶 void MakeEmpty(){top=-1;}∥置空栈 int Is Empty const return top==-1; 3 int IsFull( const f return top=maxSize-1;) template Stack:: Stack( int s): top(-1), maxSize(s)i elements= new Type]; assert( elements!=NULL);断言

Type Pop ( ); //出栈 Type GetTop ( ); //取栈顶 void MakeEmpty ( ) { top = -1; } //置空栈 int IsEmpty ( ) const { return top == -1; } int IsFull ( ) const { return top == maxSize-1; } } template Stack :: Stack ( int s ) : top (-1), maxSize (s) { elements = new Type[maxSize]; assert ( elements != NULL ); //断言 }

top-b top- top→空栈 a进栈 b进栈 top top- edcba to p b edcba e进栈 ∫进栈濫出 e退栈

top 空栈 top top top top top a 进栈 b 进栈 a a b a b c d e e 进栈 a b c d e f 进栈溢出 a b d e e 退栈 c

top cba top-b b top d退栈 C退栈 b退栈 top-a退栈top→空栈

top c 退栈 b 退栈 a b a a 退栈 空栈 top a b d d 退栈 c top a b c top top

template void Stack:: Push( Type item assert(!IsFull () ∥/先决条件断言 elements[++topl=item;∥/加入新元素 template int stack:: Popoi if( IsEmpty() return0;栈空不退栈 top, return 1 ∥退出栈顶元素

template void Stack :: Push ( Type & item ) { assert ( !IsFull ( ) ); //先决条件断言 elements[++top] = item; //加入新元素 } template int stack :: Pop ( ) { if ( IsEmpty ( ) ) return 0; //栈空不退栈 top--; return 1; //退出栈顶元素 }

template Type stack:: GetTop oi assert( IsEmpty());∥先决条件断言 return elements[top];/取出栈顶元素 双栈共享一个栈空间 0 maxSize-1 b[0 t0]{1

template Type stack:: GetTop ( ) { assert ( !IsEmpty ( ) ); //先决条件断言 return elements[top]; //取出栈顶元素 } 双栈共享一个栈空间 b[0] t[0] t[1] b[1] 0 maxSize-1 V

栈的链接表示一链式栈 top- 链式栈无栈满问题,空间可扩充 插入与删除仅在栈顶处执行 a链式栈的栈顶在链头 适合于多栈操作

栈的链接表示 — 链式栈 ◼ 链式栈无栈满问题，空间可扩充 ◼ 插入与删除仅在栈顶处执行 ◼ 链式栈的栈顶在链头 ◼ 适合于多栈操作 top