计算机软件技术基础34-栈-课件

计算机软件技术基础3.4栈3.4栈一、栈的定义二、栈的运算三、栈的存储结构及算法四、栈的应用一、栈的定义栈是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。设栈s=(a1,a2,...,an)，a1称为栈底元素，an称为栈顶元素。栈中元素按a1,a2,...,an次序进栈，又按an,...,a2,a1次序退栈。因此栈的操作特点是：后进先出（LIFO）；n=0时称为空栈。anan-1a1stack[n-1]top

栈顶

进栈

stack[0]栈底

出栈二、栈的运算1.初始化栈 INISTACK(S)

将栈S置成空栈2.判空栈 ISEMPTY(S) 若栈S是空栈，返回“真”，

否则返回“假”3.进栈 PUSH(S,x) 在栈S顶部插入（压入）元素x4.出栈 POP(S) 若栈S不空，删除顶部元素5.取栈顶 GETTOP(S) 取栈顶元素，并不改变栈中内容三、栈的存储结构及算法1.顺序栈1)类型定义顺序栈用向量作为栈的存储结构，可用一维数组s[1:m]表示。其中m表示栈的最大容量。用一个简单变量top来指示栈顶位置，称为栈顶指示器。top=0表示栈空，top=m表示栈满。类型定义structSeqStack{ elemtypestack[MAXSIZE]; inttop;};三、栈的存储结构及算法2）顺序栈初始化

⑴操作:

建一空栈，将栈顶位设置为-1

⑵接口： 入口和出口参数均为堆栈指针s

⑶算法描述：令栈顶位s.top为-1

⑷函数实现：voidiniStack(SeqStack&s){ s.top=-1;} 三、栈的存储结构及算法3)进栈算法

⑴操作:先将栈顶位置加一将数据放入栈顶位置

⑵接口：

入口参数：堆栈指针s，新数据元素x出口参数:堆栈指针s函数值： 成功则返回1(用true表示),

失败则返回0(用false表示)三、栈的存储结构及算法 (3)算法描述大家学习辛苦了，还是要坚持继续保持安静三、栈的存储结构及算法(4)函数实现intpush(SeqStack&s,elemtypex){ if(s.top>=MAXSIZE-1)return(false); s.top++; s.stack[s.top]=x; return(true);} 三、栈的存储结构及算法4)出栈算法

(1)操作取栈顶位置内数据.再将栈顶位置减一(2)接口

入口参数：堆栈指针s出口参数:堆栈指针s函数值：成功则返回数据元素x,失败则返回NULL三、栈的存储结构及算法 (3)算法描述三、栈的存储结构及算法(4)函数实现elemtypepop(SeqStack&s){ if(s.top<0) returnNULL; s.top--; returns.stack[s.top+1];}三、栈的存储结构及算法5)双栈操作顺序栈的缺点：栈满后不能进行进栈操作，否则将产生“上溢”错误同时使用同类的两个栈，充分利用剩余空间 两栈共用一个存储空间，分别从两端向中间增长a1a2……

an……

bm……

b2b101n-1出栈MAXSIZE-m

MAXSIZE-2

MAXSIZE-1栈1底栈1顶入栈栈2顶栈2底三、栈的存储结构及算法2.链栈链栈是用链表作为栈的存储结构，top为栈顶指针，指示栈顶元素位置，若top=NULL,则表示栈空。链栈一般不会出现上溢，除非内存中已不存在可用空间。使用单链表，不设头结点插入和删除仅在表头一端栈顶top：指始结点，浮动空栈用top=NULL实现链栈结点动态分配，空间无限链栈定义与单链表相同

structlink*top；.a2top

aia1NULL四、栈的应用表达式求值

1）高级语言中的表达式是用人们熟悉的公式形式书写的，编译系统要根据表达式的运算顺序将它翻译成机器指令序列。

2）为解决运算顺序问题，把运算符分成若干等级，称为优先数。

3）为进行表达式的翻译，需设立两个栈，分别存放操作数(NS)和运算符(OS)。四、栈的应用4）首先在OS中放入表达式结束符“#”，然后自左至右扫描表达式，根据扫描的每一个符号作如下不同处理：①若为操作数，将其压入NS栈②若为运算符，需看当前OS的栈顶元素：若OS栈顶运算符小于或等于当前运算符的优先数，则将当前运算符压入OS栈。若OS栈顶运算符大于当前运算符的优先数，则从NS栈中弹出两个操作数，设为x、y，再从OS栈中弹出一个运算符，设为θ，由此构成一条机器指令：yθx→T，并将结果T送入NS栈。③若当前运算符为“#”，且OS栈顶也为“；”，则表示表达式处理结束，此时NS栈顶的元素即为此表达式的值。四、栈的应用5)算符优先+-*/()#+>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=四、栈的应用 6)函数实现doubleExp(){

inistack(OS);inistack(NS);//初始化栈OS和NS push(OS,’#’);//在OS栈中压入结束符

t=0;//t=0表示扫描下一个符号

while(t!=2){//当处理没有结束时循环

if(t==0)w=getchar();//读取一个符号

if(w为操作数)push(NS,w);//操作数压NS栈

else{

q=top(OS);//查看OS栈顶元素

if(q<=w){push(OS,w);t=0;}//不大于时

else{//处理结束,t=2

if(q==‘#’&&w==‘#’){z=pop(NS);t=2;}

else{//计算,t=1

x=pop(NS);y=pop(NS);

q=pop(OS);x=yqx;

push(NS,x);t=1;}}}}}inttop(seqstack&s)

{

if(s.top==-1)return(NULL);

return(s.data[s.top]);

}需编写函数实现四、栈的应用7)举例

设表达式为：3*(7-2)#

步骤操作符栈操作数栈输入字符操作1#3*(7-2)#压入“3”2#3*(7-2)#压入“*”3#*3(7-2)#压入“(”4#*(37-2)#压入“7”5#*(37-2)#压入“-”6#*(-372)#压入“2”7#*(-372)#弹出“-”压入7-28#*(35)#弹出“(”9#*35#计算3*510#15#操作符栈空，结束3.4栈五、小结

1、理解栈的概念和特点

2、掌握进/出栈的算法

3、了解栈的应用：表达式求值，背包问题3.5队列一、队列的定义及运算二、顺序队列三、链队列四、队列的应用3.5队列 一、队列的定义及基本操作1、队列的定义队是限定在表的一端进行插入，在表的另一端进行删除的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。队用移动rear和front指示器进行插入和删除。队中元素按a1,a2,…,an次序入队和出队。因此队的操作特点是：先进先出（FIFO）；n=0时称为空队。A1A2A3A4A5……An入队出队队头（front）队尾（rear）一、队列的定义及运算2、队列的基本操作初始化队列iniqueue(Q) 将队列Q置成空判空队列 empty(Q) 若队列Q是空，返回“真”，否则返回“假”入队列 enqueue(Q,x)在队列Q尾部插入元素x出队列 dlqueue(Q,x)若队列Q不空，删除头部元素取队头 gethead(Q,x)取队列Q头元素，但不改变队列Q中内容3.5队列 二、顺序队列顺序队用向量作为队的存储结构，可用一维数组Q[1:m]表示。其中m表示队的最大容量。初始状态rear=front=0，队空，入队时rear增1，出队时front增1，当front=rear时队空，当rear=m时无法再继续入队，但此时队中空间并不一定满(只有当rear-front=m时才真正满)，这种现象称为“假溢出”。rear=3front=3a5a4a3a2a1rear=5front=0a5a4rear=5front=3队空 队满 假溢出循环队列51

42

3rear=3front=5a1a2a3为避免假溢出的发生，我们假想把存放队列的数组形成一个头尾相接的环形，称为循环队列。二、顺序队列1、顺序队列的类型定义

structSeqQueue{ elemtypequeue[MAXSIZE+1]；

intfront；

intrear；

}Q; queue[0]不用，实际占用MAXSIZE个单元;队列空：队头=队尾，即front=rear队列满：队尾=MAX，即rear=MAXSIZE*注意：假满，若front≠0时，实际还有空间二、顺序队列解决方法：若将整个队列前挪，至队头front=0，花费太大。常用的是：循环队列：这种队列结构首尾相连,当尾指针rear=MAXSIZE时重指向1。(用rear=(rear+1)%MAXSIZE修改rear指针即可)由于queue[0]不用，因此当front=(rear+1)%MAXSIZE时队列为满;当front=rear时队列为空;不使用queue[0]就是为了能够比较方便地判断队列的空与满二、顺序队列2、顺序队列的初始化

⑴操作:

建一空队列，队头队尾均置零

⑵接口：队列指针q(q=&Q) ⑶算法描述：

q－>front=0;q－>rear=0; ⑷函数实现：

voidiniQueue(SeqQueue&q){ q.front=0; q.rear=0; }二、顺序队列3、循环队列的入队操作

⑴操作:若队列满，返回false(q->front=(q->rear+1)%MAXSIZE)队尾指针加一q->rear=(q->rear+1)%MAXSIZE将数据放入队尾q->queue[q->rear]=x返回true ⑵接口：

入口参数：队列指针q，新数据元素x出口参数:函数值：成功true;失败false二、顺序队列 (3)算法描述二、顺序队列(4)函数实现intenQueue(SeqQueue&q,elemtypex){ if(q.front=(q.rear+1)%MAXSIZE) return(false);//队列已满，入队错误

q.rear=(q.rear+1)%MAXSIZE;//更改尾指针

q.queue[q.rear]=x; //插入数据

return(true);}

二、顺序队列3、循环队列的出队操作

⑴操作:若队列空，返回NULL (q->front==q->rear)队头指针加一 q->front=(q->front+1)%MAXSIZE返回队头数据 q->queue[q->front] ⑵接口：入口参数：队列指针q，出口参数:函数返回值：成功：数据元素;失败返回NULL二、顺序队列 (3)算法描述二、顺序队列(4)函数实现elemtypedlQueue(SeqQueue&q){ if(q.front==q.rear) returnNULL; //队列为空，返回NULL q.front=(q.front+1)%MAXSIZE;//取队头元素

returnq.queue[q.front];}3.5队列 三、链队列链队列是用链表作队列的存储结构，当队列的容量无法预先估计时采用。在链队列中设一个头结点，头指针front始终指向头结点，尾指针rear指向队尾元素，当rear=front表时队空。结点动态分配，不会溢出链队列结点定义与单链表一样qdata指针data指针data指针data指针frontrearQSqdata指针data指针data指针data指针frontrearQS三、链队列1、结点结构定义:structLNode{ elemtype