队列
是一种先进先出线性表，FIFO； 表的一段（表尾）插入，表的另一点端（表头）删除 ；同线性表一样仍为一对一关系；有顺序队或链队；只能在队首或队尾操作
Q=(a1队头,a2,...,an队尾)
线性表：
Insert（L,i,x)
1<=i<=n+1
Delete(L,i)
1<=i<=n
队列（先进先出，表尾进表头删）：
Insert（Q,n+1,x）
Delete（Q,1）
队列的抽象数据类型定义
ADT Queue{
数据对象：D=ai|ai属于Elemset，i=1,2,...,n,n>=0}
数据关系：R1=<ai-1,ai>|ai-1,ai属于D,i=2,3,...,n}
约定an为队尾，a1为队头
基本操作：
InitQueue(&Q)
操作结果：构造一个空队列Q
DestroyQueue(&Q)
初始条件：队列Q已存在
操作结果：队列Q被销毁
ClearQueue(&Q)
初始条件：队列Q已存在
操作结果：队列Q被清空
QueueLength(Q)
初始条件：队列Q已存在
操作结果：返回Q的元素个数，即队列的长度
GetHead(Q,&e)
初始条件：队列Q已存在且非空
操作结果：用e返回Q的队头元素
EnQueue(&Q,e)
初始条件：队列Q已存在
操作结果：插入元素e为Q的队尾元素
DeQueue(&Q,&e)
初始条件：队列Q已存在且非空
操作结果：删除Q的队头元素，并用e返回其值
......
}ADT Queue
顺序队列
- rear=MAXQSIZE front=0 再入队 真溢出
- rear=MAXQSIZE front≠0 再入队 假溢出
解决假上溢可使用循环队列 ：base[0]接在base[MAXQSIZE-1]后，若rear+1=M，令rear=0
插入元素：Q.base[Q.rear]=x;Q.rear=(Q.rear+1)%MAXQSIZE;
删除元素：x=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;
队满：front==rear
队空：front==rear
解决方法：
- 另外设一个标志来区别队空、队满
- 另外设一个变量记录元素个数
- 少用一个元素空间（队尾指针再+1与头指针重合）：队满：（rear+1）%MAXQSIZE==front
循环队列的定义
#define MAXQSIZE 100
typedef struct{
int *base; //动态分配存储空间
int front; //头指针
int rear; //尾指针
}SqQueue;
循环队列的初始化
void InitQueue(SqQueue *Q){
Q->base=malloc(sizeof(int)*MAXQSIZE); //分配数组空间
if(!Q->base) printf("Error");
Q->front=Q->rear=0;
}
求循环队列的长度
(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE
int LengthQueue(SqQueue Q){
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
循环队列的入队
队满：(Q->rear+1)%MAXQSIZE==Q->front
Q.base[Q.rear]=x;Q.rear=(Q.rear+1)%MAXQSIZE;
void EnQueue(SqQueue *Q,int e){
if((Q->rear+1)%MAXQSIZE==Q->front) printf("Error"); //如果队满
Q->base[Q->rear]=e;
Q->rear=(Q->rear+1)%MAXQSIZE;
}
循环队列的出队
队空：Q->rear==Q->front
x=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;
void DeQueue(SqQueue *Q,int *e){
if(Q->rear==Q->front) printf("Error");
*e=Q->base[Q->front];
Q->front=(Q->front+1)%MAXQSIZE;
}
链队
若用户无法估计所用队列的长度，则宜使用链队（有头结点）
链队列的定义
#define MAXQSIZE 100
typedef struct Qnode{
int data;
struct Qnode *next;
}QNode,*QueuePtr;
typedef struct {
QueuePtr front;
QueuePtr rear;
}ListQueue;
链队列的初始化
void InitQueue(LinkQueue *Q){
Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q->front) printf("Error");
Q->front->next=NULL;
}
求循环队列的长度
(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE
int LengthQueue(SqQueue Q){
return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
链队列的销毁
从头指针开始
void DestroyQueue1(LinkQueue *Q){
while (Q->front){
QueuePtr p;
p= Q->front->next;
free(Q->front); //从头结点开始销毁
Q->front= (QueuePtr) p;
}
}
void DestroyQueue2(LinkQueue *Q){
while (Q->front){
Q->rear=Q->front->next;
free(Q->front);
Q->front=Q->rear;
}
}
链队列的入队
void EnQueue(LinkQueue *Q,int e){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if (!p) printf("Error");
p->data=e;
p->next=NULL;
Q->rear->next=p;
Q->rear=p;
}
链队列的出队
void DeQueue(LinkQueue *Q,int *e){
QueuePtr p;
if(Q->rear==Q->front) printf("Error");
p=Q->front->next;
*e=p->data;
Q->front->next=p->next;
if(Q->rear==p) Q->rear=Q->front;
free(p);
}
队列的应用
-
舞伴问题：
- 构造出两个空的队列QM,QW
- 依次将队头元素出队配成舞伴
- 某队为空，另一队等待的下一曲继续配对
-
脱机打印输出，按申请先后次序输出
-
多用户系统中，多个用户排成队，分时地循环使用CPU和主存
-
按用户的优先级排成多个队，每个优先级一个队列
-
实时控制系统中，信号按接收的先后顺序依次处理
-
网络电文传输，按到达的时间先后顺序依次进行