ch03 Stack & Queue.ppt

《ch03 Stack & Queue.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈和队列本章内容3.1栈3.1.1栈的定义及基本运算3.1.2栈的存储结构和实现3.1.3栈的应用3.2队列3.2.1队列的定义及基本运算3.2.2队列的存储结构和实现3.2.3队列的应用3.1.1栈的定义及基本运算栈(Stack)的定义栈是仅限定在表尾进行插入和删除操作的线性表。术语栈顶(top)－－栈的表尾栈底(bottom)－－栈的表头空栈－－没有元素的栈入栈(push)－－向栈顶压入元素出栈(pop)－－从栈顶弹出元素anan-1...a2a1栈底栈顶入栈出栈栈的特点栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。3.1

2、.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。DCBAABCDDCBA3.1.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？ABCDE操作序列：出栈序列：①元素A入栈AA②元素B入栈BB③元素C入栈CC3.1.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E

3、得到出栈序列CBDAE？DE操作序列：出栈序列：①元素A入栈A②元素B入栈B③元素C入栈④元素C出栈CC⑤元素B出栈B3.1.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？DE操作序列：出栈序列：①元素A入栈A②元素B入栈③元素C入栈④元素C出栈C⑤元素B出栈B⑥元素D入栈DD⑦元素D出栈D⑧元素A出栈A3.1.1栈的定义及基本运算栈的运算演示(1)A、B、C、D四个元素依次进入一个栈，再依次出栈，得到一个输出序列DCBA。(2

4、)能否由入栈序列A、B、C、D、E得到出栈序列CBDAE？E操作序列：出栈序列：①元素A入栈②元素B入栈③元素C入栈④元素C出栈C⑤元素B出栈B⑥元素D入栈⑦元素D出栈D⑧元素A出栈A⑨元素E入栈EE⑩元素E出栈E栈的基本运算InitStack(&S):初始化栈SStackEmpty():判断栈是否为空Push(e):将元素e放入栈顶Pop(e):移走栈顶的元素，同时由e带回该元素的值Gettop():获取栈顶的元素，但不从栈中移走3.1.1栈的定义及基本运算3.1.2栈的存储结构和实现顺序栈－－栈的顺序存储结构…a1a2an-1an线性表anan-1..

5、.a2a1栈栈底栈顶6F28an6F26an-1......6F02a26F00a1栈的顺序存储映象basetop3.1.2栈的存储结构和实现顺序栈－－栈的顺序存储结构6F28an6F26an-1......6F02a26F00a1栈的顺序存储映象basetop顺序栈基本操作的实现StackEmpty():top==basePush(e):*top++=ePop(e):e=*--topGettop():e=*(top-1)思考：若令top指向栈顶元素，与上述方法有何区别？3.1.2栈的存储结构和实现顺序栈的C语言实现结构定义//-----栈的顺序存储表示-

6、----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{ElemType*base;//栈底指针，栈构造前和销毁后为空ElemType*top;//栈顶指针，指向栈顶元素的下一位置intstacksize;//当前分配的栈的存储空间数}SqStack;3.1.2栈的存储结构和实现顺序栈的C语言实现基本操作的实现(1)初始化StatusInitStack(SqStack&S){//构造一个空栈S.base=(ElemType*)malloc(STACK_INIT_SIZE*siz

7、eof(ElemType));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStack3.1.2栈的存储结构和实现顺序栈的C语言实现基本操作的实现(2)元素入栈StatusPush(SqStack&S,ElemTypee){//构造一个空栈if(S.top–S.base==S.stacksize)returnERROR;*S.top=e;S.top++;returnOK;}//Push请自学其他操作的实现算法。3.1.2栈的存储结构和实现

8、顺序栈的另一种实现结构定义//-----栈的顺序存储表示-----