队列

一.队列的特点是先进先出。

二.关于队列的简单实现。

     顺序队列的基本实现和顺序栈的实现基本相似。顺序队列在出列和入列的时候会使队列整体向上移动，会浪费一定的空间。因此出现了一种队列叫做循环队列。

     

     循环队列可以实现空间的重复利用，大大节省了空间。

 关于循环队列的实现

  建立一个空队列
struct Node
{
int data[10];
int front;
int rear;
};
struct Node InitQueue(struct Node *Q)
{
Q->front=0;
Q->rear=0;
return 0;

}

求队列的长度
 
int QueueLengh(struct Node *Q)
{
return (Q.rear-Q.front+10)%10;

}

入队：
struct Node EnQueue(struct Node *Q,int e)
{
if((Q->rear+1)%10==Q->front)
{
return 0;
}
Q->data[Q->rear]=e;
         Q->rear=(Q->rear+1)%MAXSIZE;

return 1;

}

出队：
struct Node DeQueue(struct Node *Q,int  *e)
{
         if(Q->front==Q->rear)
{
return -1;
}
*e=Q->data[Q->front];
Q->front=(Q->front+1)%MAXSIZE;
return 0;

}

三.队列的链式结构

创建一个空队列

void initQueue(LinkQueue *q)//q为结构体指针，初始化  
{  
     q->front=q->rear=(QueuePtr)malloc(sizeof(QNode));//用malloc动态生成头结点，然后队头队尾指针指向这个头结点  
     if(!q->front)  
        exit(0);  
     q->front->next=NULL;//空队列  

}  

入队

void InserQueue(LinkQueue *q,ElemType e)  

{  
     QueuePtr p;  
     p=(QueuePtr)malloc(sizeof(QNode)); //申请一个p结点  
     if(p==NULL)  
       exit(0);  
     p-data=e; //p的数据域为要插入的值e  
     p->next=NULL; //p的指针域next的下一个为NULL  
     q->rear->next=p; //本来q->rear->next为NULL，现在将p赋值给它，先连接起来  
     q->rear=p; //最后直接将p结点赋值给q，p就不要了，可以扔了  

}  

出队

void DeleteQueue(LinkQueue *q,ElemType *e)  
{  
     QueuePtr p;  
     if(q->front==q->rear)//空队列  
         return;  
     p=q->front->next;//将欲删除的队头结点暂存给p  
     *e=p->data;//将欲删除的队头结点的值赋值给e      
     q->front->next=p->next;//将原队头接待的后继p->next赋值给头结点后继  
     if(q->rear==p)//意思为队列中只有一个元素，即处理队尾指针，q->rear指向头结点         q->rear=q->front;       free(p);  }