数据结构--队列
队列是只允许在表的一端进行插入（队尾），在另一端进行删除（对头）的运算受限的线性表。
允许删除的一端称为对头（front），允许插入的一端称为队尾（rear）。
队列称为先进先出（First in first out）的线性表。
基本运算
InitQueue（Q）
构造一个空队列Qv
QueueEmpty（Q）
判断队空，若队列Q空，则返回true，否则返回false
QueueFull（Q）
判断队满，若队列为满，则返回true，否则返回false，此操作只适应线性表的队列。
EnQueue（Q,x）
入队，若队列Q非满，则将元素x插入Q的队尾。
DeQueue（Q）
出队，若队列Q非空，则删除Q的对头元素，并返回该元素。
QueueFront（Q）
若队列Q非空，则返回队头元素，注意不改变队列Q的状态。
队列必须使用一个变量保存队列的元素个数。
由于队列的对头和队尾的位置是变化的，因此我们设置两个指针front和rear分别指示对头元素和队尾元素在队列中的位置，他们的初值为0。
入队时将新元素插入到rear所指向的位置，然后将rear加1
出队的时候，返回front所指的元素，然后将front加1
在非空的队列中，头指针始终指向对头元素，而尾指针始终指向最后一个元素+1的位置。
循环队列的取模运算
i=(i+1)%QUEUESIZE;
顺序队
#define QUEUESIZE 100
typedef char DataType;
typedef struct
{
int nFront; //头指针
int nRear; //尾指针
int nCount; //计数器
DataType data[QUEUESIZE];
}CirQueue;
初始化
void InitCQ(CirQueue *c)
{
c->nCount=0;
c->nFront=0;
c->nRear=0;
}
判断队空
int QueueEmply(CirQueue *q)
{
return q->nCount==0;
}
判断队满
bool QueueFull(CirQueue *q)
{
return q->nCount==QUEUESIZE;
}
入队
bool EnQueue(CirQueue *p,DataType _data)
{
if(QueueFull(p))
return false;
p->nCount++;
p->data[p->nRear]=_data;
p->nRear=(p->nRear+1)%QUEUESIZE;
return true;
}
出队
bool DeQueue(CirQueue *p,DataType *data)
{
if(QueueEmpty(p))
return false;
*data=p->data[p->nFront];
p->nFront=(p->nFront+1)%QUEUESIZE;
p->nCount--;
return true;
}
取队头元素
DataType QueueFront(CirQueue *p)
{
if(QueueEmpty(p))
return -1;
return p->data[p->nFront];
}
链队
typedef char DataType;
typedef struct Node
{
Datatype data;
struct Node *next;
}QueueNode;
typedef struct queue
{
QueueNode *front;
QueueNode *rear;
}LinkQueue;
初始化
void InitQueue(LinkQueue *Q)
{
Q->front=Q->rear=NULL;
}
判断队空
int QueueEmpty(LinkQueue *Q)
{
return Q->front==NULL;
}
入队
void EnQueue(LinkQueue *Q,DataType x)
{
QueueNode *p=(QueueNode *)malloc (sizeof(QueueNode));
p->data=x;
p->next=NULL;
if(QueueEmpty(Q))
Q->front=Q->rear=p;
else
{
Q->rear->next=p;
Q->rear=p;
}
}
出队
DataType DeQueue(LinkQueue *Q)
{
DataType x;
QueueNode *p;
if(QueueEmpty(Q))
return -1;
p=Q->front;
x=p->data;
Q->front=p->next;
if(Q->rear==p)
Q->rear=NULL;
free(p);
return x;
}
取队头元素
DataType QueueFront(LinkQueue *Q)
{
if(QueueEmpty(Q))
return -1;
return Q->front->data;
}
补充：综合编程 , 其他综合 ,
