第三章第三讲栈和对列

《第三章第三讲栈和对列》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三讲栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性线性表.ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)3.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈.特点：先进后出（FILO）或后进先出（LIFO）13.1.1顺序栈实现：一维数组s[1..M];top=0234561栈空栈顶指针top,指向实际栈顶元素位置，初值为0.top234561进栈Atop出栈栈满BCDEF设数组为s[

2、1..M];top=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop234561ABCDEFtoptop栈空2栈--结论：后进先出（LastInFirstOut），简称为LIFO线性表。举例1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。举例2：堆放在桌上的课本，在使用时，若一个一个地拿，一定最先拿走最上面的那本书，而最后拿出最下面的那本

3、书。3思考题：一个栈的输入序列为123，若在入栈的过程中允许出栈，不可能得到的出栈序列是什么？A)123；b)132；c)231；d)213；e)312;解：可以通过穷举所有可能性来求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入,3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；⑥…………………………312（不行）合计只有5种可能性。4下面我们再给出顺序栈结构的基本操作：（1）初始化栈InitSt

4、ack(S)（2）入栈Push(S,item)（3）出栈Pop(S,item)（4）获取栈顶元素内容GetTop(S,item)（5）判断栈是否为空StackEmpty(S)5栈的顺序存储的定义栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。类型定义如下所示：#defineMAX10//栈的最大数据元素数目typedefstructstack{charData[1..MAX];//存放栈中数据元素的存储单元inttop;//栈顶指针}STACK;6基本操作算法(简化)：

5、1.初始化栈SvoidInItStack(STACK*S){s->top=0;}/*s->top为栈顶指针,在顺序结构中既为数组下标*/2.入栈voidPush(STACK*S,DataTypex){if(S->top==MAX_STACK)exit(“Stackisfull”);elseS->Data[++(S->top)]=x;}出栈ana1a2……...s->top...进栈73.出栈voidPop(STACK*S){if(StackEmpty(S))exit(“Stackisempty”);retu

6、rnS->data[(S->top)];s->top--;}4.获取栈顶元素内容voidGetTop(STACK*S){if(StackEmpty(S))exit(“Stackisempty”);returnS->data[S->top];}ana1a2……...s->top...进栈85.判断栈S是否为空intStackEmpty(STACK*S){if(S->top==0)returnTRUE;elseFALSE;}结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数

7、据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。93.1.3线性表的链式存储(补充)栈顶^…...topdatalink栈底结点定义:typedefstructnode{intdata;structnode*next;}stack;Stacktop;//定义栈的栈顶指针10初始化栈SVoidInitStack(STACK*S){top=NULL;}链栈各项基本操作的算法:112.入栈简化算法^…...栈底toptopxpvoidPush(STACK*S,DataTypex){STACK*p=(N

8、ODE*)malloc(sizeof(NODE));P->data=x;p->next=top;top=p;}}122.出栈简化算法top^…...栈底topqvoidPop(Stack*S){DataTypex;stack*q;if(StackEmpty(top))exit(“Stackisempty”);else{x=top->data;q=top;top=q->next;free(q)}}134.获取栈顶元