数据结构栈和队列

1、第第3 3章章 栈和队列栈和队列 栈和队列是两种特殊的线性表，是操作受限的线性表，称为限定性数据结构。3.1 栈（stack）3.1.13.1.1栈的定义和特点栈的定义和特点定义：栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，,an)，则a1称为栈底元素，an为栈顶元素。栈中元素按 a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。特点：先进后出（FILO）或后

2、进先出（LIFO）。ana1a2.栈底栈顶.出栈进栈栈s=(a1,a2,an)栈的示意图3.1.2栈的运算（栈的基本运算）栈的运算（栈的基本运算）1.初始化栈：初始化栈：InitStack (&S)初始空栈S。将栈S置为一个空栈(不含任何元素)。2.销毁：销毁：destroyStack (&S)将栈S销毁，释放栈的存储空间。3.判栈空：判栈空： StackIsEmpty(S) 判断栈S是否为空，若为空则返回真（TRUE）否则返回假（FALSE）.4.清空：清空： clearStack(&S)将栈清空，变为空栈。5.入栈：入栈： Push(&S,e)栈S已存在，e为给定数据元素值。将给定值为e的

3、元素入栈，即将e在栈S的栈顶端插入。6.出栈：出栈： Pop(&S,&e)将栈S的栈顶元素出栈，即将栈顶元素删除，并通过参数e返回出栈的元素的值。7.取栈：取栈： getTop(S,&e)取栈S的栈顶元素的值，将栈顶的元素的值通过参数e返回。8.求栈长：求栈长： stackLength(S)求栈S的长度，即栈中的元素的个数。当栈S非空时，函数返回该栈的长度；而当栈S为空时则返回0。9.遍历：遍历： stackTraverse(S,visit()Visit()为元素的访问函数。依照从栈底到栈顶的顺序依次访问栈S的元素，且每个元素只被访问一次。3.1.3 3.1.3 顺序栈顺序栈实现：一维数组sM

4、top=-1123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为-1top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=-1,栈空，此时出栈，则下溢（underflow)top=Maxsize-1,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空顺序栈的存储结构描述 #define StackSpaceIncer 20 /存储空间的增量 typedef struct SElemType * base; / SElemType为栈元素类型,base为顺序栈存储空间的动态 数组 in

5、t top; /指示下一个入栈的下标位置 int stackSize; /栈当前的存储空间大小 SqStack ; / SqStack为顺序栈类型顺序栈的基本操作（1）初始化 InitSqStack (&S,InitSize) 创建一个初始空间大小为InitSize的空顺序栈S。（2）判空操作 stackIsEmpty(S) 清空操作 clearStack(&S) 求栈长 stackLength (S)（3）入栈 Push(&S,e) 在顺序栈S的栈顶插入一个值为e的元素。（4）出栈 Pop(&S,&e) 若顺序栈S为空，则出栈操作出错。否则，将栈顶元素删除只需将栈顶指针top向下移动一个位置

6、（top-1）即可，同时还需将出栈元素的值由参数e 返回。（5）取栈顶 getTop(S,&e) 若顺序栈S为空，则出栈操作出错。否则，下标为top-1的元素即为栈顶元素，将其值由参数e返回。3.1.4 3.1.4 链式栈链式栈栈的链式存储结构成为链式栈。栈的链式存储结构成为链式栈。链栈的存储结构描述 typedef struct stackNode SElemType data; struct stackNode *next; *LinkStack; /链式栈类型，即链表的头指针类型实现实现 .topdatalink栈底 .栈底toptopxptop .栈底topp入栈过程：出栈过程：栈顶3

7、.1.4 链式栈上的基本操作链式栈上的基本操作 由栈的基本操作可见，栈的操作仅仅是线性表的相应操作的特例。因此，当利用单链表来表示链式栈时，链式栈基本操作的实现算法就可以用单链表的相关基本操作算法来表示。（1）初始化 InitLinkStack(&S) 即创建一个空的不带头结点的单链表S，也就是将头指针S赋值为空。算法见 3-8。（2）入栈操作 Push(&S,e) 将元素e入栈即在单链表S的首端插入值为e的结点。链式栈的入栈操作算法见 3-9.（3）出栈操作 Pop(&S,&e) 栈非空时，将单链表的表首结点删除，算法见3-10（4）取栈顶操作 getTop(S,&e) 栈非空时，由参数e返

8、回栈顶指针S所指栈顶结点的值。算法见 3-113.1.5 栈的应用1、简单的行编辑程序 一个简单的行编辑程序功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。由于用户在终端上进行输入时，不能保证不出差错 ,如原为输入：while(*s)却输成：whliilre(s)。 在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。比如：whli#ilr#e(s#*s) outchaputchar(*s=#+)实际上为： while(*s) putchar(*s+) 算法如下: void lineedit( ) /利

9、用字符栈S，从终端接收一行并传送至调用过程的数据区 initstack(s); /构造空栈S ch=gether( ); /从终端接收一个字符 while(ch!=eof) /若全文未结束 while(ch!=eof & ch!=n) switch(ch) case # : pop(s,c); break; /仅当栈非空时退栈 case : clearstack(s);break; /重置s为空栈 default : push(s,ch); break; /有效字符进栈，未考虑栈满情形 ch=getchar( ); /从终端接收下一个字符 /将从栈底到栈顶的栈内字符传送至调用过程的数据区 cl

10、earstack(s); /重置s为空栈 if(ch!=eof) ch=gethar( ); destroystack(s); /结束字符输入后销毁栈 3.2 栈与递归栈与递归 递归是在数学和计算机科学中处理问题的一种重要方法。在软件设计中当采用递归方法解决问题时，可以使问题的描述和编写的程序变得简洁和清晰。3.2.1 递归的概念和算法 递归：一个概念、函数等对象用自己来定义自己。递归：一个概念、函数等对象用自己来定义自己。 在程序设计语言中，一个算法直接或者间接调用了自己，在程序设计语言中，一个算法直接或者间接调用了自己，则称该算法为递归算法。这过程称为递归调用的过程。则称该算法为递归算法。

11、这过程称为递归调用的过程。例如，下列为某人祖先的递归定义：某人的双亲是他的祖先（基本情况）。某人祖先的双亲同样是某人的祖先（递归步骤）。斐波纳契数列（Fibonacci Sequence），又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21. 斐波纳契数列是典型的递归案例：递归关系就是实体自己和自己建立关系。递归的算法递归的算法 了解了递归的定义，在程序语言中便可给出其递归的算法。例如，利用C语言定义阶乘的递归函数：算法 3-16 long fac(int n) /求n的阶乘；设n值大于等于0long f;If (n=0) f=1;Else f=n*fac(n-1) ;

12、/递归调用自身return f;一个递归定义必须满足两个最基本的递归法则：（1）基准情形法则：递归定义中的基准情形即递归出口，它本身不再使用递归定义，是递归的结束条件。（2）不断推进法则：是指在递归求解过程中，每一次递归调用都必须使求解状况朝接近基准情形的方向推进。算法举例算法举例在数学中对于阶乘的递归定义：n!，是阶乘符号在此定义中，当n0时就说利用n-1的阶乘来定义n的阶乘，所以此定义为递归定义。3.2.2 3.2.2 递归算法的运行机制递归算法的运行机制 在高级程序设计语言中，函数的执行所遵循的原则为：当函数调用时，则将实参传递给函数的形参，然后转到函数的入口执行函数体。而当被调用函数执

13、行结束时，则返回到改函数的被调用位置继续执行下一程序指令，当有函数的多层嵌套调用时，在返回时也将逐层返回，其特点为“最后调用的，最先执行完，最先往回返”。每次调用函数时所需保存的一个相关信息称为一个“工作记录”，其主要包括：1、返回地址：即函数运行结束后需转去执行的程序指令（是上一层中“函数被调用位置”的下一条程序指令）的地址2、函数的形参，函数局部变量：即在调用时为函数形参与局部变量分配的动态存储空间。在程序执行时，每当发生一次函数调用，就向工作栈中压入一个新的工作记录；每当有一次函数结束发生时，就从工作栈中弹出一个工作记录。所以当前正在执行的函数的工作记录一定在工作栈的栈顶，称此工作记录为

14、“活动记录”3.3 3.3 队列队列(Queue)(Queue)3.3.1 3.3.1 队列的定义及特性队列的定义及特性定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)v特性：队列是一种运算受限制的线性表，元素的添加在表的一端进行，而元素的删除在表的另一端进行。允许添加元素的一端称为队尾（Rear）；允许删除元素的一端称为队头（Front）。向队列添加元素称为入队，从队列中删除元素称为出队。 新入队的元素只能添加在队尾，出队的元素只能是

15、删除队头的元素，队列的特点是先进入队列的元素先出队，所以队列也称作先进先出表或FIFO（First-In-First-Out）表。 3.3.2 3.3.2 队列的基本运算队列的基本运算 队列可定义如下五种基本运算：1初始化队列初始化队列 InitQueue(&Q) 构造一个队列，并将队列Q设置成一个空队列。2销毁队列销毁队列 destroyQueue (&Q) 将队列Q销毁，释放其存储空间。3. 判队空判队空 queueIsEmpty(Q) 判断队列Q是否为空，若为空返回真，否则返回假。4. 清空操作清空操作 clearQueue (&Q) 将队列将队列Q清空，变为空队列清空，变为空队列5.

16、入队列入队列 insertQueue(&Q,e) 将元素e插入到队尾中，也称“进队” ，“插入”。 6出队列出队列 deleteQueue(&Q,&e) 将队列Q的队头元素删除，也称“退队”、“删除”。并通过e返回其值。7取队头元素取队头元素 GetFront(Q,&e) 得到队列Q的队头元素的值，并将该值由参数e返回。8求队长操作求队长操作 queueLength(Q) 求队列Q的长度，即队列中元素的个数。队列为空时返回0。9遍历操作遍历操作 queueTraverse(Q,visit() 依照从队头到队尾的顺序依次访问队列依照从队头到队尾的顺序依次访问队列Q中的所有元素，且中的所有元素，且

17、每个元素只被访问一次。每个元素只被访问一次。3.3.3 3.3.3 循环队列循环队列 循环队列是队列的顺序存储结构中最常用的一种形式。1、循环队列的存储结构与类型定义为充分利用向量空间，克服假溢出现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。这种循环队列可以以单链表的方式来在实际编程应用中来实现。循环队列类型循环队列类型CirQueuev循环队列v基本思想：基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0.实现：利用“模”运算;入队： sqrear=x ;rea

18、r=(rear+1) %M;v 出队：x=sqfront;front=(front+1)%M; 012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：front=rear队满：front=rear3.3.3 3.3.3 循环队列循环队列 2、循环队列上基本操作的实现（1）初始化操作）初始化操作 InitCirQueue(&Q,QSize)创建一个空间大小为Qsize的空队列Q（2）判空操作判空操作 queueIsEmpty(Q)判断队列是否为空，只需判断其队头指针Q .

19、front与队尾指针Q.rear是否相等清空操作清空操作 clearQueue(&Q)（3）入队操作）入队操作 insertQueue(&Q,e)入队操作时，若队列Q已满，就不再进行插入，操作失败。（4）出队）出队 操作操作 deleteQueue(&Q,&e)（5）取队头操作）取队头操作 getFront(Q,&e)当队列Q非空时，front指针所指向的即为队头元素。（6）求队长操作）求队长操作 queueLength(Q)队列的长度即为队列中元素的个数。 3.3.4 3.3.4 链式队列链式队列1、链式队列的存储结构与类型定义与线性表类似，队列也有两种存储表示；队列的链式存储-链队列链队列

20、需要队头和队尾两个指针来确定；给链队列添加个头结点，并令头指针指向头结点。头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾2、 链式队列上基本操作实现：（1 1）初始化操作）初始化操作 InitLinkQueue(&Q)InitLinkQueue(&Q)对链式队列Q进行初始化，即创建只含有一个头结点的空队列。（2 2）队列的判空操作）队列的判空操作 queueIsEmpty(Q)queueIsEmpty(Q)判断链式队列Q是否为空，可以有两种方法：一是盘对队头指针front与队尾指针rear是否相等；二是盘对队列链表中是否只有一个头结点，即Q.front-是否为空，一般采用方法一，即空队列的判断条件为：Q.front=Q.raer（3 3）入队操作）入队操作 insertQueue(&Q,e)insertQueue(&Q,e)对于链式队列Q，入队时只需在rear所指向的队尾结点后面插入新结点，同时rear再指向新的队尾结