队列

¶ 队列

队列是一种可以实现先进先出 (first in first out,FIFO) 的存储结构。与栈不一样的是，队列规定只在一端进行插入操作，在另一端进行删除操作。允许插入的一端叫做队尾 (rear)，允许删除的一端叫做队首 (front)。

¶ 分类

• 链式队列：用链表实现。

• 静态队列：用数组实现。(为了解决假溢出现象，静态队列通常都必须是循环队列)

¶ 循环队列

¶ 参数：front、rear

• rear 所指的单元始终为空

• 队列初始化：front 和 rear 的值都是 0。

• 队列非空：front 指向队列的第一个元素；rear 指向队列的最后一个有效元素的下一个元素。

• 队列空：front 和 rear 值相等，但不一定是 0。

¶ 算法解析

1. 入队：将值存入 rear 所代表的位置r

• 错误写法：r=r+1

• 正确写法：r=(r+1)%数组长度

2. 出队：
f=(f+1)%数组长度

3. 判断循环队列是否为空

rear = front

4. 判断循环队列是否已满

• 多增加一个参数标志满或者空（一般不用此方式）

• 少用一个元素：如果(r+1)%数组长度==f表示循环队列已满

¶ 代码实现

1. 队列数据建构

typedef struct queue {
   int *p;
   int front;
   int rear;
   int maxsize;
}Queue;

2. 初始化队列

void CreateQueue(Queue *Q,int maxsize){
   Q->p = (int*)malloc(sizeof(int)*maxsize);
   if(!Q->p){
    printf("Memory allocation failure!");
       exit(-1);
 }
   Q->front = Q->rear;
   Q->maxize = maxsize;
}

3. 判断循环队列是否为满

int isFull(Queue *Q){
   if ((Q->rear+1)%Q->maxsize == Q->front)
       return 1;
   else
       return 0;
}

4. 判断循环队列是否为空

int isEmpty(Queue *Q){
   if(Q->rear == Q->front)
       return 1;
  else
       return 0;
}

5. 入队操作

void Enter(Queue *Q,int val){
   if (isFull(Q)){
    printf("The queue is full!");
    return;
 }
   else{
    Q->p[Q->rear] = val;
       Q->rear = (Q->rear+1)%Q->maxsize;
 }
}

6. 出队操作

void Delete(Queue *Q,int *val){
   if(isEmpty(Q))
  return 0;
   else{
    *val = Q->p[Q->front];
       Q->front=(Q->front+1)%Q->maxszie;
       printf("Get out of the queue successfully!");
 }
}

7. 遍历操作

void Traverse(Queue *Q){
   int i = Q->front;
   printf("The items in queue are:\n");
   while(i%Q->maxsize!=Q->rear){
    printf("%d",Q->p[i]);
       i=(i+1)%Q->maxsize;
 }
   printf("\n");
}

¶ 链式队列

链式队列实现和链式栈相差不多，只是将删除操作放在了另外一端，有效的解决了顺序队列存储空间不足的缺陷。

¶ 代码实现

1. 队列节点构建

typedef struct Node{
   int data;  //数据域
   struct Node *next;  //指针域
}Node;

typedef struct{
   Node *front;
   Node *rear;
}Queue;

2. 队列初始化

int InitQueue(Queue *Q){
   Node *head = (Node*)malloc(sizeof(Node));
   if(!head){
    printf("Memory allocation failed!\n");
       return ;
 }
   head->next = NULL;
   Q->rear = Q->front = head;  //front和rear都指向头指针
   printf("Init successfully!\n");
   return 0;
}

3. 入队操作

int Enter(Queue *Q,int item){
   Node *s = (Node*)malloc(sizeof(Node));
   if(!s){
    printf("Memory allocation failed!\n");
       return ;
 }
   s->next = NULL;
   s->data = item;
   Q->rear->next = s;
   Q->rear = s;
   return 0;
}

4. 出队操作

void Delete(Queue *Q,int *item){
   if(Q->front == Q->rear){
    printf("The queue is empty!\n");
       return;
 }
   Node *p;
   p = Q->front->next;  //先将要出栈的节点存在P中
   Q->front->next = p->next;  //重新构造队头元素的后继
   *item = p->data;   //保存出队的数据；
   if(Q->rear == p)  //判断删除的节点是否为队尾元素
       Q->rear = Q->front;
   free(p);
}

5. 遍历元素

void Traverse(Queue *Q){
   if(Q->front == Q->rear){
    printf("The queue is empty!\n");
 }
   Node *p = Q->front->next;
   while(p){
    printf("%d",p->data);
       p = p->next;
 }
   printf("\n");
}