计算机软件技术基础 课件.ppt
计算机软件技术基础,教 师：曾晓东电 话：13679007201E_mail: zengxiaodong263.net,3.4 栈,一、栈的定义二、栈的运算三、栈的存储结构及算法四、栈的应用,计算机软件技术基础,数据结构栈和队列,一、栈的定义,栈是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。设栈s=(a1,a2,.,an)，a1称为栈底元素，an称为栈顶元素。栈中元素按a1,a2,.,an次序进栈，又按an,.,a2,a1次序退栈。因此栈的操作特点是：后进先出（LIFO）；n=0时称为空栈。,计算机软件技术基础,数据结构栈和队列,二、栈的运算,1.初始化栈INISTACK(S)将栈S置成空栈2.判空栈ISEMPTY(S)若栈S是空栈，返回“真”，否则返回“假”3.进栈PUSH(S,x) 在栈S顶部插入（压入）元素x4.出栈POP(S) 若栈S不空，删除顶部元素5.取栈顶GETTOP(S)取栈顶元素，并不改变栈中内容,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,1.顺序栈1)类型定义顺序栈用向量作为栈的存储结构，可用一维数组s1:m表示。其中m表示栈的最大容量。用一个简单变量top来指示栈顶位置，称为栈顶指示器。top=0表示栈空，top=m表示栈满。类型定义struct SeqStackelemtype stackMAXSIZE;int top;,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,2）顺序栈初始化 操作:建一空栈，将栈顶位设置为-1 接口：入口和出口参数均为堆栈指针s 算法描述：令栈顶位 s.top为-1 函数实现：void iniStack(SeqStack ,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,3)进栈算法 操作:先将栈顶位置加一将数据放入栈顶位置 接口： 入口参数：堆栈指针s，新数据元素x出口参数: 堆栈指针s函数值：成功则返回 1 ( 用true表示), 失败则返回 0 ( 用false表示),计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,(3)算法描述,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,(4) 函数实现int push(SeqStack ,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,4)出栈算法(1) 操作取栈顶位置内数据.再将栈顶位置减一(2) 接口 入口参数：堆栈指针s出口参数: 堆栈指针s函数值： 成功则返回数据元素x, 失败则返回NULL,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,(3) 算法描述,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,(4) 函数实现elemtype pop(SeqStack ,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,5)双栈操作顺序栈的缺点：栈满后不能进行进栈操作，否则将产生“上溢”错误同时使用同类的两个栈，充分利用剩余空间两栈共用一个存储空间，分别从两端向中间增长,计算机软件技术基础,数据结构栈和队列,三、栈的存储结构及算法,2.链栈链栈是用链表作为栈的存储结构，top为栈顶指针，指示栈顶元素位置，若top=NULL,则表示栈空。链栈一般不会出现上溢，除非内存中已不存在可用空间。使用单链表，不设头结点插入和删除仅在表头一端 栈顶top ：指始结点，浮动空栈用 top=NULL 实现 链栈结点动态分配，空间无限链栈定义与单链表相同 struct link *top；,.,计算机软件技术基础,数据结构栈和队列,四、栈的应用,表达式求值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)函数实现double Exp()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=#,int top(seqstack ,需编写函数实现,计算机软件技术基础,数据结构栈和队列,四、栈的应用,7)举例设表达式为： 3*(7-2)# 步骤 操作符栈 操作数栈 输入字符 操作1 # 3*(7-2)# 压入“3”2 # 3 *(7-2)# 压入“*”3 #* 3 (7-2)# 压入“(”4 #*( 3 7-2)# 压入“7”5 #*( 3 7 -2)# 压入“-”6 #*(- 3 7 2)# 压入“2”7 #*(- 3 7 2 )# 弹出“-”压入7-28 #*( 3 5 )# 弹出“(”9 #* 3 5 # 计算3*510 # 15 # 操作符栈空，结束,计算机软件技术基础,数据结构栈和队列,3.4 栈,五、小结1、理解栈的概念和特点2、掌握进/出栈的算法3、了解栈的应用：表达式求值，背包问题,计算机软件技术基础,数据结构栈和队列,3.5 队列,一、队列的定义及运算二、顺序队列三、链队列四、队列的应用,计算机软件技术基础,数据结构栈和队列,3.5 队列,一、队列的定义及基本操作1、队列的定义队是限定在表的一端进行插入，在表的另一端进行删除的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。队用移动rear和front指示器进行插入和删除。队中元素按a1,a2,an次序入队和出队。因此队的操作特点是：先进先出（FIFO）；n=0时称为空队。,计算机软件技术基础,数据结构栈和队列,一、队列的定义及运算,2、队列的基本操作初始化队列iniqueue(Q)将队列Q置成空判空队列 empty(Q) 若队列Q是空，返回“真”，否则返回“假”入队列enqueue(Q,x)在队列Q尾部插入元素x出队列dlqueue(Q,x)若队列Q不空，删除头部元素取队头gethead(Q,x)取队列Q头元素，但不改变队列Q中内容,计算机软件技术基础,数据结构栈和队列,3.5 队列,二、顺序队列顺序队用向量作为队的存储结构，可用一维数组Q1:m表示。其中m表示队的最大容量。初始状态rear=front=0，队空，入队时rear增1，出队时front增1，当front=rear时队空，当rear=m时无法再继续入队，但此时队中空间并不一定满(只有当rear-front=m时才真正满)，这种现象称为“假溢出”。,为避免假溢出的发生，我们假想把存放队列的数组形成一个头尾相接的环形，称为循环队列。,计算机软件技术基础,数据结构栈和队列,二、顺序队列,1、顺序队列的类型定义struct SeqQueue elemtype queueMAXSIZE+1；int front； int rear；Q;queue0不用，实际占用MAXSIZE个单元;队列空：队头=队尾，即 front=rear队列满：队尾=MAX，即 rear=MAXSIZE * 注意：假满，若 front0时，实际还有空间,计算机软件技术基础,数据结构栈和队列,二、顺序队列,解决方法： 若将整个队列前挪，至队头front=0，花费太大。常用的是：循环队列：这种队列结构首尾相连,当尾指针 rear=MAXSIZE 时重指向1。(用rear=(rear+1)%MAXSIZE修改rear指针即可)由于queue0不用，因此当front= (rear+1)%MAXSIZE时队列为满;当front= rear时队列为空;不使用queue0就是为了能够比较方便地判断队列的空与满,计算机软件技术基础,数据结构栈和队列,二、顺序队列,2、顺序队列的初始化 操作: 建一空队列，队头队尾均置零 接口： 队列指针q (q=,计算机软件技术基础,数据结构栈和队列,二、顺序队列,3、循环队列的入队操作 操作:若队列满，返回false (q->front=(q->rear+1)%MAXSIZE)队尾指针加一 q->rear = (q->rear+1)%MAXSIZE将数据放入队尾 q->queueq->rear=x返回true 接口： 入口参数：队列指针q，新数据元素x出口参数: 函数值：成功true;失败false,计算机软件技术基础,数据结构栈和队列,二、顺序队列,(3)算法描述,计算机软件技术基础,数据结构栈和队列,二、顺序队列,(4)函数实现int enQueue(SeqQueue ,计算机软件技术基础,数据结构栈和队列,二、顺序队列,3、循环队列的出队操作 操作:若队列空，返回NULL(q->front= q->rear )队头指针加一q->front=(q->front+1)%MAXSIZE返回队头数据q->queueq->front 接口： 入口参数：队列指针q，出口参数: 函数返回值：成功：数据元素;失败返回NULL,计算机软件技术基础,数据结构栈和队列,二、顺序队列,(3)算法描述,计算机软件技术基础,数据结构栈和队列,二、顺序队列,(4)函数实现elemtype dlQueue(SeqQueue ,计算机软件技术基础,数据结构栈和队列,3.5 队列,三、链队列链队列是用链表作队列的存储结构，当队列的容量无法预先估计时采用。在链队列中设一个头结点，头指针front始终指向头结点，尾指针rear指向队尾元素，当rear=front表时队空。结点动态分配，不会溢出链队列结点定义与单链表一样,q,计算机软件技术基础,数据结构栈和队列,三、链队列,1、结点结构定义:struct LNode elemtype data;/ 数据域LNode *next; / 指针域;链队列结构定义:struct LinkQueue LNode *front, *rear;/ 队头、队尾指针;,计算机软件技术基础,数据结构栈和队列,三、链队列,2、插入int enQueue(LinkQueue /失败,计算机软件技术基础,数据结构栈和队列,三、链队列,3、删除void dlQueue(LinkQueue ,计算机软件技术基础,数据结构栈和队列,3.5 队列,四、队列的应用任务调度打印任务多用户资源竞争问题主机与外设速度不匹配问题消息队列排队模拟,计算机软件技术基础,数据结构栈和队列,3.5 队列,五、小结1、理解队列的概念和特点2、理解队的假溢出现象3、掌握循环队列判断空和满的条件4、掌握进/出队列的算法,计算机软件技术基础,数据结构栈和队列,
