计算机应用基础课件1.3栈和队列.ppt

,第 1 章 数据结构,1.1 基本数据结构与算法 1.2 线性表 1.3 栈和队列1.4 树和二叉树 1.5 查找1.6 内部排序,姓名 学号 成绩 班级 李红 9761059 95 机97.6,10,65,865,一叠书或一叠盘子。,栈顶,栈底,a1,栈s=(a1,a2,，an),a2,an-1,an,一种操作受限的线性表,只允许在表的一端进行插入和删除,1.栈的定义,定义：只允许在线性表的一端进行插入和删除的线性表。,与栈有关的相关术语：,1.3栈和队列,(1)栈顶：允许插入与删除的一端称为栈顶(2)栈底：不允许插入与删除的一端称为栈底(3)入栈：栈的插入操作(往栈中插入一个元素)(4)出栈：栈的删除操作(从栈中删除一个元素)(5)栈空：top=0(6)栈满：top=m(m为栈最大容量),进栈,出栈,栈顶,栈底,假设栈：s=(a1,a2,，an),1.3.1 栈,栈空：top=-1,栈示意图：,修改栈的原则：(考点)先进后出(FILO,First In Last Out)或后进先出(LIFO),栈顶元素总是最后入栈，而最先出栈的栈底元素总是最先入栈，而最后出栈的,堆栈操作,出栈元素顺序：B C D A,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。链式存储结构：用于收集计算机存储器中所有空闲存储空间,来保存自栈底到栈顶的数据元素。,顺序栈：顺序存储结构的栈称为顺序栈。链栈：链式存储结构栈称为链栈。,进栈,A,出栈,栈满,B,C,D,E,F,设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow),栈空,顺序栈实现：一维数组dataM,注意：数组是倒过来图示的。故，top指向的是其箭头上面的存储空间,顺序栈实现：一维数组dataM,栈顶指针并不一定是指针变量，也可以是下标变量,#define SIZE 50typedef struct char dataSIZE;int top;SeqStack;,/*置栈空*/void InitStack（SeqStack*S）S-top=0;,/*进栈*/void Push（SeqStack*S，char x）if(StackFull(S)printf(“Stack overflow”);/上溢，退出运行 exit(0);S-dataS-top=x;/将x入栈 S-top=S-top+1;/栈顶指针加1,/*出栈*/char Pop（SeqStack*S）if(StackEmpty(S)printf(“Stack underflow”);/下溢，退出运行 exit(0);S-top=S-top-1;/将栈顶指针减1 return S-dataS-top;/栈顶元素返回,top=0,栈空,A,top=1,假设：调用两次Push函数 Push(S,A);Push(S,B);,top=2,B,假设：调用一次Pop函数 Pop(S);,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,2)顺序栈的基本运算：入栈、出栈与读栈顶元素,(1)入栈,新元素插入到栈顶指针指向位置栈顶指针top加1,步骤：,注意:栈顶指针指向存储空间最后一个位置时，栈已满，不能再入栈。称为栈“上溢”错误.,栈空：top=0,思考：当栈空条件为：top=-1时，入栈步骤,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,2)顺序栈的基本运算：入栈、出栈与读栈顶元素,(2)出栈,步骤：,栈顶指针top减1栈顶元素赋给一个指定的变量,栈顶指针为0时,栈空,不能再退栈。称为栈“下溢”错误,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,2)顺序栈的基本运算：入栈、出栈与读栈顶元素,(3)读栈顶元素,概念：将栈顶元素赋给一个指定变量,注意：不删除栈顶元素，栈顶指针不会改变,1.栈的定义,1.3栈和队列,1.3.1 栈,2.顺序栈及其运算,1)栈的两种存储结构,2)顺序栈的基本运算：,3)栈的典型应用,进制的转换,139,10001011,(139)10=(10001011)2,除余倒序法,(139)10（？）2,139,除余倒序法,(139)10（？）2,1,1,0,1,0,0,0,1,余数栈,定义：指允许在一端插入,而在另一端进行删除的线性表。,与队列有关的相关术语:(1)队尾：允许插入的一端称为队尾。rear队尾指针，指向队尾元素的下一个位置(2)队头：允许进行删除的一端称为队头。front队头指针，指向队头元素。(3)入队列：队列插入操作(进队列)(4)出队列：队列的删除操作(退队列)(5)空队列：队列中无数据元素,1.3栈和队列,1.3.2 队列,定义：指允许在一端插入,而在另一端进行删除的线性表。,队列结构示意图：队列Q=(a1，a2,an),1.3栈和队列,1.3.2 队列,队列修改原则：先进先出(FIFO)或后进后出(LILO),队头元素总是最先进队列的,也总是最先出队列队尾元素总是最后进队列,也是最后出队列,新来的成员总是加入队尾（即不允许加塞），每次离开的成员总是队列头上的（不允许中途离队），即当前最老的成员离队。,定义：指允许在一端插入,而在另一端进行删除的线性表。,1.3栈和队列,1.3.2 队列,2.链队列:用链表表示的队列。,Q.front,Q.rear,具有n个元素的队列,structqueueNodeintdata;/存放数据元素structqueueNode*next;/指向下一个结点;structqueuestructqueueNode*front;structqueueNode*rear;struct queue*Q;,void InitQueue(structqueue*q)/初始化队列 structqueueNode*node;node=(structqueueNode*)malloc(sizeof(structqueueNode);node-next=NULL;q-front=node;q-rear=node;,node,q.front,q.rear,带头结点的空队列,/入队列voidAddQueue(structqueue*q,inte)structqueueNode*node;node=(structqueueNode*)malloc(sizeof(structqueueNode);node-data=e;node-next=NULL;q-rear-next=node;q-rear=node;,q.front,q.rear,1,又调用一次,node,/入队列voidAddQueue(structqueue*q,inte)structqueueNode*node;node=(structqueueNode*)malloc(sizeof(structqueueNode);node-data=e;node-next=NULL;q-rear-next=node;q-rear=node;,q.front,q.rear,1,又调用一次,2,node,node,/出队int DelQueue(struct Queue*q)int x;struct QueueNode*p;p=q-front-next;q-front-next=p-next;if(p-next=NULL)q-rear=q-front;/防止尾指针丢失 x=p-data;free(p);return x;,q.front,q.rear,1,2,p,x,1,又调用一次,if不成立,/出队int DelQueue(struct Queue*q)int x;struct QueueNode*p;p=q-front-next;q-front-next=p-next;if(p-next=NULL)q-rear=q-front;/防止尾指针丢失 x=p-data;free(p);return x;,q.front,q.rear,2,x,1,又调用一次,p,if成立,2,新元素入队时插在头结点之后,修改rear指针删除一个元素时,修改front指针。,Q.front,Q.rear,空队列,Q.front,Q.rear,a1入队列,新元素入队时插在头结点之后,修改rear指针删除一个元素时,修改front指针。,Q.front,Q.rear,队列中有两个数据元素,出队列,删除唯一元素时,front与rear回缩到头结点，为空队列。,定义：指允许在一端插入,而在另一端进行删除的线性表。,1.3栈和队列,1.3.2 队列,3.顺序队列,定义：队列的顺序存储结构称为顺序队列，利用一组地址连续的存储单元依次存放队列中的数据元素。,约定：初始化队列令front=rear=0,入队时：将新元素插入rear所指的位置，然后将rear加1。出队时：删去front所指的元素，然后将front加1并返回被删元素。,在非空队列中头指针front始终指向队列头元素尾指针指向队尾元素的下一个位置,2.链队列:用链表表示的队列。,举例：顺序队列头尾指针变化情况,A,B,C,D,Q.front,ABCD相继入队,Q.front,空对列,front=rear=0,举例：顺序队列头尾指针变化情况,A,B,C,D,Q.front,出队,Q.front,空队列,front=rear=0,Q.front,Q.front,Q.front,E,入队,F,队未满,却不能再入队，假溢出,定义：指允许在一端插入,而在另一端进行删除的线性表。,1.3栈和队列,1.3.2 队列,2.链队列:用链表表示的队列。,3.顺序队列,缺点：有“假溢出”现象，为克服这点，引入循环队列。,4.循环队列,定义：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环形空间。,0,4,3,2,1,Q.front,对应为：,A,B,C,D,入队,A,B,C,D,出队,Q.front,Q.front,0,4,3,2,1,对应为：,C,D,入队,C,D,出队,Q.front,E,E,队尾指针指出数组外,队未满,却不能再入队，假溢出,0,若用循环队列：,即,问题是如何让rear（等于4）加1之后能够回退到0,方法一：if(Q.rear+1=5)Q.rear=0;else Q.rear=Q.rear+1;,方法二：利用“求余运算Q.rear=(Q.rear+1)%5；,0,4,3,2,1,对应为：,C,D,入队,C,D,出队,Q.front,E,E,F,F,继续入队,G,G,队满：Q.rear=Q.front,但是,考虑出队情况,队空：Q.rear=Q.front,因此，一般循环队列少用一个存储空间;队满条件就变为：(Q.rear+1)%M=Q.front,0,4,3,2,1,C,D,E,F,0,4,3,2,1,C,D,E,F,G,队满,指针基本运算空与满上溢与下溢,栈 队列顺序栈 顺序队列 循环队列,top:指向栈顶下一个位置,front:队头元素rear:队尾元素的下一个位置,同左,入栈:top加1出栈:top减1,入队:队尾rear加1 出队:队头front加1,入队:(rear+1)%m 出队:(front+1)%m,栈空:top=0栈满:top=m,队空:front=rear=0 队满:rear=m,front=rear(rear+1)%m=front,栈顶已满,不能入栈栈空,不能退栈,上溢:队满,不能入队下溢:队空,不能退队,总结,m为存储空间长度,练习1一个栈的入栈序列1，2，3，4，则它的不可能的输出序列是（）。A.1，2，3，4 B.4，3，2，1 C.1，3，4，2 D.4，1，2，3,2.一个栈的输入序列是1，2，3，4，5，则下列序列中（）是栈的输出序列。A.31245 B.41325 C.23415 D.142533.假定利用数组aN顺序存储一个栈，用top表示栈顶指针，top=-1表示栈空，并已知栈未满，当元素x进栈时所执行的操 作为（）A.a-top=x B.atop-=x C.a+top=x D.atop+=x,top=-1栈空：先top1，再x赋值过来 top=0栈空：x先赋值过来，再top+1,4.一个队列的入队序列是1，2，3，4，则队列的输出序列是（）A.4，3，2，1 B.1，2，3，4 C.1，4，3，2 D.3，2，4，15.从一个顺序循环队列中删除元素时，首先需要（）A.前移队首指针 B.后移队首指针C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素6.假定一个顺序循环队列的队首和队尾指针分别用front和rear表示，则判断队列空的条件为（）A.front+1=rear B.rear+1=front C.front=0 D.front=rear,7.假定一个顺序循环队列存储于数组aN中，其队首和队尾指针分别用front和rear表示，则判断队列满的条件为（）A.（rear-1）%N=front B.（rear+1）%N=front C.（front-1）%N=rear D.（front+1）%N=rear5,8.线性表、栈和队列都是_结构，对于栈只能在_插入和删除元素；对于队列只能在_插入元素，在_删除元素。,线性、栈顶、队尾、队头,9.设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，对应的输出序列是_。,2,3,10.设元素1，2，3，4，5依次进栈，若要在输出端得到序列 34251，则应进行的操作序列为push(S,1),push(S,2),_，pop(S)，push(S,4)，pop(S)，_，_,pop(S)，pop(S)。,push(S,3),pop(S),push(S,5),11.在一个具有n个存储单元的循环队列中，当队列满时共有_ 个元素。,n-1,12.栈又称为_表，队列又称为_表。,后进先出、先进先出,