1.队列(Queue):具有一定操作约束的线性表
插入和删除操作:只能在一端插入，而在另一端删除
数据插入:入队列(AddQ)
数据删除:出队列(DeleteQ)
先来先服务
先进先出:FIFO
2.抽象数据描述
类型名称:队列(Queue) 数据对象集:一个有0个或多个元素的有穷线性表。
操作集:长度为MaxSize的队列Q Queue，队列元素item ElementType
1、Queue CreatQueue( int MaxSize ):生成长度为MaxSize的空队列;
2、int IsFullQ( Queue Q, int MaxSize ):判断队列Q是否已满;
3、void AddQ( Queue Q, ElementType item ): 将数据元素item插入队列Q中;
4、int IsEmptyQ( Queue Q ): 判断队列Q是否为空;
5、ElementType DeleteQ( Queue Q ):将队头数据元素从队列中删除并返回。
- 队列的顺序存储实现
队列的顺序存储结构通常由一个一维数组和一个记录队列头元 素位置的变量front以及一个记录队列尾元素位置的变量rear组成。
#define MaxSize <储存数据元素的最大个数>
typedef struct {
ElementType Data[ MaxSize ];
int rear;
int front;
} Queue;
入队
void AddQ( Queue *PtrQ, ElementType item) {
if ( (PtrQ->rear+1) % MaxSize == PtrQ->front ) {
printf(“队列满”);
return;
}
PtrQ->rear = (PtrQ->rear+1)% MaxSize;
PtrQ->Data[PtrQ->rear] = item;
}
出队
ElementType DeleteQ ( Queue *PtrQ ) {
if ( PtrQ->front == PtrQ->rear ) {
printf(“队列空”);
return ERROR;
} else {
PtrQ->front = (PtrQ->front+1)% MaxSize;
return PtrQ->Data[PtrQ->front];
} }
front 和 rear 的指针移动使用加一取余法。体现了顺序存储的循环使用。
