《《数据结构（第二版）》课件 包振宇 第三章 栈和队列》由会员分享，可在线阅读，更多相关《《数据结构（第二版）》课件 包振宇 第三章 栈和队列（35页珍藏版）》请在金锄头文库上搜索。
1、第三章 栈和队列,3.1 堆栈 3.2 队列 3.3 典型例题,3.1 堆栈,3.1.1 堆栈的定义和基本操作 栈（stack）是一种特殊的线性表，这种表只能在其一端（称为栈顶top）进行插入和删除操作,如图2-4-1所示。栈的概念来自存货的堆栈，存货时一件一件往上堆，每次取货时都有只能从上面取。栈的存取特征是后进先出（Last In First Out,缩写为LIFO）。栈顶将随着栈中元素的增减而浮动，通过栈顶指针指明当前栈顶元素位置。栈的固定端称为栈底（bottom），栈底指针并不移动。 栈的基本操作包括：创建一个栈进栈 栈顶 出栈 进栈（push），出栈（pop） 读取栈顶元素，判栈空，
2、 栈清空（初始化），求当前栈 中元素的个数，撤消一个栈等 栈底,3.1.2 顺序存储栈,可用顺序存储线性表来表示栈，为了指明当前执行插入和删除运算的栈顶位置，需要一个游标变量top（习惯称为栈顶指针，注意与指针变量的区别），top指出栈顶表元素在数组中的下标。当栈为空时，top =0;栈满时，top=MAXN(数组元素个数),如图2-4-1所示。,顺序存储栈示意图,MAXN-1 MAXN-1 top . . . . . . 1 1 top-0 0 栈空 栈满,1、顺序存储栈的进栈操作(1),顺序存储栈的进栈操作(2),函数如下： int push(NODE stack,int maxn,int
3、 top,NODE x)/*设栈点的数据类型为NODE，栈空间最多能存maxn个结点*/ if (top=maxn) return 1; /*栈满，进栈失败返回*/ stack top=x; /*完成进栈运算*/ +top; return 0; /*进栈成功，返回0*/ ,2、顺序存储栈出栈操作(1),顺序存储栈出栈操作(2),函数如下： int pop(NODE stack,int top,NODE cp) if(top=0) return 1; /*栈空，出栈失败返回*/ -top; cp=stacktop; /*完成出栈运算*/ return 0; /*出栈成功，返回*/ ,3.1.3
4、链式存储栈,栈也可以用链表实现，用链表实现的栈称为链式栈。链表的第一个元素是栈顶结点，链表的末尾元素是栈底结点，链表的首表指针是栈顶指针top ,top为null的空链表是空栈。 设栈结点类型为： typedet struct node NODE data; /*栈元值，某种NODE类型*/ struct node *link; LNODE;,(一) 链式存储栈的进栈函数,示意图 top top=p p-link=top p,4,X,5,2 null,函数定义,函数如下： void L_push(NODE x,LNODE *top) /*设栈结点的数据类型为NODE*/ LNODE *p=(L
5、NODE *)malloc(sizeof(LNODE); p-data=x; p-link=top; top=p; ,（二 ）链接存储栈的出栈函数,示意图 Top p,4,5,2 Null,函数定义,int L_pop(NODE *cp,LNODE *top) /*设栈结点的数据类型为NODE*/ LNODE *p=top; if(top=NULL) return 1;/*空栈*/ *cp=p-data; top=p-link; free(p); return 0;/*出栈成功*/ ,3.2 队 列,一、队列定义、 队列是只允许在一端进行插入，另一端正进行删除的线性表，如图3-7所示。 出队
6、q0 q1 qi qi+1 qn-1 进队 队首 队尾 图3-7 队列示意图,队列中允许删除运算的一端称队首，允许插入运算的一端称为队尾。习惯称在队列中插入结点操作为进队，队列中删除结点的操作为出队。 若有队Q=(q0,q1,qn-1),则q0为队首结点，qn-1为队尾结点。因最先进入队列的结点将最先出队，所以队列具有先进先出（First In First Out简称FIFO）的特性。 队列的基本操作包括：创建一个队列，入列，出队，读取队首元素，判队空，请队列空，求当前队列中的元素个数，撤消一个队列等。,3.2.1 顺序存储队列,可以用顺序存储线性表来表示队列，为了指明当前执行出队运算的队首位
7、置，需一个游标变量front（习惯上称为头指针），为了指明当前执行进队运算的队尾位置，需要一个游标变量rear（习惯上称为尾指针）。 开始时，让队列front度rear都指向数组的前端，这是一个空队列。在队列未满情况下，队列可执行进队运算。进队时，首先让rear加1,变为指向队列新结点的存放下标，然后将新结点送到由rear所指的数组元素中。队列非空时，可执行出队运算。出队时，首先把front所指的队列首结点送到接受结点的变量中，然后让front加1，使front指向新的队首结点。,出入队列的状态示意图,环形队列(1),若用有MAXN个元素的数组表示队列，随着一系列进队和出队运算，队列的结点移向
8、存放队列的数组的尾端，会出现数组的前端空着，而队列空间已用完的情况。一种可行的解决方法是当发生这样的情况时，把队列中的结点移到数组的前端，并修改头指针和尾指针。另一种更好的解决办法是采用环形队列。 环形队列就是将实现队列的数组q的首元q0与末元qmax-1连接起来。队空的初态为front=rear=0；在环形队列中，当rear赶上front时，队列满。反之，当front赶上rear时，队列为空。这样队空或队满的条件都同为front=rear，这给程序判别队空或队满带来不便。为此采用当队列只剩下一个空闲结点的空间时，就认为队列已满的简单办法以区别队空和队满。示意图如下： 队列出、入队操作示例：,
9、环形队列(2),在下面的入列和出队算法中，queue数组用来存放队列元素，头指针为front，尾指针为rear，数据结构定义如下： #define MAX 50 int queueMAX； int front=-1,rear= -1; 1、顺序队列的进队列算法：队满时返回eof，否则返回0 int insert_queue (int x) if (rear= =MAX-1) return(eof); queue+rear=x; return(0); ,环形队列(3),2、顺序队列出队列算法：队空时返回eof，否则返回y值 int delete_queue() int y ; if (front
10、= =rear) return(eof); y=queue+front; return(y); 3、入循环队列 int inset_q(int q, int x) int front,rear; if (rear+1)%MAX)= =front) return(eof); else rear=(rear+1)%MAX; qrear=x; return(1); ,环形队列（4）,4、出循环队列 int delete_q(int q, int y) int front,rear; if(front= = rear) return(0); front=(front+1)%MAX; y=qfront;
11、 return(y); ,3.2.2链式存储队列,队列也可以用链表实现，用链表实现的队列称为链式队列。链表的第一个表示是队列首结点，链表的末尾表示是队列的队尾结点，队尾结点的链接指针值为null。队列的头指针hpt指向队列的首结点，队列的尾指针tpt指向队尾结点。当队列的头指针hpt值为null时，队列为空。设有： typedef struct node node data; struct node *link; Lnode;,一、链式队列进队函数,示意图 tpt hpt p,A,X null,B,C null,链式队列进队函数定义,void Len_queue(Lnode *hpt,Lnod
12、e *tpt,node x) Lnode *p=(Lnode *)malloc(sizeof(Lnode); p-data=x; p-link=null; if (hpt= =null)tpt=hpt=p; else tpt = (tpt)-link=p; ,二、链式队列出队函数,示意图 hpt=hpt-link tpt hpt p,A,B,C null,链式队列出队函数定义,int Lde_queue(Lnode *hpt,Lnode *tpt,node *cp) Lnode *p= hpt; if(hpt= =null) return 1; /* 队空*/ *cp= (hpt)-data;
13、 hpt=(hpt)-link; if(hpt= = null) tpt=null; free (p); return 0; ,3.3 典型例题,1.设有一顺序栈S,元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是( )。 分析s1,s2进栈后，此时栈中有2个元素，接着s2出栈，栈中尚有一个元素；s3,s4进栈后，此时栈中有3个元素，接着s4,s3出栈，栈中尚有一个元素；s5,s6进栈后，此时栈中有3个元素，接着s6,s5出栈，栈中尚有一个元素；s1出栈后，此时栈为空栈。由此可知，栈的容量至少应该是3。 答案B),
14、2.链栈与顺序栈相比，有一个比较明显得优点是( )。 A)通常不会出现栈满的情况 B)通常不会出现栈空的情况 C)插入操作更加方便 D)删除操作更加方便 分析不管是链栈还是顺序栈，其插入、删除操作都是在栈顶进行的，都比较方便，所以不可能选C)，D)。对链栈来讲，当栈中没有元素而又要执行出栈操作时，就会出现栈空现象，故B)也是不正确的。只要内存足够大，链栈上就不会出现栈满现象。而对顺序栈来讲，由于其大小是事先确定好的，因此可能会出现栈满现象。所以A)是正确的。 答案A),3.3 典型例题,3.在具有n个单元的循环队列中，队满共有_个元素。 分析在循环队列中，为了能正确区分队满、队空两个判断条件，
15、当前头指针front所指单元总是空的。因此最多(队满时)能存放n-1个元素。 答案n-1,3.3 典型例题,4.栈的逻辑特点是_，队列的逻辑特点是_。两者的共同点是只允许在它们的_处插入和删除数据元素。 分析由于只能在栈顶处执行插入、删除操作，使得数据元素的进栈顺序恰好与出栈顺序相反，所以栈的逻辑特点是先进后出(或后进先出)。而对队列来讲，插入、删除操作必须在队列的两端进行，数据元素的进队顺序与出队顺序是一致的。所以队列的逻辑特点是先进先出(或后进后出)。两者的共同点是所有操作只能在端点处进行。 答案先进后出(或后进先出)，先进先出(或后进后出)，端点。,3.3 典型例题,5.二维数组M的的成员是6个字符(每个字符占一个存储单元)组成的串，行下标I的范围从0到8，列下标从1到10，则存放M至少需要_个字节；M的第8列和第5行共占_个字节；若M按行优先方式存储，元素M85的起始地址与当M按列优先方式存储时的_元素的起始地址一致
