算法与数据结构-队列第3章2.pptVIP

3.2队列一、队列的类型定义 队列（Queue）：是一种只允许在表的一端插入，在另一端删除的存取受限的线性表。 队尾rear： 插入端，线性表的表尾。 队头front：删除端，线性表的表头 空队列：不含元素的空表 又称先进先出（First In First Out,FIFO）线性表。 队列的抽象数据类型： ADT Queue{ 数据对象：D={ai | ai ? ElemSet ， i=1，2，... ，n，n=0} 数据关系：R={ai-1 ，ai | ai-1 ，ai ? D ，i=2,...,n} 基本操作： 队列初始化： QueueInit () 入队： 　 QueueIn (Q , x), 出队：　 QueueOut (Q ) 读队头元素： QueueGetHead(Q ) 判队空： QueueEmpty (Q) }ADT Queue 二、队列的表示和实现 队列与线性表相同，有顺序存储结构和链式存储结构两种存储方法 顺序存储：循环队列 链式存储：链队列 队列的顺序表示和实现 队列的顺序存储： 数组+两个指针（队头，队尾）。 一般约定队头指针指向队头元素的前一个元素，队尾指针指向队尾元素。 顺序队列的类型定义如下： #define MAXSIZE 100 ∥队列可能最大长度 typedef struct {ElemType data[MAXSIZE]; int front，rear; }SeqQueue; SeqQueue Q: 队头元素Q.data[Q.front+1] 队尾元素Q.data[Q.rear] 不考虑溢出的情况下，入队操作： Q.rear++; Q.data[Q.rear]=x; 不考虑队空的情况下，出队操作： Q.front++ x=Q.data[Q.front]; //原队头元素送x 队满时：m=MAXSIZE 队空时：m=0 队列的顺序表示和实现 队列的顺序表示和实现 循环队列 空队列条件： Q.rear = Q.front; 满队列条件： Q.rear = Q.front; 解决方法是循环队列少用一个元素空间，以队尾指针加1等于队头指针为队满的标志，即（rear+1）%MAXSIZE=front。 循环队列的基本操作 1）初始化 SeqQueue SeqQueueInit() {∥ 初始化队列Q SeqQueue Q; Q.front=Q.rear=0; //队头指针和队尾指针初值 return Q; } 2） 判队空 Q.front==Q.rear 判队满 (Q.rear+1)%MAXSIZE==Q.front 队中元素个数： (Q.rear-Q.front+MAXSIZE)% MAXSIZE 3）入队 void SeqQueueIn(SeqQueue Q ， ElemType x) {∥插入元素x为Q的新的队尾元素 if((Q.rear+1)%MAXSIZE==Q.front) {printf(“队列满\n”); exit(0); } ∥队列满，退出运行 Q.rear=(Q.rear+1) % MAXSIZE; ∥计算队尾位置 Q.data[Q.rear]=x; ∥入队 } 4）出队 ElemType SeqQueueOut (SeqQueue Q) {if (Q.front==Q.rear) {printf(“Empty\n”); exit(0); }//队已空,退出运行 Q.front=( Q.front+1) % MAXSIZE; x=Q.data[Q.front]; //读出队头元素 return x; //出队完成 } 链队列 链队列的类型描述： typedef struct LQNode { ElemType data; struct LQNode *next; }LQNode,*LinkedQNode;//链队结点的类型及指针 typedef struct { Struct LQNode *front,*rear; } LQueue ,*LinkedQueue;//将头尾指针封装在一起的链队 LinkedQueue Q； 链队示意图 链队列的初始化 创建一个带头结点的空队 2） 判空 Q-front==Q-rear 判满 队头元素 Q-front-next-data; 队尾元素 Q-rear-data; 2）入队 void LinkedQueueIn(Li