《数据结构栈和队列.pptx》由会员分享，可在线阅读，更多相关《数据结构栈和队列.pptx（41页珍藏版）》请在三一办公上搜索。
1、数据结构与算法,一、线性结构,（二）栈和队列,1.定义,2.1 栈,与线性表相同，仍为一对一(1:1)关系。,用顺序栈或链栈存储均可，但以顺序栈更常见,只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。,关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。,限定只能在表的一端进行插入和删除运算的线性表。,即栈顶,基本操作有：建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值等。,顺序栈的存储结构,栈顶指针top,指向实际栈顶后的空位置，初值为0,top,进栈,A,top,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=0,栈空，此时出栈，则下
2、溢（underflow)top=M,栈满，此时入栈，则上溢（overflow),top,top,top,top,top,top,top,top,top,top,top,栈空,Q：顺序表和顺序栈的操作有何区别？,写入：Si=ai读出：e=Si,压入(PUSH):Stop+=an+1弹出(POP):e=S-top,an+1,以线性表 S=(a1,a2,.,an-1,an)为例,例1 一个栈的输入序列为1,2,3，若在入栈的过程中允许出栈，则可能得到的出栈序列是什么？,答：,可以通过穷举所有可能性来求解：1入1出，2入2出，3入3出，即123；1入1出，2、3入，3、2出，即132；1、2入，2出，
3、3入3出，即231；1、2入，2、1出，3入3出，即213；1、2、3入，3、2、1出，即321；合计有5种可能性。,例2：一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,答：,43512不可能实现，主要是其中的12顺序不能实现；12345的输出可以实现，每压入一数便立即弹出即可。,例3：,设依次进入一个栈的元素序列为c、a、b、d，则可得到出栈的元素序列是：）a，b，c，d）c，d，a，b）b，c，d，a）a，c，d，b,A）、D）可以，B）、C）不行。,讨论：有无通用的判别原则？有！若输入序列是,PjPkPi(PjPkPi)
4、，一定不存在这样的输出序列,PiPjPk,答：,即对于输入序列1，2，3，不存在输出序列3，1，2,基本操作：,入栈、出栈、建栈初始化、判断栈满或栈空、读栈顶元素值,InitStack（&s）操作结果：构造一个空栈DestroyStack(&s)初始条件：栈s已经存在操作结果：栈s被销毁ClearStack（&s）初始条件：栈s已经存在操作结果：将s清为空,isEmpty(s)初始条件：栈s已经存在操作结果：若栈为空栈，则返回TRUE,否则FALSEStackLength（s）初始条件：栈s已经存在操作结果：返回栈的元素个数，即栈的长度,GetTop（s,&e）初始条件：栈s已经存在且非空操作
5、结果：用e返回s的栈顶元素Push（&s,e）初始条件：栈s已经存在且非空操作结果：插入元素e为新的栈顶元素Pop（&s,&e）初始条件：栈s已经存在且非空操作结果：删除s的栈顶元素，并用e返回其值,(1)链栈的构造方式以头指针为栈顶，在头指针处插入或删除。,栈顶,栈底,链栈：用链式结构来表示的栈,链栈中每个结点由两个域构成：data域和next域，其定义为：,typedef Struct SNode SElemType data;Struct SNode*next;Node;,链栈一般不会出现栈满（上溢）情况，除非没有空间导致malloc分配失败。链栈的入栈、出栈操作就是栈顶的插入与删除操作
6、，修改指针即可完成。链栈是运算受限的单链表。,（2）链栈说明,栈的应用,由于栈具有的“后进先出”的固有特性，因此，栈成为程序设计中常用的工具和数据结构。以下是几个栈应用的例子。,栈的应用一：（1）数制转换,十进制整数 n 向其它进制数 d(二、八、十六)的转换是计算机实现计算的基本问题。转换法则：对应于一个简单算法原理 n=(n div d)*d+n mod d 其中：div为整除运算,mod为求余运算,例如(159)10=(？)8，其运算过程如下:n n div 8 n mod 8 159 19 7 19 2 3 2 0 2,采用顺序栈方式实现 void conversion(int n,i
7、nt d)/*将十进制整数n转换为d(2或8)进制数*/SqStack S;int k,*e;S=Init_Stack();while(n0)k=n%d;push(S,k);n=n/d;/*求出所有的余数，进栈*/while(S.top!=0)/*栈不空时出栈，输出*/pop(S,e);printf(“%1d”,*e);,栈的应用二：（2）括号匹配,在文字处理软件或编译程序设计时，常常需要检查一个字符串或一个表达式中的括号是否相匹配?匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括
8、号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。算法思想：设置一个栈，当读到左括号时，左括号进栈。当读到右括号时，则从栈中弹出一个元素，与读到的左括号进行匹配，若匹配成功，继续读入；否则匹配失败，返回FLASE。,栈的另一个重要应用是在程序设计语言中实现递归调用。递归调用：一个函数(或过程)直接或间接地调用自己本身，简称递归(Recursive)。,栈的应用三：（3）递归处理,例如：求n!,栈是在同一端进行插入和删除运算的线性表，具有先进后出的特性。栈的这种特性正好适用函数嵌套调用（递归）的过程。(1)调用函数时：系统将为调用者构造一个由参数表和返回地址组成等信息的活动记
9、录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。(2)被调函数执行完毕时：系统将运行时刻栈顶的活动记录退栈，并根据退栈的活动记录中所保存的返回地址将程序的控制权转移给调用者继续执行。,栈的应用四：（4）表达式求值,46+5*（120-37）,46 5 120 37-*+,后缀表达式,46,5,120,37,-,37,120,=83,83,*,83,5,=415,415,+,415,46,=461,461,2.2 队列,与线性表相同，仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握
10、入队和出队操作，具体实现依顺序队或链队的不同而不同。,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。,基本操作：入队或出队，建空队列，判队空或队满等操作。,尾部插入,首部删除,队列定义,队列（Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（）的线性表。,在队尾插入元素称为入队；在队首删除元素称为出队。,问：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）；操作系统中的作业调度（一个CPU执行多个作业）等类似的事件。,答：,（1）队列的顺序存储结构：用一维数组sqM实现,J1,J2,
11、J3,rear,rear,J4,J5,J6入队,J4,J5,J6,front,rear指示队尾元素后一位置front指示队头元素位置初值front=rear=0,入队列：sqrear+=x;出队列：x=sq+front;空队列条件：front=rear,rear,rear,front,front,front,front,rear,rear,rear,假溢出！,【存在问题】设数组长度为M，则：当front=0,rear=M时，再有元素入队发生溢出真溢出当front0,rear=M时，再有元素入队发生溢出假溢出【解决方案】队首固定，每次出队剩余元素向下移动浪费时间循环队列：把队列设想成环形，让sq
12、0接在sqM-1之后，若rear+1=M，则令rear=0;,实现：利用“模”运算入队：sqrear=x;rear=(rear+1)%M;出队：x=sqfront;front=(front+1)%M;,新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear；判决条件将出现二义性！,解决方案：使用一个计数器记录队列中元素个数（即队列长度）；加设标志位，删除时置1，插入时置0，则可识别当前front=rear属于何种情况；人为浪费一个单元，则队满特征可改为front=(rear+1)%N；,队空条件:front=rear(初始化时：front=rear)队满条件：f
13、ront=(rear+1)%N(N=maxsize)队列长度（即数据元素个数）：L=（Nrearfront）%N,常选用方案3（人为浪费一个单元）：即rear所指的单元始终为空。,问3：在具有n个单元的循环队列中，队满时共有多少个元素？,n-1个,6,问1：左图中队列maxsize N=？,问2：左图中队列长度L=？,5,（）rf（）（nfr）%n（）nrf（）（nrf）%n,例：数组n用来表示一个循环队列，f 为当前队列头指针位置，r 为尾指针位置。假定队列中元素的个数小于n，计算队列中元素的公式为:,例：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向
14、哪个位置?,解：由图可知，队头和队尾指针的初态分别为front=1和rear=0。,删除4个元素后front=5；,再插入4个元素后，rear=(0+4)%6=4,front=5,rear=4,rear=0,front=5,建队核心语句：q.base=(QElemType*)malloc(sizeof(QElemType）*MAXQSIZE);/为整个队列分配空间,#define MAXQSIZE 100/最大队列长度 typedef struct QElemType*base;/队列的基址 int front;/队首指针 int rear;/队尾指针 SqQueue,顺序队类型定义,循环队列
15、的基本操作,1）初始化一个空队列,算法要求：生成一空队列算法操作：为队列分配基本容量空间 设置队列为空队列，其特征即：front=rear=0,建队的完整算法：,Status InitQueue(SqQueue,算法说明：向循环队列的队尾插入一个元素分析：(1)插入前应当先判断队列是否满？if(q.rear+1)%MAXQSIZE)=q.front)return ERROR;(2)插入动作 q.base q.rear=e;q.rear=(q.rear+1)%MAXQSIZE;,2）入队操作,队列尺寸,Status EnQueue(SqQueue,入队操作完整算法,rear指针在元素入队后再加,
16、3）出队操作,算法说明：删除队头元素，返回其值 e 分析：（1）在删除前应当判断队列是否空？if(q.front=q.rear)return ERROR;（2）删除动作分析；前面约定队头front指向队首元素的位置，故：e=q.base q.front;q.front=(q.front+1)%MAXQSIZE;,front指针在元素出队后再加,Status DeQueue(SqQueue/DeQueue,出队操作完整算法,（2）链队列,队首指针front指向头结点，队尾指针rear指向队尾,链队列类型定义：typedef struct QueuePtr front;/队首指针 QueuePtr
17、 rear;/队尾指针 LinkQueue;,结点类型定义：typedef Struct QNode QElemType data;/元素 Struct QNode*next;/指向下一结点的指针 Qnode,*QueuePtr;,关于整个链队的总体描述,链队中任一结点的结构,讨论：空链队的特征？,怎样实现链队的入队和出队操作？,链队会满吗？,Q.front=Q.rear,一般不会，因为删除时有free动作。除非内存不足！,入队（尾部插入）：Q.rear-next=S;Q.rear=S;S-next=NULL出队（头部删除）：Q.front-next=p-next;,链队示意图：,在程序的执行
18、过程中，用_结构可以实现嵌套调用函数的正确返回。A队列 B栈 C树 D图,堆栈操作中，保持不变。A堆栈的顶 B堆栈中的数据 C堆栈指针 D堆栈的底,解析：在CPU执行程序的过程中，会执行有关的堆栈操作指令。执行这样的指令，无论是压入堆栈还是弹出堆栈，堆栈指针和栈顶肯定随着指令的执行而发生改变。同时，堆栈中的数据也会随着压入数据的不同而改变。惟一不会改变的就是在堆栈初始化时设置的堆栈的底。,判断一个表达式中左右括号是否匹配，采用 实现较为方便。A线性表的顺序存储 B队列 C线性表的链式存储 D栈,PUSH和POP命令常用于 操作。A队列 B数组 C栈 D记录,若in、out分别表示入队、出队操作
19、，初始队列为空且元素a、b、c依次入队，则经过操作序列in、in、out、out、in、out之后，得到的出队序列为。Acba Bbac Cbca Dabc,队列的运算特点是先入先出，总是处于队头的元素先出队，新元素总是加入队尾，元素a、b、c依次入队并经过操作序列in、in、out、out、in、out的过程如下图所示。,在以下情形中，适合于采用队列数据结构。A监视一个火车票售票窗口等待服务的客户 B描述一个组织中的管理机构 C统计一个商场中的顾客数 D监视进入某住宅楼的访客,元素3、1、2依次全部进入一个栈后，陆续执行出栈操作，得到的出栈序列为。A 3、2、1 B3、1、2 C 1、2、3 D2、1、3,若需将一个栈S中的元素逆置，则以下处理方式中正确的是。A将栈S中元素依次出栈并入栈T，然后将栈T中元素依次出栈并进入栈S B将栈S中元素依次出栈并入队，然后使该队列元素依次出队并进入栈S C直接交换栈顶元素和栈底元素 D直接交换栈顶指针和栈底指针,选项B，将栈S中元素依次出栈并入队后，队头元素为原栈S的栈顶元素，队尾元素尾原栈S的栈底元素。队列的操作特点是先入先出，因此使该队列元素依次出队并进入栈S后，队头元素就进入栈底，队尾元素称为栈顶，因此可实现将栈S中元素逆置的效果。,
