[工学]栈和队列.ppt

第四章 栈和队列 栈和队列都是操作受限的线性表，应用十分广泛。 4.1 栈（Stack） 定义：栈是限制插入和删除操作只能在某一端进行的线性表，并按先进后出（ F I L O )或后进先出（ＬIＦＯ）的原则进行操作 入栈顺序： e0 e1 e2 … en-2 en-1 出栈顺序： en-1 en-2 … e2 e1 e0 栈可以对序列实现求逆 栈的基本操作： （参见P104） （1）栈初始化 Stack ( int = 10 );//构造函数 （2）进栈 Push void Push( const Type item ); （3）出栈 Pop Type Pop( ); （4）判栈空 IsEmpty int IsEmpty( ) { return top==-1;} （5）读取栈顶元素 GetTop Type GetTop ( ); （6）置空栈 MakeEmpty void MakeEmpty( ) { top=-1;} （7）判栈满 IsFull int IsFull( ) const { return top==maxSize;} 栈的封闭性及其抽象数据类型： 在一个栈中，出入口处称为栈顶，栈内最深处称为栈底。除了栈顶元素外，其他元素不会被改变，因而栈的封闭性非常好，使用起来非常安全。另外，在下面的栈的类定义中，体现了栈的抽象数据类型，在此定义中，所有栈的成员函数都是共有的，其他类的成员函数都可以使用这些函数，但是，栈的存储表示和成员函数的实现对其他类的成员来说都是隐蔽的。 4.1.1 顺序栈－－在顺序存储结构上实现的栈 # include assert.h //C＋＋断言功能 template class Type class Stack //顺序栈的类定义 { public: Stack ( int=10 );//栈初始化，建立一个空栈，缺省大小为10 ~Stack ( ) { delete [ ] elements ; } void Push ( const Type item ); //将数据元素 item 入栈 Type Pop ( ) ; //将栈顶元素出栈 Type GetTop ( ) ; //读取栈顶元素 void MakeEmpty ( ) { top=-1;} //置空栈，top=-1表示栈为空 int IsEmpty ( ) const { return top==-1;} //判栈空 int IsFull ( ) const { return top==maxSize-1;} //判栈满 private: //top=maxSize-1表示栈已满 int top;//栈顶指针（栈顶元素下标） Type * elements;//存储顺序栈的数组 int maxSize;//顺序栈的最大容量 } 顺序栈的基本操作（算法） （1）顺序栈初始化算法（构造函数） template class Type StackType::Stack(int s):top(-1),maxSize(s) //建立一个最大尺寸为 s 的空栈，若分配不成功则错误处理 { element=new Type[maxSize];//创建顺序栈空间（数组） assert( elements != 0); //断言语句：若条件成立，则继续；否则出错处理并终止执行 } （2）顺序栈入栈算法 template class Type void StackType::Push(const Type item) //若栈不满，则将元素 item 插入到栈顶，否则出错处理 { assert( ! IsFull());//断言：栈不满则继续执行 elements[++top]=item;//栈顶指针先加 1 ，然后按此地址进栈 } （3）顺序栈出栈算法 template class Type Type StackType::Pop() //若栈不空，则返回栈顶元素，并使栈顶指针退 1 ；否则出错处理 { assert( ! IsEmpty());//