《栈和队列》PPT课件

《《栈和队列》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、3.1栈　　　　　　　　　　　　　　　　　　　第3章栈和队列栈(Stack)是限定仅在表的一端（一般指表尾）进行插入和删除操作的线性表。允许插入、删除的这一端称为栈顶(Top)，另一端称为栈底(Bottom)。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。3.1栈数据结构第3章栈和队列假设栈S=(a0，a1，a2，…an-1)，则a0称为栈底元素，an-1称为栈顶元素。栈中元素按a0，a1，a2，…an-1的次序入栈，出栈的第一个元素应为栈顶元素an-1。也就是说，栈的操作是按后进先出

2、的原则进行的。因此，栈又称为后进先出（LastInFirstOut）的线性表（简称LIFO表）。入栈出栈栈底栈顶an-1···a1a03.1栈数据结构第3章栈和队列栈的基本运算如下：⑴InitStack(s)：栈初始化。初始条件：栈s不存在操作结果：构造了一个空栈。⑵StackEmpty(s)：判栈空。初始条件：栈s已存在操作结果：若s为空栈则返回1，否则返回0。⑶Push(s，e)：入栈。初始条件：栈s已存在操作结果：在栈s的顶部插入一个新元素e，e成为新的栈顶元素。栈发生变化。3.1栈数据结构第3章栈和队列⑷Pop(s，

3、e)：出栈。初始条件：栈s存在且非空操作结果：将栈s的栈顶元素从栈中删除，并用e返回其值。栈发生变化。⑸GetTop(s，e)：读栈顶元素。初始条件：栈s存在且非空操作结果：读栈顶元素并用e返回其值。栈不变化。栈是一种特殊的线性表，因此栈也可采用两种存储结构：顺序存储结构链式存储结构3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列1.顺序栈（1）顺序栈的存储结构顺序栈是指采用顺序存储结构存储的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针（下标）top，指示栈顶元素的当前位置。对于用C

4、语言描述的顺序栈通常用top=-1表示空栈；入栈时，栈顶指针top增1；出栈时，栈顶指针top减1。3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列topEDCCBBAAAtoptoptop顺序栈的类型定义如下：#defineMAXSIZE100typedefintElemType;typedefstructstack{ElemTypeelem[MAXSIZE];//存栈顺序表inttop;　//栈顶下标}SQSTACK;3.2栈的存储结构及其基本运算的实现

5、数据结构第3章栈和队列（2）顺序栈的基本操作①栈的初始化（即构造一个空栈）voidInitStack(SQSTACK*ps){ps->top=-1;}②判栈空intStackEmpty(SQSTACKs){if(s.top==-1)return1;elsereturn0;}3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列③入栈intPush(SQSTACK*ps,ElemTypee){if(ps->top==MAXSIZE-1)//判栈满{cout<<"Stackisfull“<

6、>top++;ps->elem[ps->top]=e;return0;}3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列④出栈intPop(SQSTACK*ps,ElemType*pe){if(ps->top==-1)//判栈空{cout<<"Stackisempty“<elem[ps->top];ps->top--;return0;}3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列⑤读取栈顶元素intGetTop(SQSTACKs,ElemType*pe){

7、if(s.top==-1)//判栈空{printf("Stackisempty");return1;}*pe=s.elem[s.top];return0;}3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列2.链栈（1）链栈的存储结构链栈是指采用链式存储结构存储的栈。链栈是一种特殊的单链表，即限定仅在表头进行插入和删除操作的单链表，因此链栈的结点结构与单链表的结点结构相同。3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列a1a2an∧topdatanext栈顶栈底…（1）链栈中指针的方向是从栈顶指向栈底

8、（区别于顺序栈，顺序栈是将表尾作为栈顶）。（2）链栈中没必要附加一个表头结点（因为在表头进行插入、删除操作，带头结点和不带头结点都是一样的）。3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列3.2栈的存储结构及其基本运算的实现数据结构第3章栈和队列链栈的类型定义如下：typede