队列 | 文的盲

队列是具有一定操作约束的线性表，只能在一端（队尾）进行插入，另一端（队头）进行删除。

简单地理解，按照字面意思，队列这种数据结构，就如同生活中排队的队列一般，后来的人（数据）只能跟在队尾，而队首的人（数据）首先接受服务（进行删除）。

数据插入：入队列（addQueue）
数据删除：出队列（deleteQueue）

而队列主要的特性如下：

先来先服务
先进先出：FIFO

类型名称：队列（Queue）

数据对象集：一个有0个或多个元素的有穷线性表

操作集：长度为 MaxSize 的队列 Q 属于 Queue，队列元素 item 属于 ElementType

1. Queue CreatQueue()						生成空队列
2. int IsFullQ(Queue PtrQ)		判断队列Q是否已满
3. void AddQ(Queue PtrQ, ElementType item)	将数据元素item插入队列Q中
4. int IsEmptyQ(Queue PtrQ)					判断队列是否为空
5. ElementType DeleteQ(Queue PtrQ)			将对头数据元素从队列中删除并返回

队列的顺序储存实现

利用数组来实现相关操作

直接利用数组实现

数组的一端作为头，另一端作为尾，这样的方式是比较容易实现的：
- 首先在空数组上的将队列头和尾均放在数组头的前一个位置，头和尾的标号为-1
添加元素之后，则将队尾保存的标号加一；同理删除元素之后，将队头的元素加一

存在的问题：

如果队放满，也就是队尾下标为 MaxSize-1 但此时队头由于删除元素的原因，还空有位置，因此会造成空间浪费。
利用环形数组实现

环形数组并不是物理意义上的环形，而是指队列如果放满之后（队尾下标为 MaxSize-1 ），数组头部如果还有空位，就将新加进来的元素，从数组头继续存放。这时，如何判断队列是否已满呢？

判断队列空和满
- 空：队头下标等于队尾下标
满：队尾下标加一等于对头下标，但如果此时队尾下标而队头为0则无法用此法判断

改进：最大队尾下标加一除以 MaxSize 的余数等于队尾下标（除数大于被除数，余数为被除数本身）

正因为上述所说，平常所说的 顺序存储 实现均是以 指环形数组 的方式实现。

首先写出 Queue.h ，C语言代码如下：

C语言代码：

//
// Created by wenmang on 2019/8/2.
//

#ifndef DATA_STRUCTURE_QUEUE_H
#define DATA_STRUCTURE_QUEUE_H

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define BASE_SIZE 8

typedef int elementType;
typedef struct QNode *queue;
struct QNode{
    elementType* data;	// 队列数据存储位置
    int size;	// data 数组大小
    int rear;	// 队尾
    int front;	// 队首
};

queue createQueue();
bool isFull(queue q);
bool isEmpty(queue q);
void addQueue(queue q, elementType e);
elementType deleteQueue(queue q);

#endif //DATA_STRUCTURE_QUEUE_H

紧接着，我们在 Queue.c 文件中实现头文件中所申明的函数：

C语言代码：

//
// Created by wenmang on 2019/8/2.
//

#include <assert.h>
#include "Queue.h"

queue createQueue() {
    queue q = (queue) malloc(sizeof(struct QNode));
    q->size = 8;
    q->data = (elementType*) malloc(q->size * sizeof(elementType));
    q->front = q->rear = 0;
    return q;
}

bool isFull(queue q) {
    return (q->rear+1) % q->size == q->front;
}

bool isEmpty(queue q) {
    return q->rear == q->front;
}

void addQueue(queue q, elementType e) {
    if (isFull(q)) {
        q->size *= 2;
        q->data = (elementType*) realloc(q->data, q->size * sizeof(elementType));
    }
    q->rear = (q->rear+1) % q->size;
    q->data[q->rear] = e;
}

elementType deleteQueue(queue q) {
    assert(!isEmpty(q));
    q->front = (q->front+1) % q->size;
    return q->data[q->front];
}

队列的链式储存实现

也就是使用链表存储

首先可以写出头文件 Queue.h 的内容：

//
// Created by wenmang on 2019/8/2.
//

#ifndef DATA_STRUCTURE_QUEUE_H
#define DATA_STRUCTURE_QUEUE_H


#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct LQNode* lQueue;
struct Node{
    elementType data;
    struct Node* next;
};
struct LQNode{
    struct Node* rear;
    struct Node* front;
};

lQueue createlQueue();
void addlQueue(lQueue q, elementType e);
elementType deletelQueue(lQueue q);
bool islEmpty(lQueue q);

#endif //DATA_STRUCTURE_QUEUE_H

用链表储存，设计了两个结构，

Node 为队列中节点，指针指向下一个节点，data 储存节点数据

QNode 为队列头节点，两个指针分别指向队列头和队列尾

然后，在 Queue.c 文件中实现声明的函数：

lQueue createlQueue() {
    lQueue q = (lQueue) malloc(sizeof(struct LQNode));
    q->front = q->rear = NULL;
    return q;
}

void addlQueue(lQueue q, elementType e) {
    struct Node* tmp = (struct Node*) malloc(sizeof(struct Node));
    tmp->data = e;
    if (q->front == NULL)
        q->front = q->rear = tmp;
    else
        q->rear = q->rear->next = tmp;
    q->rear->next = NULL;
}

elementType deletelQueue(lQueue q) {
    assert(!islEmpty(q));
    struct Node* tmp = q->front;
    q->front = q->front->next;
    return tmp->data;
}

bool islEmpty(lQueue q) {
    return q->front == NULL;
}

优点：链表储存无需判断是否队列已满

队列的顺序储存实现

直接利用数组实现

利用环形数组实现

队列的链式储存实现