第三章数据结构队列

1、也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为，允许插入的一端称为。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称。当队列中没有元素时称为。在空队列中依次加入元素a1,a2,an之后，a1是，an是。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。3.4 队列的类型定义队列的类型定义 ADT Queue 数据对象：数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系：数据关系：

2、R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头队列头， an 端为队列尾队列尾基本操作：基本操作：队列的抽象数据类型定义队列的抽象数据类型定义 ADT Queue队列的基本操作：队列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q, &e)ClearQueue(&Q)DeQueue(&Q, &e)EnQueue(&Q, e)QueueTraverse(Q, visit()InitQueue(&Q) 操作结果：

3、操作结果：构造一个空队列Q。DestroyQueue(&Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：队列Q被销毁， 不再存在。 QueueEmpty(Q)初始条件：初始条件：队列Q已存在。 操作结果：操作结果：若Q为空队列，则返回TRUE，否则返回FALSE。 QueueLength(Q) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：返回Q的元素个数，即队列的长度。 GetHead(Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：用e返回Q的队头元素。a1a2an ClearQueue(&Q)初始条件：初始条件：队列Q已

4、存在。 操作结果：操作结果：将Q清为空队列。 EnQueue(&Q, e) 初始条件：初始条件：队列Q已存在。 操作结果：操作结果：插入元素e为Q的新的队尾元素。a1a2ane DeQueue(&Q, &e) 初始条件：初始条件：Q为非空队列。 操作结果：操作结果：删除Q的队头元素，并用e返回其值。a1a2an 3.5 队列类型的实现队列类型的实现链队列链队列链式映象循环队列循环队列顺序映象 typedef struct QNode / 结点类型结点类型 QElemType data; struct QNode *next; QNode, *QueuePtr;链队列链队

5、列链式映象typedef struct / 链队列类型链队列类型 QueuePtr front; / 队头指针队头指针 QueuePtr rear; / 队尾指针队尾指针 LinkQueue;a1anQ.frontQ.rearQ.frontQ.rear空队列空队列非空队列非空队列 Status InitQueue (LinkQueue &Q) / 构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存储分配失败 Q.front-next = NULL; r

6、eturn OK; Status DestroyQueue (LinkQueue &Q) / 销毁队列Q while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front = Q.rear; return OK; Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素e为Q的新的队尾元素(尾插法） p = (QueuePtr) malloc (sizeof (QNode); if (!p) exit (OVERFLOW); /存储分配失败 p-data = e; p-next = N

7、ULL; Q.rear-next = p; Q.rear = p; return OK; Status DeQueue (LinkQueue &Q, QElemType &e) / 若队列不空，则删除Q的队头元素，（头删法） /用 e 返回其值，并返回OK；否则返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; /第一个结点也是最后一个结点 free (p); retur

8、n OK;非循环队列（顺序队列）非循环队列（顺序队列）队列的顺序存储结构称为顺序队列，顺序队队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个地址连续的空间来存放顺序队列也是必须用一个地址连续的空间来存放当前队列中的元素。由于队列的队头和队尾的位当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值在队和队尾元素在队列中的位置，它们的初始值在队列初始化时均应置为。入队时列初始化时均应置为。入队

9、时先将新元素插入先将新元素插入所指的位置，然后加所指的位置，然后加。出队时，。出队时，先删去所指的先删去所指的元素，然后加元素，然后加并返回被删元素。由此可见，当并返回被删元素。由此可见，当头尾指针相等时队列为空。头尾指针相等时队列为空。 0 1 2 3frontrearabcfront rear (a)队列初始为空（b）A,B,C入队 b c front rear front rear（c) a出队 (d) b,c出队，队为空 n队空：队空：Q.front=Q.rearn队满：队满：Q.rear-Q.front=maxsize（求队（求队长）长）n 入队：新元素按入队：新元素按 rear 指

10、示位置加入，指示位置加入，再将队尾指针加一再将队尾指针加一 ，即，即 Q.rear = Q.rear + 1n 出队：将出队：将front指示的元素取出，再将队指示的元素取出，再将队头指针加一，即头指针加一，即 Q.front = Q.front + 1非循环队列（顺序队列）非循环队列（顺序队列） 012345Q.rearQ.frontJ4J5J6012345Q.rearQ.frontJ3J8J7J3J4J5012345Q.rearQ.front初始状态J3,J4,J5出队J6,J7,J8入队如何判断队空队满现象？如何判断队空队满现象？队空：Q.front=Q.rear队满：Q.front=Q

11、.rear解决方案解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间： 队空：Q.front=Q.rear 队满：(Q.rear+1)%M=Q.front即队列头指针在队列尾指针的下一位置（指环状的下一位置）上012345Q.rearQ.frontJ4J5J6012345Q.rearQ.frontJ3J7J3J4J5012345Q.rearQ.front当前状态J3,J4,J5出队J6,J7入队队空：Q.front=Q.rear队满：(Q.rear+1)%M=Q.front解决方案：解决方案：少用一个元素空间：012345Q.rearQ.front初始状态J0,J1,J2,J3,

12、J4,J5入队入队J0,J1,J2出队出队队空：Q.front =Q. rear队满： Q.front =(Q.rear + 1) % MAXQSIZE入队: 1)队列不满 2)Q.rear = (Q.rear + 1) % MAXQSIZE出队: 1)队列不空 2)Q.front = (Q.front + 1) % MAXQSIZE求队长求队长:(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE循环队列循环队列#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front;

13、/ 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;循环队列循环队列顺序映象 Status InitQueue (SqQueue &Q) / 构造一个空队列Q Q.base = (QElemType *) malloc (MAXQSIZE *sizeof (QElemType); if (!Q.base) exit (OVERFLOW); / 存储分配失败 Q.front = Q.rear = 0; return OK; Status EnQueue (SqQueue &Q, ElemTy

14、pe e) / 插入元素e为Q的新的队尾元素 if (Q.rear+1) % MAXQSIZE = Q.front) return ERROR; /队列满 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % MAXQSIZE; return OK; Status DeQueue (SqQueue &Q, ElemType &e) / 若队列不空，则删除Q的队头元素， / 用e返回其值，并返回OK; 否则返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q

15、.front+1) % MAXQSIZE; return OK;第 1 行 1 1第 2 行 1 2 1 第 3 行 1 3 3 1第 4 行 1 4 6 4 1二项式系数值（杨辉三角）设第 i-1行的值：(a0=0) a1.ai (ai+1=0)则第 i 行的值：bj = aj-1+aj, j=1,2,i+1利用循环队列计算二项式的过程：假设只计算四行，则队列的最大容量为 5。1 1 00q.frontq.rear1 1 001q.frontq.rear1 1 021q.frontq.rear1 1 021q.frontq.rear1 0 021q.frontq.rear1 0 121q.f

16、rontq.rear1 0 121q.frontq.rear1 0 123q.frontq.rear1 0 133q.frontq.rear1 0 131q.frontq.reardo DeQueue(Q, s); GetHead(Q, e); if (e!=0) printf (“%d”, e); EnQueue(Q, s+e); while (e!=0); 1. 掌握栈和队列类型的特点，并能在相应掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。的应用问题中正确选用它们。2. 熟练掌握栈类型的两种实现方法，特别应熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。注意栈满和栈空的条件以及它们的描述方法。3. 熟练掌握循环队列和链队列的基本操作实熟练掌握循环队列和链队列的基本操作实现算法，