数据结构：第3章 栈和队列.ppt

第3章 栈和队列概述Ø两种特殊的线性表Ø逻辑结构和线性表相同Ø比起线性表其运算受限制，故又称它们为运算受限的线性表Ø栈和队列应用在各种程序设计中Ø尤其栈的应用更广1. 栈1.1 栈的定义1.2 顺序栈1.3 链栈1.1 栈的定义       栈（Stack）是限制仅在表的一端进行插入   和删除运算的线性表1)通常称插入、删除的这一端为栈顶栈顶（Top），另一端称为栈底栈底（Bottom）2)当表中没有元素时称为空栈空栈3)栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈 每次进栈的元素都被放在原栈顶元素之上而成为每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中新的栈顶，而每次出栈的总是当前栈中“最新最新”的元的元素，即最后进栈的元素因此，栈又称为素，即最后进栈的元素因此，栈又称为后进先出的后进先出的线性表线性表简称为LIFOLIFO表栈的示意图a1a2an栈顶（表尾）栈底bottomtop入栈入栈push出栈出栈pop栈的示意图S3bottomtopS1S2S5S6S3S4S3S3S3S3S3PUSHPUSHPUSHPOPPUSHPUSHPUSH 栈在计算机中主要有两种基本的存储栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。

结构：顺序存储结构和链式存储结构l 顺序存储的栈为顺序栈顺序存储的栈为顺序栈l 链式存储的栈为链栈链式存储的栈为链栈栈的存储方式1.2 顺序栈         栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素       顺序栈的类型定义#define TRUE 1#define FALSE 0#define Stack_Size 50 typedef struct{    StackElementType  elem[Stack_Size];        /* 一维数组*/      int  top;                                /*用来存放栈顶元素的下标*/}SeqStack; top空栈toptoptoptoptopa 进栈b 进栈aababcdee 进栈abcdef 进栈溢出abdee 退栈ctopc 退栈b 退栈abaa 退栈空空栈topabdd 退栈ctopabctoptop  注意①顺序栈中元素用向量存放②栈底位置是固定不变的，可设置在向量两端的任意一个端点③栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置顺序栈的基本运算（1） 置栈空（初始化）（2） 判栈空（3） 判栈满（4） 进栈操作（5） 退栈操作（6） 取栈顶元素    　（1）置栈空（初始化）  void InitStack（SeqStack *S） {//将顺序栈置空      S->top=-1;    } (2) 判栈空  int StackEmpty（SeqStack *S）{      /*判栈S为空栈时返回值为真，反之为假*/       return S->top==-1;   }（3）判栈满  int StackFull（SeqStack *S）{/*判栈S为满时返回真，否则返回假*/       return S->top==StackSize-1; }（4）进栈进栈时，需要将S-＞top加1  注意：　   ①S-＞top==StackSize-1表示栈满　　②"上溢上溢"现象-当栈满时，再做进栈运算产生空间溢出的现象。

      上溢是一种出错状态，应设法避免   void Push（SeqStack *S，DataType x） { if (StackFull(S))     Error(“Stack overflow”); //上溢，退出运行 S->data[++S->top]=x;//栈顶指针加1后将x入栈}（5）退栈退栈时，需将S-＞top减1  注意：　    ①S-＞top<0表示空栈    　②"下溢下溢"现象——当栈空时，做退栈运算产生的溢出现象      下溢是正常现象，常用作程序控制转移的条件DataType Pop（S）{ if(StackEmpty(S))     Error(“Stack underflow”); //下溢，退出运行 return S->data[S->top--];//栈顶元素返回后将栈顶指针减1 }（6）取栈顶元素  DataType StackTop（S）    {       if(StackEmpty(S))           Error("Stack is empty");       return S->data[S->top];     }1.4 链栈 链栈链栈是采用是采用链表链表作为存储结构实现的栈作为存储结构实现的栈，是线性，是线性链表的特例链表的特例。

因为栈的插入和删除操作仅限制在表头因为栈的插入和删除操作仅限制在表头位置进行，所以链表的表头指针就作为栈顶指针位置进行，所以链表的表头指针就作为栈顶指针 toptop为栈顶指针，始终指向当前栈顶元素结点为栈顶指针，始终指向当前栈顶元素结点若若top=NULLtop=NULL，则代表空栈则代表空栈注意：注意：链栈在使用完毕时，应该释放其空间链栈在使用完毕时，应该释放其空间注意注意: 链栈中指针的方向是从栈顶指向栈底方向链栈中指针的方向是从栈顶指向栈底方向栈顶指针栈顶指针top∧∧a1 an-1 an   typedef struct stacknode{            DataType data            struct stacknode *next       }StackNode;  StackNode *head=NULL;   typedef struct{           StackNode *top;  //栈顶指针       }LinkStack;链栈的基本运算(1) 置栈空(2) 判栈空(3) 进栈(4) 退栈(5) 取栈顶元素（1） 置栈空      void InitStack(LinkStack *S)      {             S->top=NULL;      }(2) 判栈空      int StackEmpty(LinkStack *S)      {            return S->top==NULL;      }（3） 进栈void Push(LinkStack *S,DataType x){//将元素x插入链栈头部   StackNode *p=            (StackNode *)malloc(sizeof(StackNode));   if(p==NULL)       { printf(“内存空间不够分配”);          exit(0);//return        }  //健壮       p->data=x;   p->next=S->top;//将新结点*p插入链栈头部   S->top=p; }（4） 退栈      DataType Pop(LinkStack *S)      {            DataType x;            StackNode *p=S->top;//保存栈顶指针            if(StackEmpty(S))                  Error("Stack underflow.");  //下溢            x=p->data;  //保存栈顶结点数据            S->top=p->next;  //将栈顶结点从链上摘下            free(p);            return x;       }将将x x入栈，修改栈顶入栈，修改栈顶指针指针:top=p:top=pa an n出栈，修改栈顶指出栈，修改栈顶指针针:top=top->next:top=top->next链栈的入栈操作和出栈操作（5） 取栈顶元素      DataType StackTop(LinkStack *S)       {            if(StackEmpty(S))                 Error("Stack is empty.")             return S->top->data;        }  注意        链栈中的结点是动态分配的，所以可以不考虑上溢，无须定义StackFull运算。

 2. 队列2.1 队列的定义2.2 顺序队列2.3 链队列   队列队列是一种特殊的线性表，限定插入和删除操作分别在表的两端进行                      a1 a2 … ai … an  队头 f队尾 r出队出队入队入队2.1 队列的定义和基本运算队列的性质（1）允许删除的一端称为队头（队头（Front））2）允许插入的一端称为队尾（队尾（Rear））3）当队列中没有元素时称为空队列空队列4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表表队列的进队和出队 front rear空队列front rearA进队Afront rearB进队A Bfront rearC, D进队A B C Dfront rearA退队B C Dfront rearB退队C Dfront rearE,F,G进进队C D E F GC D E F Gfront rearH进进队,溢出队列的进队和出队原则n 进队时队尾指针先进一进队时队尾指针先进一 rear = rear + 1，， 再将新元素按再将新元素按 rear 指示位置加入。

指示位置加入n 出队时队头指针先进一出队时队头指针先进一 front = front + 1，， 再将下标为再将下标为 front 的元素取出的元素取出n 队满时再进队将队满时再进队将溢出出错溢出出错；；n 队空时再出队将队空时再出队将队空处理队空处理n 解决办法之一：将队列元素存放数组首尾解决办法之一：将队列元素存放数组首尾 相接，形成相接，形成循环循环(环形环形)队列队列  队列在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构l顺序存储的队列为顺序队列l链式存储的队列为链队列队列的存储方式队列的基本运算(1)初始化队列(2)判队空(3)判队满(4)入队(5)出队(6)取队首元素2.2 顺序队列2.2.1 顺序队列的定义2.2.2 顺序队列的基本运算2.2.3 循环队列2.2.1 顺序队列的定义       队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表 frontreara b c da b c d d e f d e f rear front rear  顺序队列的表示　①和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。

②由于队列的队头和队尾的位置是变化的，设置两个“指针”front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为02.2.2 顺序队列的基本运算①入队时：将新元素插入rear所指的位置，然后将rear加1②出队时：删去front所指的元素，然后将front加1并返回被删元素  注意：①当头尾指针相等时，队列为空②在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置    　 当Q->front= Q->rear 时,队列空 当Q->rear+1>MaxSize 时,队列满(即上溢出),但此时头指针指示的元素之前可能还有空单元,此现象称为假溢出;若把这样的顺序结构设想为一个循环表, 插入时就可以利用这些空单元, 这样就构成循环队列假上溢2.2.3 循环队列为充分利用向量空间，克服“假上溢”现象的方法：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量[0][1][2][3][4][5]ENQUEUE1ENQUEUE2ENQUEUE3DEQUEUE1ENQUEUE4DEQUEUE2ENQUEUE5ENQUEUE6ENQUEUE7ENQUEUE8q1q2q3 q4 q5q6q7q8循环队列 （circular queue）满满空空?FRFRFRRRRRRR 入队操作时的尾指针运算入队操作时的尾指针运算: rear=(rear+1)%Maxsize出队操作时的头指针运算出队操作时的头指针运算: front=(front+1)%Maxaize问题：问题：在循环队列中，由于队空时有在循环队列中，由于队空时有front==rear；；队满时也有队满时也有front==rear；；因因此我们无法通过此我们无法通过front==rear来判断队列是来判断队列是“空空”还是还是“满满”。

循环队列示意图循环队列的几种状态循环队列的几种状态frontrear循环队列循环队列队满和队空队满和队空的描述方法的描述方法frontrear队空队空:队满队满:frontfrontrearrear rear=front（（?））rear=front判断循环队列满和空的三种方法判断循环队列满和空的三种方法如何判断是“空”还是“满”    　 解决这个问题的方法至少有三种：　　① 设一布尔变量以区别队列的空和满，设置标志flag----- flag=0 表示空，flag=1 表示满， front 追上 rear 则 flag=0， rear 追上 front 则 flag=1 ；②留下一个单元不使用约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满，则 rear 永远也追不上 front ；③使用一个计数器记录队列中元素的总数（即队列长度）顺序循环队列的类型定义#define QueueSize  100   //应根据具体情况定义该值typedef char  DataType;  //DataType的类型依赖于具体的应用typedef struct{         int front;    //头指针，队非空时指向队头元素   int rear;    //尾指针，队非空时指向队尾元素的下一位置         int  count; //计数器，记录队中元素总数        DataType data[QueueSize] }CirQueue;顺序循环队列的基本运算1.置队空置队空2.判队空判队空3.判队满判队满4.入队入队5.出队出队6.取队头元素取队头元素①① 置队空置队空      void InitQueue(CirQueue *Q)      {              Q->front=Q->rear=0;              Q->count=0;     //计数器置0       }②② 判队空判队空       int QueueEmpty(CirQueue *Q)       {            //队列无元素为空，属第三种方法             return Q->count==0;          }       int QueueEmpty(CirQueue *Q)       {            //属第二种方法      return Q->rear==Q->front;         }　　③③ 判队满判队满int QueueFull(CirQueue *Q){ return Q->count==QueueSize;       //队中元素个数等于QueueSize时队满，属第三种方法}int QueueFull(CirQueue *Q){  return (Q->rear+1)%QueueSize==Q->front ;     //队中元素个数等于QueueSize时队满，属第二种方法}④④ 入队入队void EnQueue(CirQueue *Q,DataType x){     if(QueueFull((Q))                                Error("Queue overflow");     //队满上溢    Q->count ++;                        //队列元素个数加1    Q->data[Q->rear]=x;                 //新元素插入队尾    Q->rear=(Q->rear+1)%QueueSize;      //循环意义下将尾指针加1}⑤⑤ 出队出队DataType DeQueue(CirQueue *Q) {     DataType temp;     if(QueueEmpty((Q))          Error("Queue underflow");     //队空下溢      temp=Q->data[Q->front];      Q->count--;                        //队列元素个数减1      Q->front=(Q->front+1)%QueueSize;         /*循环意义下的头指针加1*/      return temp;  }⑥⑥取队头元素取队头元素DataType QueueFront(CirQueue *Q) {       if(QueueEmpty(Q))                 Error("Queue if empty.");       return Q->data[Q->front]; }2.3链队列2.3.1 链队列的定义2.3.2 链队列的基本运算2.3.1 链队列的定义       队列的链式存储结构简称为链队列。

它是限制仅在表头删除和表尾插入的单链表 队头在链头，队尾在链尾队头在链头，队尾在链尾a1∧an…q.frontq.rearq.frontq.rear∧空队列空队列链队列的几种状态示意图此时，front==rear修改rear指针修改头结点的指针域①①链队列为空的特征：链队列为空的特征：front==rearfront==rear②② 链队列会满吗链队列会满吗？？一般不会，因为删除时有一般不会，因为删除时有freefree动作，除非内存不足！动作，除非内存不足！修改rear指针注意       增加指向链表上的最后一个结点的尾指针，便于在表尾做插入操作   ①和链栈类似，无须考虑判队满的运算及上溢②在出队算法中，一般只需修改队头指针但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空③以上讨论的是无头结点链队列的基本运算和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算定义链队列的存储结构typedef char DataType;typedef struct queuenode{   DataType data;    struct queuenode *next;}QueueNode;typedef struct  {QueueNode * front; QueueNode *rear;} LinkQueue;2.3.2 链队列的基本运算1.置空队2.判队空3.入队4.出队5.取队头元素（1） 置空队int InitQueue( LinkQueue *Q )int InitQueue( LinkQueue *Q ){ { ////构造一个空队列构造一个空队列 * *Q Q Q->front = (LQnode *)malloc(sizeof(LQnode)); Q->front = (LQnode *)malloc(sizeof(LQnode)); if( Q->front == NULL ) if( Q->front == NULL ) return FALSE; return FALSE; ////申请内存失败返回申请内存失败返回 Q->rear = Q->front;Q->rear = Q->front; Q->front Q->front-> next = NULL;next = NULL; return TRUE; return TRUE; ////申请内存成功返回申请内存成功返回} }（2） 判队空 int QueueEmpty(LinkQueue *Q){return Q-> front-> next ==NULL&&Q->rear->next==NULL;/*实际上只须判断队头指针是否为空即可*/}（3） 入队void EnQueue(LinkQueue *Q,DataType x){//将元素x插入链队列尾部  QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));     //申请新结点   p->data=x;   p->next=NULL;   if(QueueEmpty(Q))   { Q->front->next=p;      Q->rear=p; } //将x插入空队列    else { //x插入非空队列的尾          Q->rear->next=p;     //*p链到原队尾结点后          Q->rear=p;           //队尾指针指向新的尾        }}（4） 出队DataType DeQueue (LinkQueue *Q){   DataType x;     QueueNode *p;     if(QueueEmpty(Q))          Error(“Queue underflow”);//下溢     p=Q->front->next;                   //指向队头结点     x=p->data;                    //保存队头结点的数据     Q->front->next=p->next; //将队头结点从链上摘下     if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空      { Q->rear= Q->front;}     free(p);   //释放被删队头结点     return x;  //返回原队头数据  }（5） 取队头元素      DataType QueueFront(LinkQueue *Q)       {             if(QueueEmpty(Q))                  Error("Queue if empty.");              return Q->front->next->data;        }3. 栈的应用3.1 函数调用3.2 递归、非递归 当在一个函数的运行期间当在一个函数的运行期间调用另一个函数调用另一个函数时时, 在在运行该被调用函数之前运行该被调用函数之前, 需先完成三项任务：需先完成三项任务：①① 保存现场保存现场, 保存本函数参数、返回地址等保存本函数参数、返回地址等信息信息;②② 为被调用函数的局部变量为被调用函数的局部变量分配存储区分配存储区传递参数传递参数;③③ 将将控制转移控制转移到被调用函数的入口。

到被调用函数的入口3.1 函数调用 从被调用函数从被调用函数返回返回调用函数调用函数之前之前, 应该完成下列应该完成下列三项任务：三项任务：①①保存保存返回的返回的计算结果计算结果(用函数名用函数名,引用参数引用参数) ；；②②释放释放被调函数的被调函数的数据区数据区, 恢复调用函数现场恢复调用函数现场 ;③③依照被保存的返回地址将依照被保存的返回地址将控制转移控制转移到调用函数到调用函数多个函数嵌套调用的规则多个函数嵌套调用的规则此时的内存管理实行此时的内存管理实行“栈式管理栈式管理”后调用先返回后调用先返回 ！！例如：例如：main( ) void a( ) void b( ){ … { … { … a( ); b( ); … …}//main }// a }// bmain的数据区函数a的数据区函数b的数据区 栈在函数调用中的作用过程一过程二过程三过程四断点三断点一断点二断点一断点二断点三stack调用子程序返回断点程序执行 数据结构---第3章 栈和队列723.2 递归、非递归[递归的含义递归的含义]             函数、过程或者数据结构的内部又直接或者间接地由自身定义。

[适合于应用递归的场合适合于应用递归的场合]规模较大的问题可以化解为规模较小的问题，且二者处理(或定义)的方式一致；当问题规模降低到一定程度时是可以直接求解的(终止条件)     例1.    阶乘 n!=     1                 n=0                                  n×(n-1)!     n>0数据结构---第3章 栈和队列73[写递归算法应注意的问题写递归算法应注意的问题]–递归算法本身不可以作为独立的程序运行，需在其它的程序中设置调用初值，进行调用；–递归算法应有出口(终止条件)    例1.  求n！int Factorial(int n){ if (n==0) return(1); return n*Factorial(n-1);}//Factorial数据结构---第3章 栈和队列74[递归算法的实现原理递归算法的实现原理]123s123- 利用栈，栈中每个元素称为工作记录，分成三个部分： 返回地址 实际参数表(变参和值参) 局部变量- 发生调用时，保护现场，即当前的工作记录入栈，然后 转入被调用的过程- 一个调用结束时，恢复现场，即若栈不空，则退栈，从 退出的返回地址处继续执行下去75[递归时系统工作原理示例递归时系统工作原理示例]int  Factorial( int  n){           L1:      if ( n==0 )             L2:              return  1;             L3:      else     return  n*Factorial(n-1);             L4:  } //Factorial     void main(void)     {    ……     L0: N=Factorial(3);         ……     } //main                  返回地址  n   Factorial  NL0 3 / / L3 3 /L3 2 /L3 1 / 1126数据结构---第3章 栈和队列76[递归算法的用途递归算法的用途]–求解递归定义的数学函数–在以递归方式定义的数据结构上的运算/操作–可用递归方式描述的解决过程[递归算法的特点递归算法的特点]–递归算法简单明了，直观易懂–时间效率低，空间开销大，算法不易优化数据结构---第3章 栈和队列77[递归转换为非递归的方法递归转换为非递归的方法]1）采用迭代算法）采用迭代算法    递归—从顶到底    迭代—从底到顶       例：求n！               int  fact(int n)               {    m=1;                     for ( i=1; i<= n; i++)    m=m*i;                     return m;                }//fact数据结构---第3章 栈和队列782）消除尾递归）消除尾递归例：顺序输出单链表中的结点数据void linklist_output(LNode *p);{    if (p)      {   printf(p->data);           linklist_output(p->next)      }}//linklist_output使用跳转语句：void linklist_output1(LNode *p){ 1: if ( p ) { printf(p->data); p=p->next; goto 1 }}//linklist_output1使用循环语句：void linklist_output2(LNode *p){ while ( p ) { printf(p->data); p=p->next; }}//linklist_output2p^ana 2a1数据结构---第3章 栈和队列793)对递归算法改写对递归算法改写—通用方法（利用栈模拟递归）通用方法（利用栈模拟递归）如果是递归函数，需改写为递归过程如果是递归函数，需改写为递归过程     例：求n!      void   fact(int n, int &f)      {0: if (n==0)    f=1;            else  [  1: fact(n-1,f);                        2: f=n*f                       ]       } //fact InitStack(S);Push( S, (2, n, f ));n=n-1; goto 0; if ( !StackEmpty(S) ) { (S.top-1)->f=f; //还原本层变参值 Pop(S, (rd, n, f) ); goto rd ;} 80  自设栈模拟系统工作栈自设栈模拟系统工作栈   例例：：typedef  struct  {                   int  rd;                   int  n;                   int  f;            }SElemType; 改写算法改写算法–在程序开头增加栈的初始化语句–改写递归调用语句  入栈处理；                                      确定调用的参数值；                                      转至调用的开始语句–改写所有递归出口  退栈还原参数；                                      转至返回地址处Srd n ftopvoid fact(int n; int &f) { InitStack(S);0: if (n==0) f=1; else { 1: Push( S, (2, n, f )); n=n-1; goto 0;  2: f:=n*f; }   if ( !StackEmpty(S) ) { (S.top-1)->f=f; Pop(S, (rd, n, f) ); goto rd ; } }//factvoid fact(int n; int &f ) { InitStack(S); while (n!=0) { Push (S, n); n=n-1; } f=1; while ( !StackEmpty(S) ) { Pop (S, n); f=n*f; }}//fact注：此时可确定栈中只 存放n值即可。

typedef int SElemType;。