数据结构栈和队列.pptx

《数据结构栈和队列.pptx》由会员分享，可在线阅读，更多相关《数据结构栈和队列.pptx（41页珍藏版）》请在优知文库上搜索。

1、数据结构数据结构西安高新学院 数据结构与算法数据结构数据结构西安高新学院一、线性结构（二）栈和队列数据结构数据结构西安高新学院1.1.定义定义与线性表相同，仍为一对一与线性表相同，仍为一对一( 1:1)关系关系。用用顺序栈顺序栈或或链栈链栈存储均可，但以顺序栈更常见存储均可，但以顺序栈更常见只能在只能在运算，且访问结点时依照运算，且访问结点时依照（LIFOLIFO）或或（FILOFILO）的原则。）的原则。关键是编写关键是编写和和函数，具体实现依顺序栈或链函数，具体实现依顺序栈或链栈的存储结构有别而不同。栈的存储结构有别而不同。3. 存储结构存储结构4. 运算规则运算规则5. 实现方式实现方式

2、 2. 逻辑结构逻辑结构限定只能在表的限定只能在表的进行插入和删除运算的线性表。进行插入和删除运算的线性表。即栈顶即栈顶基本操作有基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值等。建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值等。数据结构数据结构西安高新学院q顺序栈的存储结构top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptop

3、toptoptoptop栈空数据结构数据结构西安高新学院 a1 a2 an顺序栈顺序栈S aiQ Q：顺序表和顺序栈的操作有何区别？：顺序表和顺序栈的操作有何区别？表头表头表尾表尾低地址低地址高地址高地址写入：写入：Si= ai读出：读出： e= Si压入压入(SS+=an+1弹出弹出( - 低地址低地址高地址高地址Si a1 a2 ai an 顺序表顺序表S an+1以线性表以线性表 S= (a1 , a2 , . , an-1 , an )为例为例栈底栈底栈顶栈顶数据结构数据结构西安高新学院例1 一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？答：答：

4、可以通过穷举所有可能性来求解：可以通过穷举所有可能性来求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合计有合计有5 5种可能性。种可能性。数据结构数据结构西安高新学院例例2 2：一个栈的输入序列是

5、一个栈的输入序列是12345，若在，若在入栈的过程中允许入栈的过程中允许出栈出栈，则栈的输出序列则栈的输出序列43512可能实现吗可能实现吗？12345的输出的输出呢？呢？答：答：4351243512不可能实现，主要是其中的不可能实现，主要是其中的1212顺序不能实现；顺序不能实现；1234512345的输出可以实现，每压入一数便立即弹出即可。的输出可以实现，每压入一数便立即弹出即可。 数据结构数据结构西安高新学院例例3：设依次进入一个栈的元素序列为c、a、b、d，则可得到出栈的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，bA）、）、D）可以，）可以， B

6、）、）、C）不行。）不行。讨论：有无讨论：有无通用的判别原则通用的判别原则？有！若输入序列是有！若输入序列是 ,P,Pj jP Pk kP Pi i (P(Pj jPPk kP0) k=n%d ; push(S , k) ; n=n/d ; /* 求出所有的余求出所有的余数，数，进栈进栈 */while (S.top!=0) /* 栈不空时出栈，输出栈不空时出栈，输出 */ pop(S, e) ; printf(“%1d” , *e) ; 数据结构数据结构西安高新学院栈的应用二：栈的应用二： （2）括号匹配 在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配?

7、匹配思想匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号每个右括号将与最近遇到的那个左括号相匹配。将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。算法思想算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。数据结构数据结构西安高新学院 栈的另一个重要应用是在程序设计语言中实现递归调用。栈的另一个重要应用是在程序设计语言中实现递归调用。 递归调用：递归

8、调用：一个函数一个函数( (或过程或过程) )直接或间接地调用自己本身，直接或间接地调用自己本身，简称简称递归递归( (RecursiveRecursive) )。 栈的应用三：栈的应用三： （3）递归处理例如：求求n!n!Fact(n)=1 当当n=0时时 终止条件终止条件n*fact(n-1) 当当n0时时 递推规则递推规则数据结构数据结构西安高新学院 栈是在同一端进行插入和删除运算的线性表，具有先进后出的特性。栈的这种特性正好适用函数嵌套调用（递归）的过程。 (1)调用函数时：系统将为调用者构造一个由参数表和返回地址组成等信息的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程

9、序的控制权转移到被调函数。 (2)被调函数执行完毕时：系统将运行时刻栈顶的活动记录退栈，并根据退栈的活动记录中所保存的返回地址将程序的控制权转移给调用者继续执行。数据结构数据结构西安高新学院栈的应用四：栈的应用四： （4）表达式求值46+5*（120-37）46 5 120 37 - * +后缀表达式1234046512037- 37120= 8383*835= 415415+41546 = 461461数据结构数据结构西安高新学院与线性表相同，仍为一对一关系与线性表相同，仍为一对一关系。顺序队顺序队或或链队链队，以，以循环顺序队循环顺序队更常见。更常见。只能在队首和队尾运算，且访问结点时依照

10、只能在队首和队尾运算，且访问结点时依照先进先先进先出出（FIFOFIFO）的原则。的原则。关键是掌握关键是掌握入队入队和和出队出队操作，具体实现依顺序队或操作，具体实现依顺序队或链队的不同而不同。链队的不同而不同。只能在表的一端进行插入运算，在表的另一端进行删除只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。运算的线性表。基本操作基本操作：入队或出队，建空队列，判队空或队满等操作。入队或出队，建空队列，判队空或队满等操作。尾部插入尾部插入首部删除首部删除数据结构数据结构西安高新学院队列队列 （Queue）是仅在是仅在表尾表尾进行插入操作，在进行插入操作，在表头表头进行删除操进行删

11、除操作的线性表。它是一种先进先出作的线性表。它是一种先进先出（）（）的线性表。的线性表。在队尾插入元素称为入队；在队首删除元素称为出队。在队尾插入元素称为入队；在队首删除元素称为出队。问：为什么要设计队列？它有什么独特用途？问：为什么要设计队列？它有什么独特用途？1. 离散事件的模拟离散事件的模拟（模拟事件发生的先后顺序（模拟事件发生的先后顺序, ,例如例如 CPUCPU芯片中的芯片中的指令译码队列）指令译码队列）；2. 操作系统中的作业调度操作系统中的作业调度（一个（一个CPUCPU执行多个作业）执行多个作业）等类似的事件。等类似的事件。答：答：a1 a2 a3.an 入队出队frontre

12、ar队列Q=(a1,a2,an)数据结构数据结构西安高新学院（1）队列的顺序存储结构：用一维数组sqM实现front=0rear=0123450队空123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6frontrear指示队尾元素后一位置front指示队头元素位置初值front=rear=0入队列：sqrear+=x;出队列：x=sq+front;空队列条件：front=rearrearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfrontrearrearrear 假溢出！数据结构数据结

13、构西安高新学院【存在问题】【存在问题】设数组长度为M，则：u 当front=0,rear=M时，再有元素入队发生溢出真溢出u 当front0,rear=M时，再有元素入队发生溢出假溢出【解决方案】【解决方案】u 队首固定，每次出队剩余元素向下移动浪费时间u 循环队列：把队列设想成环形，让sq0接在sqM-1之后， 若rear+1=M， 则令rear=0;a3a2a10123M-1rearfronta3a2a1frontrear 0 1 2 3 . .M-1实现：利用“模”运算入队：sqrear=x; rear=(rear+1)%M; 出队：x=sqfront; front=(front+1)%

14、M; 数据结构数据结构西安高新学院新问题：在循环队列中，空队特征是在循环队列中，空队特征是front=rear；队满时也会有队满时也会有front=rear；判决条件将出现二义性！判决条件将出现二义性！a3a2a10123N-1rearfront解决方案：使用一个使用一个计数器计数器记录队列中元素个数记录队列中元素个数（即队列长度）；（即队列长度）；加加设标志位设标志位，删除时置，删除时置1 1，插入时置，插入时置0 0，则可识别当前则可识别当前front=rear属于何种情况；属于何种情况； 人为人为浪费一个单元浪费一个单元，则队满特征可改，则队满特征可改为为front=(rear+1)%N

15、；数据结构数据结构西安高新学院l 队空条件队空条件 : front = rear (初始化时：初始化时：front = rear )l 队满条件队满条件： front = (rear) % N (N=maxsize)l 队列长度队列长度（即数据元素个数）（即数据元素个数）：L=（Nrearfront）% N J3 J4J2 J5 J6frontrear 常选用常选用方案方案3（人为浪费一个单元）人为浪费一个单元）：即即rear所指的单元始终为空。所指的单元始终为空。问问3： 在具有在具有n个单元的循环队列个单元的循环队列中，队满时共有多少个元素？中，队满时共有多少个元素？ n-1个个6 问问1

16、：左图中队列左图中队列maxsize N=？问问2：左图中队列左图中队列长度长度L=？5501234数据结构数据结构西安高新学院（）（） rf （）（）（nfr）% n （）（）nrf （）（） （nrf）% n例：例：数组数组n用来表示一个循环队列，用来表示一个循环队列，f 为当前队列头指针位为当前队列头指针位置，置，r 为尾指针位置。假定队列中元素的个数小于为尾指针位置。假定队列中元素的个数小于n，计算队，计算队列中元素的公式为列中元素的公式为:数据结构数据结构西安高新学院例：例： 一循环队列如下图所示，若先删除一循环队列如下图所示，若先删除4个元素，接着再插入个元素，接着再插入4个元个元素，请问队头和队尾指针分别指向哪个位置素，请问队头和队尾指针分别指向哪个位置? J2 J3J1 J4 J5front=1rear=0解：解：由图可知，队头和队尾指针的初态分别为由图可知，队头和队尾指针的初态分别为front=1和和rear=0。删除删除4个元素后个元素后front=5；再插入再插入4个元素后，个元素后，rear=(0+4)%6=4 front=5J6 J5J7J8 J9rear=4