第四章栈和队列 表达式求值 队列 优先队列
◼ 栈 ◼ 表达式求值 ◼ 队列 ◼ 优先队列
栈( Stack) 只允许在一端插入和删除的线性表 允许插入和删除 退栈 进栈 的一端称为栈顶 top),另一端称 top 为栈底( bottom) n-2 特点 0 后进先出(LIFO) bottom
◼ 只允许在一端插入和删除的线性表 ◼ 允许插入和删除 的一端称为栈顶 (top)，另一端称 为栈底(bottom) ◼ 特点 后进先出 (LIFO) 栈 ( Stack ) 退栈 进栈 a0 an-1 an-2 top bottom
栈的抽象数据类型 template <class Type> 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 Type> class Stack { public: Stack ( int sz = 10 ); //构造函数 void Push ( Type& item); //进栈 Type Pop ( ); //出栈 Type GetTop ( ); //取栈顶元素 void MakeEmpty ( ); //置空栈 int IsEmpty ( ) const; //判栈空否 int IsFull ( ) const; //判栈满否 } 栈的抽象数据类型
栈的数组表示一顺序栈 include <assert.h> template <class Type> class Stack i private int top, ∥栈顶指针 ype relements, 栈元素数组 int maxSize. 最大容量 public Stack( int sz=10);/造函数 Stack(){ delete [ elements步楼 void Push( Type item ); /
#include <assert.h> template <class Type> 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 <class Type> Stack<Type>:: 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 <class Type> Stack<Type> :: Stack ( int s ) : top (-1), maxSize (s) { elements = new Type[maxSize]; assert ( elements != NULL ); //断言 }