队列

队列

队列是一种可以实现先进先出(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");
}