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

教学目标 1、知识目标 1）掌握栈的定义及基本运算； 2）掌握顺序栈、链栈基本运算的实现算法。 3）掌握队列的定义及基本运算； 4）掌握循环队列、链队列基本运算的实现算法。 2、能力目标 1）具有恰当的选择栈作为数据的逻辑结构、顺序栈，链栈作为数据的存储结构的能力； 2）具有恰当的选择队列作为数据的逻辑结构、循环队列、链队列作为数据的存储结构的能力； 3）具有应用栈和队列解决实际问题的能力。 3、素质目标 养成分工合作、团结协作的良好协作精神。,3.1 栈的定义及基本操作 栈是一种特殊的线性表，它的逻辑结构与线性表相同，只是其运算规则较线性表有更多的限制，故又称它为运算受限的线性表。 1、栈的定义 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。向栈中插入元素称为进（入）栈，从栈中删除元素称为退（出）栈。 通常插入、删除的这一端称为栈顶，由于元素的进栈和退栈，使得栈顶的位置经常是变动的，因此需要用一个整型量Top指示栈顶的位置，通常称Top 为栈顶指针；另一端称为栈底。 当表中没有元素时称为空栈，即Top=-1。 栈为后进先出（Last In First Out）的线性表，简称为LIFO表。,栈为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次删除的总是当前栈中“最新”的元素，即最后插入的元素，而最先插入的是被放在栈的底部，要到最后才能删除。 在现实生活中，我们见到的手枪的弹夹就是一个栈，装入子弹时，需要从弹夹的顶部一个个的放入，子弹射出时，需要从弹夹的顶部一个个的射出，最后装入的被最先射出，最先装入的只有到最后才能被射出。 栈可以用下图来表示：,2、栈的基本运算 （1）置空栈：InitStack (S) 构造一个空栈S。 （2）判栈空：StackEmpty (S) 若S为空栈，则返回1，否则返回0。 （3）判栈满：StackFull (S) 若S为满栈，则返回1，否则返回0。 （4）进栈：Push(S，x) 若栈S不满，则将元素x插入S的栈顶。 （5）退栈：Pop (S) 若栈S非空，则将S的栈顶元素删去，并返回该元素。 （6）取栈顶元素：StackTop (S) 若栈S非空，则返回栈顶元素，但不改变栈的状态。,3.2 顺序栈及基本操作的实现 由于栈是运算受限线性表，因此线性表的存储结构对栈也适用，而线性表有顺序存储和链式存储两种，所以，栈也有顺序存储和链式存储两种。 1、顺序栈：栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表。 2、顺序栈的描述 3、顺序栈的基本操作 设S是SeqStack类型的指针变量。若栈底位置在向量的低端，即S-data0是栈底元素。 （1）进栈操作 进栈时，需要将S-top加1。 S-top=StackSize-1表示栈满 上溢：当栈满时，再做进栈运算所产生的空间溢出现象称为上溢。上溢是一种出错状态，应设法避免。,2、顺序栈的描述 #define StackSize 100 /假定栈空间最多为100个元素 typedef char DataType;/假定栈元素的类型为字符类型 typedef struct DataType dataStackSize;/栈元素定义 int top;/栈指针定义 SeqStack; SeqStack *S;/栈定义,8,（2）退栈操作 退栈时，需将S-top减1。 S-top=-1表示空栈 下溢：当栈空时，做退栈运算所产生的溢出现象称为下溢。 顺序栈在进栈和退栈操作时的具体变化情况如下图： 4、顺序栈上六种基本运算的算法 （1） 置栈空 （2） 判栈空 如果栈S为空，则S-top=-1，此时应该返回1，而关系表达式S-top=-1的值为1；如果栈S为非空，则S-top!=-1，此时应该返回0，而关系表达式S-top=-1的值为0，因此，无论怎样只需返回S-top=-1的值。,（1） 置栈空 void InitStack（SeqStack *S） /将顺序栈置空 S-top=-1; ,8,（2）判栈空 int StackEmpty（SeqStack *S） return S-top=-1; ,（3） 判栈满 与判栈空的道理相同，只需返回S-top=StackSize-1。 （4） 进栈 进栈操作需要将栈和进栈元素的值作为函数参数,由于使用栈指针作为函数参数,对栈进行操作，所以进栈函数不需要有返回值;进栈操作时,需要判断是否栈满,当栈不满时,先将栈顶指针加1,再进栈。 （5） 退栈 退栈操作需要将栈指针作为函数参数，并返回栈顶元素的值,所以函数返回值的类型为DataType；退栈操作时，需要判断是否栈空，当栈不空时，先退栈，再将栈顶指针减1，可以先将栈顶元素的值记录下来，然后栈顶指针减1，最后返回记录下来的值，也可以像给出的退栈函数那样来操作。 （6） 取栈顶元素 取栈顶元素与退栈的区别在于，退栈需要改变栈的状态，而取栈顶元素不需要改变栈的状态。,（3） 判栈满 int StackFull（SeqStack *S） return S-top=StackSize-1; ,9,（4）进栈 void Push（SeqStack *S，DataType x） if (StackFull(S) puts(“栈满“); exit(0);/栈满时，退出程序运行 S-data+S-top=x;/栈顶指针加1后将x入栈 ,9,（5）退栈 DataType Pop（SeqStack * S） if(StackEmpty(S) puts(“栈空“); exit(0);/栈空时，退出程序运行 return S-dataS-top-;/返回栈顶元素并将栈顶指针减1 ,9,（6）取栈顶元素 DataType StackTop（SeqStack *S） if(StackEmpty(S) puts(“栈空“); exit(0); return S-dataS-top; ,3.3链栈及基本操作的实现 1、链栈 栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，所以没有必要附加头结点。栈顶指针就是链表的头指针。链栈示意图如下： 2、链栈的描述 注意： LinkStack结构类型的定义是为了方便在函数体中修改top指针本身； 若要记录栈中元素个数，可将元素个数属性作为LinkStack类型中的成员定义。,10,2、链栈的描述 typedef char DataType;/假定栈元素的类型为字符类型 typedef struct stacknode/结点的描述 DataType data; struct stacknode *next; StackNode; typedef struct/栈的描述 StackNode *top; /栈顶指针 LinkStack;,3、 链栈上基本运算的算法 （1） 置栈空 （2） 判栈空 （3） 进栈 （4） 退栈 （5） 取栈顶元素 注：由于链栈中的结点是动态分配的，可以不考虑上溢，所以无须定义StackFull运算。,（1） 置栈空 void InitStack（LinkStack *S） /将链栈置空 S-top=NULL; ,11,（2） 判栈空 int StackEmpty（LinkStack *S） return S-top=NULL; ,（3） 进栈 void Push（LinkStack *S，DataType x ） /将元素x插入链栈头部 StackNode *p=(StackNode *)malloc(sizeof(StackNode); 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) puts(“栈空”); exit(0);/下溢，退出运行 x=p-data; /保存栈顶结点数据 S-top=p-next; /将栈顶结点从链上摘下 free(p); return x; ,11,11,11,（5） 取栈顶元素 DataType StackTop（LinkStack *S） if(StackEmpty(S) puts(“栈空”); exit(0); return S-top-data; ,3.4 队列的定义及基本操作 队列与栈一样都是运算受限的线性表，但与栈的限制不同。 1、队列的定义 队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。向队列中插入元素称为入队，从队列中删除元素称为出队。 (1)允许删除的一端称为队头。 (2)允许插入的一端称为队尾。 (3)当队列中没有元素时称为空队列。 (4)队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。 队列的修改是依先进先出的原则进行的。新来的成员总是加入队尾（即不允许“加塞”），每次离开的成员总是队列头上的成员（不允许中途离队），即当前“最老的”成员离队。,2、队列的基本运算 1）置空队：InitQueue (Q)构造一个空队列Q。 2）判队空：QueueEmpty (Q)若队列Q为空，则返回真值，否则返回假值。 3）判队满：QueueFull (Q)若队列Q为满，则返回真值，否则返回假值。 注意：此操作只适用于队列的顺序存储结构。 4）入队：EnQueue(Q，x)若队列Q非满，则将元素x插入Q的队尾。 5）出队：DeQueue (Q)若队列Q非空，则删去Q的队头元素，并返回该元素。 6） 取队头元素：QueueFront (Q)若队列Q非空，则返回队头元素，但不改变队列Q的状态。,3.4 顺序队列及基本操作的实现 1、顺序队列：队列的顺序存储结构称为顺序队列，它是运算受限的顺序表。 2、顺序队列的表示 和顺序表一样，顺序队列用一个数组（向量空间）来存放当前队列中的元素。 由于随着入队和出队操作的变化，队列的队头和队尾的位置是变动的，所以应设置两个整型量front和rear分别指示队头和队尾在向量空间中的位置，它们的初值在队列初始化时均应置为0。通常称front为队头指针，称rear为队尾指针。 3、顺序队列的基本操作 入队：入队时将新元素插入rear所指的位置，然后将rear加1。 出队：出队时删去front所指的元素，然后将front加1并返回被删元素。,注意： 当头尾指针相等时，队列为空。 在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。 顺序队列基本操作如图：,4、顺序队列中的溢出现象 “下溢”现象：当队列为空时，做出队运算产生的溢出现象。 “真上溢”现象：当队列满时，做入队运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。 “假上溢”现象：由于入队和出队操作中，头尾指针只增加不减少，致使被删元素的空间永远无法重新利用。当队列中实际元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为“假上溢”现象。 5、解决“假上溢”现象的方法 当出现“假上溢”现象时，把所有的元素向低位移动，使得空位从低位区移向高位区，显然这种方法很浪费时间。 把队列的向量空间的元素位置0Queuesize-1看成一个首尾相接的环形，当进队的队尾指针等于最大容量，即rear=Queuesize时，使rear=0。,3.5 循环队列 1、循环队列：把向量空间的元素位置首尾相接的顺序队列称为循环队列。循环队列示意图： 2、循环队列头尾指针的操作 循环队列进行出队、入队操作时，头尾指针仍要加1。当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： 利用选择结构 if(i+1=QueueSize)/i为front或rear i=0; else i+; 利用模运算 i=(i+1)%QueueSize;/i为front或rear,3、循环队列边界条件的处理方法 循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是“空”还是“满”。解决这个问题的方法至少有三种： 另设一标志变量flag以区别队列的空和满，比如当条件front=rear成立，且 flag 为0时表示队列空，而为1时表示队列满； 少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）； 使用一个计数器count记录队列中元素的总数，当count =0时表示队列空；当count =QueueSize时表示队列满。 我们将使用此方法。,4、循环队列的描述 #define QueueSize 100 /定义队列最大容量 typedef char DataType; /定义队列元素类型 typedef struct cirqueue DataType dataQueueSize;/队列元素定义 int front; /头指针定义 int rear; /尾指针定义 int count; /计数器定义 CirQueue; 5、循环队列的基本运算 置队空； 判队空； 判队满； 入队； 出队； 取队头元素。,11,11,11,11, 置队空 void InitQueue(CirQueue *Q) Q-front=Q-rear=0; Q-count=0; /计数器置0 , 判队空 int QueueEmpty(CirQueue *Q) return Q-count=0; /队列无元素为空 , 判队满 int QueueFull(CirQueue *Q) return Q-count=QueueSize; /队中元素个数等于QueueSize时队满 , 入队 void EnQueue(CirQueue *Q,DataType x) if(QueueFull(Q) puts(“队满”); exit(0); /队满上溢 Q-count +; /队列元素个数加1 Q-dataQ-rear=x; /新元素插入队尾 Q-rear=(Q-rear+1)%QueueSize; /循环意义下将尾指针加1 , 出队 DataType DeQueue(CirQueue *Q) DataType temp; if(QueueEmpty(Q) puts(“队空”); exit(0); /队空下溢 temp=Q-dataQ-front; Q-count-; /队列元素个数减1 Q-front=(Q-front+1)%QueueSize; /循环意义下的头指针加1 return temp; ,取队头元素 DataType QueueFront(CirQueue *Q) if(QueueEmpty(Q) puts(“队空”); exit(0); return Q-dataQ-front; ,11,3.6 链队列及基本操作的实现 1、链队列：队列的链式存储结构称为链队列，它是限制仅在表头删除和表尾插入的单链表。由于需要在表尾进行插入操作，所以为操作方便除头指针外有必要再增加一个指向尾结点的指针。 2、链队列的描述 typedef struct queuenode/队列中结点的类型 DataType data; struct queuenode *next; QueueNode; typedef struct QueueNode *front; /队头指针 QueueNode *rear; /队尾指针 LinkQueue; 3、链队列示意图,13,13,13,13,13,4、链队列的基本运算 由于链队列结点的存储空间是动态分配的，所以无须考虑判队满的运算。 置空队 判队空 入队 出队 取队头元素 注意：在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。,置空队 void InitQueue(LinkQueue *Q) Q-front=Q-rear=NULL; ,判队空 int QueueEmpty(LinkQueue *Q) return Q-front=NULL /实际上只须判断队头指针是否为空即可 ,入队 void EnQueue(LinkQueue *Q,DataType x) /将元素x插入链队列尾部 QueueNode *p; p=(QueueNode *)malloc(sizeof(QueueNode); p-data=x; p-next=NULL; if(QueueEmpty(Q) Q-front=Q-rear=p; /将x插入空队列 else /x插入非空队列的尾 Q-rear-next=p; /*p链到原队尾结点后 Q-rear=p; /队尾