1、也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为，允许插入的一端称为。v队列的修改是依先进先出的原则进行的。队列的基本运算队列的基本运算1初始化队列初始化队列 InitQueue(&Q)将队列Q设置成一个空队列。2入队列入队列 EnQueue(&Q,X)将元素X插入到队尾中，也称“进队”，“插入”。3出队列出队列 DeQueue(&Q,&e)将队列Q的队头元素删除，并用e返回其值，也称“退队”、“删除”。4取队头元素取队头元素 GetHead(Q,&e)得到队列Q的队头元素之值，并用e返回其值。5判队空判队空 QueueEmpty(Q)判断队列Q是否
2、为空，若为空返回1，否则返回0。#define MAXSIZE 100typedef struct ElemType dataMAXSIZE;int front;int rear;SqQueue;顺序队列的操作演示顺序队列的操作演示flash在非空队列里，头指针始终指向队头元素，而尾指针在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。始终指向队尾元素的下一位置。v 为充分利用向量空间，克服上述假上为充分利用向量空间，克服上述假上溢现象，可以将向量空间想象为一个首溢现象，可以将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向尾相接的圆环，并称这种向量为循环向量，存
3、储在其中的队列称为量，存储在其中的队列称为循环队列循环队列（Circular Queue)。v循环队列中进行出队、入队操作时，头循环队列中进行出队、入队操作时，头尾指针仍要加尾指针仍要加1，朝前移动。只不过当，朝前移动。只不过当头尾指针指向向量上界（头尾指针指向向量上界（QueueSize-1）时，其加时，其加1操作的结果是指向向量的下操作的结果是指向向量的下界界0。循环队列的操作演示循环队列的操作演示flash012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4J5J6012345rearfront初始状态J4,J5,J6出队J7,J8,J9入队队空：fr
4、ont=rear队满：front=rear队空、队满无法判断：1.另外设一个标志以区别2.少用一个元素空间：队空：front=rear 队满：(rear+1)%M=front队空：Q.front=Q.rear队满：Q.front=(Q.rear+1)%maxSize入队:Q.rear=(Q.rear+1)%maxSize出队:Q.front=(front+1)%maxSize;求队长:(Q.rear-Q.front+maxSize)%maxSize循环队列循环队列1）进队列算法）进队列算法（1）检查队列是否已满，若队满，则溢出错误；（2）将新元素赋给队尾指针所指单元；（3）将队尾指针后移一个位
5、置（即加1）。2)出队列算法出队列算法（1）检查队列是否为空，若队空，则下溢错误；（2）取队首元素的值。（3）将队首指针后移一个位置（即加1）；循环队列的基本运算实现循环队列的基本运算实现ch3_ull*qq.frontq.rear非空队列q.frontq.rearnull空队列*qv链队列示意图 和顺序队列类似，我们也是将这两个指针封装在一起，将链队列的类型LinkQueue定义为一个结构类型：typedef struct queuenode ElemType data;struct queuenode*next;QueueNode;typedef struct QueueNode *fro
6、nt;QueueNode *rear;LinkQueue;链队列的ch3_lqueue.cCPU资源的竞争问题。主机与外部设备之间速度不匹配的问题。服务、排队问题线性表、栈与队的异同点线性表、栈与队的异同点相同点：相同点：逻辑结构相同，都是线性的；都可以用顺逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性序存储或链表存储；栈和队列是两种特殊的线性表，即表，即受限的线性表受限的线性表（只是对插入、删除运算加（只是对插入、删除运算加以限制）。以限制）。不同点：不同点：运算规则不同，线性表为随机存取，而栈是只运算规则不同，线性表为随机存取，而栈是只允许在一端进行插入和删除运算，因而是后进先允许在一端进行插入和删除运算，因而是后进先出表出表LIFOLIFO；队列是只允许在一端进行插入、另一；队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表端进行删除运算，因而是先进先出表FIFOFIFO。用途不同，线性表比较通用；堆栈用于函数调用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、用、递归和简化设计等；队列用于离散事件模拟、多道作业处理和简化设计等。多道作业处理和简化设计等。
