队列讲-定义顺序.pptx

第3章栈和队列;栈是一种只能在一端进行插入或删除操作的线性表。;允许进行插入、删除操作的一端称为栈顶。

表的另一端称为栈底。

当栈中没有数据元素时，称为空栈。

栈的插入操作通常称为进栈或入栈。

栈的删除操作通常称为退栈或出栈。;栈的主要特点是“后进先出”，即后进栈的元素先出栈。栈也称为后进先出表。;思考题：

栈和线性表有什么不同？;【例（补充）】设一个栈的输入序列为a，b，c，d，则借助一个栈所得到的输出序列不可能是。

A.c，d，b，a B.d，c，b，a

C.a，c，d，b D.d，a，b，c;【例3-3】一个栈的入栈序列为1，2，3，…，n，其出栈序列是p1，p2，p3，…，pn。若p2=3，则p3可能取值的个数是。

A.n-3B.n-2C.n-1D.无法确定;栈的几种基本运算如下:;栈中元素逻辑关系与线性表的相同，栈可以采用与线性表相同的存储结构。;3.1.2栈的顺序存储结构及其基本运算实现;;;;;（2）销毁栈DestroyStack(s)

释放栈s占用的存储空间。;（3）判断栈是否为空StackEmpty(s)

栈S为空的条件是s-top==-1。;（4）进栈Push(s，e)

在栈不满的条件下，先将栈指针增1，然后在该位置上插入元素e。;（5）出栈Pop(s，e)

在栈不为空的条件下，先将栈顶元素赋给e，然后将栈指针减1。;（6）取栈顶元素GetTop(s，e)

在栈不为空的条件下，将栈顶元素赋给e。;【例3-3】设计一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。;boolsymmetry(ElemTypestr[])

{inti;ElemTypee;SqStack*st;

InitStack(st); //初始化栈

for(i=0;str[i]!=\0;i++) //将串所有元素进栈

Push(st，str[i]); //元素进栈

for(i=0;str[i]!=\0;i++)

{Pop(st，e); //退栈元素e

if(str[i]!=e) //若e与当前串元素不同则不是对称串

{DestroyStack(st); //销毁栈

returnfalse;

}

}

DestroyStack(st); //销毁栈

returntrue;

};如果需要用到两个相同类型的栈，可以用一个数组data[0..MaxSize-1来实现这两个栈，这称为共享栈。;━━本讲完━━