第3章栈和队列课件.ppt

1、3.1.1 栈的基本概念栈的基本概念图图3-1 顺序顺序栈示意图栈示意图a1a2aian bottomtop进栈（进栈（push）出栈出栈(pop)栈的抽象数据类型定义栈的抽象数据类型定义ADT Stack数据对象：数据对象：D=ai|aiElemSet,i=1,2,n，n0 数据关系：数据关系：R=|ai-1，aiD,i=2,3,n 基本操作：初始化、进栈、出栈、取栈顶元素等基本操作：初始化、进栈、出栈、取栈顶元素等 ADT Stack图图3-2 (动态动态)堆栈变化示意图堆栈变化示意图空栈空栈bottomtop元素元素a进栈进栈bottomtopa元素元素b，c进栈进栈bottomtopa

2、bc元素元素c退栈退栈bottomtopabbottomtopabdef元素元素d，e，f进栈进栈图图3-3 静态静态堆栈变化示意图堆栈变化示意图空栈空栈bottomtopTop=11个元素进栈个元素进栈bottomtopaTop=33个元素进栈个元素进栈bottomtopabcTop=4栈满栈满bottomtopabedTop=2元素元素c进栈进栈bottomtopab空栈空栈top 非空栈非空栈top a4 a3 a1 a2栈存储形式栈存储形式空栈空栈top 非空栈非空栈top a4 a3 a1 a2栈存储形式栈存储形式链栈的链栈的结点类型说明如下：结点类型说明如下：typedef str

3、uct Stack_Node ElemType data;struct Stack_Node *next;Stack_Node,*LinkStack;采用静态顺序栈方式实现采用静态顺序栈方式实现 void conversion(int n,int d)/将将十进制整数十进制整数N转换为转换为d(2或或8)进制数进制数 SqStack S;int k,*e;S=Init_Stack();while (n0)k=n%d;push(S,k);n=n/d;/求出所有的余求出所有的余数，数，进栈进栈 while (S.top!=0)/栈不空时出栈，输出栈不空时出栈，输出 pop(S,e);printf(

4、“%1d”,*e);Fact(n)=1 当当n=0时时 终止条件终止条件n*fact(n-1)当当n0时时 递推规则递推规则 为保证递归调用正确执行，系统设立一个为保证递归调用正确执行，系统设立一个“递归递归工作栈工作栈”，作为整个递归调用过程期间使用的数据存，作为整个递归调用过程期间使用的数据存储区。储区。每一层递归包含的信息如：每一层递归包含的信息如：参数参数、局部变量局部变量、上上一层的返回地址构成一层的返回地址构成一个一个“工作记录工作记录”。每进入一层。每进入一层递归，就产生一个新的工作记录压入栈顶；每退出一递归，就产生一个新的工作记录压入栈顶；每退出一层递归，就从栈顶弹出一个工作记

5、录。层递归，就从栈顶弹出一个工作记录。从被调函数返回调用函数的一般步骤：从被调函数返回调用函数的一般步骤：(1)若栈为空，则执行正常返回。若栈为空，则执行正常返回。从栈顶弹出一个工作记录。从栈顶弹出一个工作记录。将将“工作记录工作记录”中的参数值、局部变量值赋给中的参数值、局部变量值赋给相应的变量；读取返回地址。相应的变量；读取返回地址。将函数值赋给相应的变量。将函数值赋给相应的变量。(5)转移到返回地址。转移到返回地址。3.3.1 队列及其基本概念队列及其基本概念a1,a2,an出队出队入队入队队尾队尾队首队首图图3-5 队列示意图队列示意图2 队列的抽象数据类型定义队列的抽象数据类型定义A

6、DT Queue数据对象：数据对象：D=ai|aiElemSet,i=1,2,n,n=0 数据关系：数据关系：R=|ai-1,aiD,i=2,3,n 约定约定a1端为队首，端为队首，an端为队尾。端为队尾。基本操作：基本操作：Create()：创建一个空队列：创建一个空队列；EmptyQue()：若队列为空：若队列为空，则返回则返回true，否则返回否则返回flase；InsertQue(x)：向队尾插入元素：向队尾插入元素x；DeleteQue(x)：删除队首元素：删除队首元素x；ADT Queue 利用利用一组连续的存储单元一组连续的存储单元(一维数组一维数组)依次存放从队依次存放从队首到

7、队尾的各个元素，称为首到队尾的各个元素，称为顺序队列顺序队列。对于队列，和顺序栈相类似，也有动态和静态之分。对于队列，和顺序栈相类似，也有动态和静态之分。本部分介绍的是本部分介绍的是静态顺序队列静态顺序队列，其类型定义如下：，其类型定义如下：#define MAX_QUEUE_SIZE 100typedef struct queue ElemType Queue_arrayMAX_QUEUE_SIZE;int front;int rear;SqQueue;设立一个设立一个队首指针队首指针front，一个，一个队尾指针队尾指针rear，分，分别指向队首和队尾元素别指向队首和队尾元素。初始化初始化

8、：front=rear=0。入队入队：将新元素插入将新元素插入rear所指的位置，然后所指的位置，然后rear加加1。出队出队：删去删去front所指的元素，然后加所指的元素，然后加1并返回被删并返回被删元素。元素。队列为空队列为空：front=rear。队满队满：rear=MAX_QUEUE_SIZE-1或或front=rear。(a)空队列空队列Q.frontQ.rear(b)入队入队3个元素个元素a3a2a1Q.frontQ.rear(c)出队出队3个元素个元素Q.frontQ.rear(d)入队入队2个元素个元素a5a4Q.frontQ.rear图图3-6 队列示意图队列示意图 为充分

9、利用向量空间，克服上述为充分利用向量空间，克服上述“假溢出假溢出”现象的现象的方法是：将为队列分配的方法是：将为队列分配的向量空间看成为一个首尾相接向量空间看成为一个首尾相接的圆环的圆环，并称这种队列为，并称这种队列为循环队列循环队列(Circular Queue)。在循环队列中进行出队、入队操作时，队首、队尾在循环队列中进行出队、入队操作时，队首、队尾指针仍要加指针仍要加1，朝前移动。只不过当队首、队尾指针指，朝前移动。只不过当队首、队尾指针指向向量上界向向量上界(MAX_QUEUE_SIZE-1)时，其加时，其加1操作的结操作的结果是指向向量的下界果是指向向量的下界0。123450(a)空

10、队列空队列frontrear123450(b)d,e,b,g入入队队frontdebgrear123450(c)d,e出队出队bgfrontrear123450(d)i,j,k入入队队bgfrontijkrear123450(e)b,g出队出队ijkrearfront123450(f)r,p,s,t入队入队ijkfrontrprear图图3-7 循环队列操作及指针变化情况循环队列操作及指针变化情况2 入队操作入队操作Status Insert_CirQueue(SqQueue Q,ElemType e)/将数据元素将数据元素e插入到循环队列插入到循环队列Q的队尾的队尾 if (Q.rear+1

11、)%MAX_QUEUE_SIZE=Q.front)return ERROR;/队满，返回错误标志队满，返回错误标志 Q.Queue_arrayQ.rear=e;/元素元素e入队入队 Q.rear=(Q.rear+1)%MAX_QUEUE_SIZE;/队尾指针向前移动队尾指针向前移动 return OK;/入队成功入队成功3 出队操作出队操作Status Delete_CirQueue(SqQueue Q,ElemType *x)/将循环队列将循环队列Q的队首元素出队的队首元素出队 if (Q.front+1=Q.rear)return ERROR;/队空，返回错误标志队空，返回错误标志 *x=

12、Q.Queue_arrayQ.front;/取队首元素取队首元素 Q.front=(Q.front+1)%MAX_QUEUE_SIZE;/队首指针向前移动队首指针向前移动 return OK;数据元素结点数据元素结点data指针结点指针结点front rear图图3-8 链队列结点示意图链队列结点示意图数据元素结点类型定义：数据元素结点类型定义：typedef struct Qnode ElemType data;struct Qnode *next;QNode;数据元素结点数据元素结点data指针结点指针结点front rear图图3-8 链队列结点示意图链队列结点示意图图图3-9 队列操作

13、及指针变化队列操作及指针变化(a)空队列空队列front rear(b)x入队入队 x front rear(c)y再入队再入队 y front rear x(d)x出队出队 y xfront rear3 链队列的基本操作链队列的基本操作 链队列的初始化链队列的初始化LinkQueue*Init_LinkQueue(void)LinkQueue *Q;QNode *p;p=(QNode*)malloc(sizeof(QNode);/开辟头结点开辟头结点p-next=NULL;Q=(LinkQueue *)malloc(sizeof(LinkQueue);/开辟链队的指针结点开辟链队的指针结点

14、Q.front=Q.rear=p;return(Q);链队列的链队列的入队操作入队操作 在已知队列的队尾插入一个元素在已知队列的队尾插入一个元素e，即，即修改队尾修改队尾指指针针(Q.rear)。Status Insert_CirQueue(LinkQueue *Q,ElemType e)/将数据元素将数据元素e插入到链队列插入到链队列Q的队尾的队尾 p=(QNode*)malloc(sizeof(QNode);if(!p)return ERROR;/申请新结点失败，返回错误标志申请新结点失败，返回错误标志 p-data=e;p-next=NULL;/形成新结点形成新结点 Q.rear-nex

15、t=p;Q.rear=p;/新结点插入到队尾新结点插入到队尾 return OK;链队列的出队操作链队列的出队操作Status Delete_LinkQueue(LinkQueue *Q,ElemType*x)QNode*p;if (Q.front=Q.rear)return ERROR;/队空队空 p=Q.front-next;/取队首结点取队首结点*x=p-data;Q.front-next=p-next;/修改队首指针修改队首指针if (p=Q.rear)Q.rear=Q.front;/当队列只有一个结点时应防止丢失队尾指针当队列只有一个结点时应防止丢失队尾指针 free(p);return OK;链队列的撤消链队列的撤消void Destroy_LinkQueue(LinkQueue *Q)/将链队列将链队列Q的队首元素出队的队首元素出队 while (Q.front!=NULL)Q.rear=Q.front-next;/令尾指针指向队列的第一个结点令尾指针指向队列的第一个结点 free(Q.front);/每次释放一个结点每次释放一个结点 /第一次是头结点，以后是元素结点第一次是头结点，以后是元素结点 Q.ront=Q.rear;