队列
队列的类型定义
基本概念
只允许在一端插入数据操作，在另一端进行删除数据操作的特殊线性表；进行插入操作的一端称为队尾（入队列），进行删除操作的一端称为队头（出队列）；队列具有先进先出（FIFO）的特性。
ADT Queue{
数据对象： D={ai|a1∈ElemSet,i=1,2,...,n,n>=0}
数据关系：R={<ai,ai-1>|ai∈D,i=1,2,...,n,n>=0}
约定其中ai为队列头，an为队列尾
基本操作：
InitQueue(&Q)
造作结果：构造一个空队列
DestroyQueue(&Q)
初始条件：队列Q已存在
操作结果：队列Q被销毁，不再存在
ClearQueue(&Q)
初始条件：队列Q已存在
操作结果：将Q清空为空队列
QueueEmpty(Q)
初始条件：队列Q已存在
操作结果：若Q为空队列，返回true，否则，返回false
QueueLength(Q)
初始条件：队列Q已存在
操作结果：返回Q的元素个数，即队列的长度
GetHead(&Q)
初始条件：队列Q已存在
操作结果：返回Q的头元素
EnQueue(&Q，e)
初始条件：队列Q已存在
操作结果：插入e为Q的新的队尾元素
DeQueue(&Q,&e)
初始条件：Q为非空队列
操作结果：删除Q的对头元素，并用e返回其值
QueueTraverse(Q)
初始条件：Q为非空队列
操作结果：从对头到对尾，依次对Q的每个数据元素访问
}ADT Queue
循环队列
为了改变假溢出所以使用循环队列
顺序表示
队列顺序存储结构
#define MAXSIZE 100
typedef struct
{
QElemType *base;//存储空间的基地址
int front;//头指针
int rear;//尾指针
}SqQueue;
初始化
Status InitQueue(SqQueue&Q)
{
Q.base = new QELemType[MAXSIZE];
if(!Q.base) return ERROR;
Q.front = Q.rear = 0;
return OK;
}
销毁队列
Status DestoryQueue(SqQueue&Q)
{
if(Q.base)
delete []Q.base;
return OK;
}
清空队列
Status ClearQueue(SqQueue&Q)
{
delete[] Q.base;
front = rear = 0;
elements = new T[maxSize];
}
判空
Status EmptyQueue(SqQueue&Q)
{
return (front == rear) ? true : false;
}
取队长
int QueueLength(SqQueue Q)
{
return(Q.rear-Q.fornt+MAXSIZE)&MAXSIZE;
}
取对头元素
Status GetHead(SqQueue&Q)
{
if(Q.front!=Q.rea)
return Q.base[Q.front];
}
入队
Status EnQueue(SqQueue &Q,QElemType e)
{
if((Q.rear+1)%MAXSIZE == Q.front)
return ERROR;
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;//队尾指针加1
return OK;
}
出队
Status DeQueue(SqQueue &Q,QElemtype &e)
{
if(Q.fornt==Q.rear)
return ERROR;
e=Q.base[Q.front];
Q.fornt=(Q.front+1)%MAXSIZE;//队头指针加1
return OK
}
遍历队列
Status QueueTraverse(SqQueue &Q)
{
int i;
i=Q.front;
while(i!=Q.rear)
{
printf("%d ",Q.data[i]);
i=(i+1)%MAXSIZE;
}
printf("\n");
return OK;
}