160929101042575_第3章桟和队列要点.ppt

第*页;第*页;第3章 栈和队列 ;; 问题：已知共有n个饼并按照做出的顺序依次编号，排队等的m个人按照先后顺序编号，问第x个人买到的饼编号是什么？; 栈和队列是两种特殊的线性表，是操作受限的线性表。;3.1 栈;;;;;;;;;;;;奖 状;作业比较;小问题;;;;2．顺序栈的基本运算;对顺序栈来说，空栈的初始化和顺序表的初始化完全相同。这不奇怪，因为它们的结构是一样的。也就是说，并非对栈而言取不到除栈顶之外的元素，而是对栈类型来说，不允许这种操作。 ;（2） 取栈顶元素 Status GetTop (SqStack S, SElemType e){ 　// 若栈不空，则用 e 返回S的栈顶元素，并返回 OK；否则返回ERROR 　　if (S.top = = S.base) return ERROR;　　e = * (S.top - 1); 　　// 返回非空栈中栈顶元素　　return OK;　} ;（3） 出栈 Status Pop (SqStack S, SElemType e){ // 若栈不空，则删除S的栈顶元素，用e返回其值， 并返回OK,否则返回ERROR 　　if (S.top = = S.base) return ERROR;　　e = * - - S.top; 　　　　return OK;　};（4） 进栈 Status Push (SqStack S, SElemType e) // 插入元素e 为新的栈顶元素 { 　if (S.top－S.base==S.stacksize) return ERROR; *S.top ++ = e; 　return OK;　};;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;D;;#define MAXQSIZE 100 //最大队列长度 Typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针 int rear; //尾指针 }SqQueue; ;;　０　１　２　３ 0 1 2 3; 假上溢 和栈类似，队列中亦有上溢和下溢现象。此外，顺序队列中还存在“假上溢”现象。因为在入队和出队的操作中，头尾指针只增加不减小，致使被删除元素的空间永远无法重新利用。因此，尽管队列中实际的元素个数远远小于向量空间的规模，但也可能由于尾指针巳超出向量空间的上界而不能做入队操作。该现象称为假上溢。 ; 循环队列 为充分利用向量空间。克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量，存储在其中的队列称为循环队列（Circular Queue)。在循环队列中进行出队、入队操作??，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（MAXQSIZE-1）时，其加1操作的结果是指向向量的下界0。; 这种循环意义下的加1操作可以描述为： if(i+1==MAXQSIZE) i=0; else i++; 利用模运算可简化为： i=(i+1)%MAXQSIZE; ;;;;;;;;;;;;;;;;;;;;;;;;;;;435612中到了12顺序不能实现； 135426可以实现。