队列的定义、表示、实现讲述.ppt

1 3.1 栈（Stack） 3.2 队列 （Queue) 第三章 栈和队列 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 1. 定义 2. 逻辑结构 3. 存储结构 4. 运算规则 5. 实现方式 2 3.2 队列 只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 1. 定义 一、概念： 例如：队列 Q= (a1 , a2 , a3 , …， an ) 在队尾插入元素称为入队； 在队首删除元素称为出队。 队头元素 队尾元素 允许插入的一端为队尾，允许删除的一端为队头。 3 与线性表相同，仍为一对一关系。 顺序队或链队，以循环顺序队更常见。 只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。 关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 队列 链队列：队列的链式表示和实现 循环队列：队列的顺序表示和实现 4 （1）初始化队列 InitQueue(Q) （2）入队 EnQueue(Q,e) （3）出队 DeQueue(Q,e) （4）获取队头元素内容 GetHead(Q,e) （5）判断队列是否为空 QueueEmpty(Q) 二、基本操作: 建队列、判断队列是否为空、入队、出队、读队头元素值，等等。 5 链队列类型定义： typedef struct { QueuePtr front ; //队头指针 QueuePtr rear ; //队尾指针 } LinkQueue; 结点类型定义： typedef struct QNode { QElemType data; //元素 struct QNode *next; //指向下一结点的指针 } Qnode , * QueuePtr ; 关于整个链队的总体描述 链队中任一结点的结构 三、队列的表示和实现 1.单链队列 // -----队列的链式存储结构----- 和单链表唯一的区别是多了一个队尾指针 为什么要使用队首指针和队尾？？？ 如果固定队头，那么每次出队后，后面若干条数 据都会往前挪。增加了开销量和浪费。 为此，将买票窗口活动起来（即增加一个队首指针） ，出队后，后面的队列不需要移动。 队列可以看成： “很窄的单向胡同”。 “多台电脑共用一台打印机设备（优先级相等）” 头指针和尾指针避免了删除时的挪动。 7 a1 ∧ an … Q.front Q.rear Q.front Q.rear ∧ 空队列 为了操作方便，添加一个头结点，令头指针指向头结点。 Q. front==Q. rear 队空的条件：Q.front = Q.rear;(有头结点） Q.front = NULL;(无头结点) 8 Status InitQueue (LinkQueue Q) { // 构造一个空队列 Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit (OVERFLOW); //存储分配失败 Q.front-next = NULL;//头结点的next域为空 return OK; } // -----基本操作的算法描述----- 建队操作——构造空队列Q 9 链队会满吗？ 一般不会，因为删除时有free动作。除非内存不足！ 入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：p=front-next; //P指向第一个元素 front-next=p-next; free(p); 链队列的入队和出队操作 10 Status EnQueue (LinkQueue Q, QElemType e) { // 插入元素e为Q的新的队尾元素 p = (QueuePtr) malloc (sizeof (QNode)); if (!p) exit (OVERFLOW); //存储分配失败