（二）线性结构——（2）队列

（二）线性结构——（2）队列

队列：具有一定 *** 作约束的线性表

（1）插入和删除 *** 作：只能在一端插入，一端删除

数据插入：入队列（AddQ)

数据删除：出队列（DeleteQ)

先来先服务：先进先出表FIFO

（2）顺序存储：一个一维数组和一个记录队列头元素位置的变量front和一个记录队列尾元素位置的变量rear组成

#define MaxSize 10
struct QNode{
  int a[MaxSize];
  int rear;
  int front;
 };

但是顺环队列的时候，比如有a个元素，但是有a+1种情况（0个元素，1个元素...a个元素）。导致无法充分判定空和满。

解决方法：（1）使用额外标记：Size或者tag域

                  （2）有n个数组空间，但是只使用（n-1)个数组空间 

所以入队列：

void Add(Queue PtrQ,int item)
{
 if((PtrQ->rear+1)%MaxSize==ptrl->front)
{ 
  printf("队列满");
  return;
}

PtrQ->rear=(PtrQ->rear+1)%MaxSize;
PtrQ->Data[PtrQ->rear]=item;
}

出队列：

int deleteQ(queue PtrQ)
{
 if(PtrQ->front==ptrQ->rear)
 {
 printf("队列空”）;
 return error;
 }
 else{
 PtrQ->front=(PtrQ->front+1)%MaxSize;
 return PtrQ->a[PtrQ->front);
}
}

(3)链表的链式存储：单链表

struct Node{
 ElementType Data;
 struct Node*Next;
}//链表中的每个节点

struct QNode{//链队列结构
  struct Node*rear;
  struct Node*front;
 };

typedef struct QNode*Queue;
Queue PtrQ;//为包含rear和front的结构体的指针

不带头结点的链式队列出队的 *** 作 ：

int DeleteQ(Queue PtrQ)
{
 struct Node*FrontCell;
 ElementType FrontELem;

 if(PtrQ->front==NULL)
 {
 printf("队列空");
 return ERROR;
 }

 FrontCell=PtrQ->front;
 if(PtrQ->front==PtrQ->rear)//若队列中只有一个元素
  PtrQ->front=PtrQ->rear=NULL;//删除后队列置为空
 else
  PtrQ->front=PtrQ->front->Next;
 FrontElem=FrontCell->Data;
free(FrontCell);//释放被删除节点的空间
return FrontElem;
}