ch3一栈的应用和创建.ppt

说明：设（a1,a2 , a3 , ... , an ）为一队列1）表尾称作队尾，表头称为队头；2）a1为队头元素，an为队尾元素；3）在表尾插入元素操作，称为入队操作；在表头删除元素的操作，称为出队操作；4）元素按a1,a2, a3, ... an 顺序入队，第一个入队的元素为a1 最后一个入队的元素是an 第一个出队的元素为a1 ； 5）队列具有先进先出的特点，所以又称为先进先出表（FIFO表）? a1 a2 a3 an 入队列 队头 队尾 出队列 队列的示意图 队列的特点 先进先出 第一个入队的元素在队头，最后一个入队的元素在队尾， 第一个出队的元素为队头元素， 最后一个出队的元素为队尾元素 队列类似于日常的排队，新来的人站在队尾，队头的人进行事务处理后离队。 队列通常设置两个变量分别指示队头元素位置和队尾元素的位置，这两个变量分别称为队头指针、队尾指针； a1 a2 a3 an 插入 端点1 端点2 删除 双端队列的示意图 双端队列：限定插入和删除操作在表的两端进行的线性表。两个端点分别称作端点1和端点2。 删除 插入 二 队列的基本操作 1）初始化操作InitQueue( Q) 功能：构造一个空队列Q；2）销毁操作DestroyQueue( Q) 功能：销毁已存在队列Q；3）置空操作ClearQueue(Q) 功能： 将队列Q置为空队列 ； 4）判空操作QueueEmpty(Q) 功能：若队列Q为空，则返回True，否则返回False；5）取队头元素操作GetHead(Q,e) 功能：取队头元素，并用e返回；6）入队操作EnQueue( Q, e )  功能：将元素e插入Q的队尾；7）出队操作DeQueue( Q, e)  功能：若队列不空，则删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR； 3.4.2 链队列——队列的链式存储结构和实现 一 什么是链队列 用链表存储的队列称为链队列 Q.front Q.rear ∧ 空链队列 J1 ∧ Q.front Q.rear J2 ∧ 链队列图示 二 链队列的类型定义 typedef struct QNode{ //链队列结点的类型定义 QElemType data;  struct QNode *next; }QNode,*QueuePtr; typedef struct { //链队列的表头结点的的类型定义 QueuePtr front; //队头指针，指向链表的头结点 QueuePtr rear; //队尾指针，指向队尾结点}LinkQueue; ·QNode：结构类型； Qnode 类型结构变量有两个域： data：用于存放队列元素， next：用于存放元素直接后继结点的地址；· Qnode 类型结构变量表示链队列的一个结点；·QueuePtr：指针类型；· QueuePtr 类型指针变量用于存放链队列结点的地址； LinkQueue:结构类型, LinkQueue类型的变量用于存放队头指针、队尾指针； J1 ∧ Q.front Q.rear J2 ∧ 设Q为LinkQueue类型的变量，Q为链队列的表头结点，用于存储队列队头指针和队尾指针；初始建队时，令Q.front-next=null; Q.front Q.rear ∧ 空链队列 链队列图示 链队列的 头结点 1）初始化操作InitQueue_L(LinkQueue Q) Status InitQueue_L(LinkQueue Q) { //建一个空队列Q Q.from=Q.rear=(QueuePtr)malloc(sizeof(QNode)); //为链队列的头结点 //分配空间  if (!Q.front) exit(OVERFLOW); Q.front-next=NULL; return OK;} //InitQueue_L 二 链队列基本操作算法 Q.front Q.rear ∧ 空链队列 链队列的 头结点 2) 销毁操作Destr