队列的设计与实现

什么是队列

栈中元素只能栈顶出入，它是一种特殊的线性表，同样的，队列（Queue）也是一种特殊的线性表。
秉承先来后到的原则，队列中的元素只能从队尾进入，只能从队首出去，也就是说，入队顺序为1、2、3、4，那么出队顺序也一定是1、2、3、4，所以队列是一种先进先出（FIFO，First In, First Out）的数据结构。

顺序表队列

想要实现队列也是很简单的，也可以通过两种线性表来实现，我们先来看看使用顺序表如何实现队列，假设一开始的时候队列中有0个元素，队首和队尾一般都初始都是-1这个位置：

此时有新的元素入队了，队尾向后移动一格（+1），然后在所指向位置插入新的元素：

之后都是同样的方式进行插入，队尾会一直向后移动：

现在我们想要执行出队操作了，那么需要将队首向后移动一格，然后删除队首指向的元素：

这样设计看起来很不错，但是队列是一次性的，最终会被用完，延长数组终究不是办法，所以我们队列上一般会使用循环队列

开始编写代码：

typedef int E;

struct Queue {
    E * array;
    int capacity;   //数组容量
    int rear, front;   //队尾、队首指针
};

typedef struct Queue * ArrayQueue;

初始化代码：

_Bool initQueue(ArrayQueue queue){
    queue->array = malloc(sizeof(E) * 10);
    if(queue->array == NULL) return 0;
    queue->capacity = 10;
    queue->front = queue->rear = 0;   //默认情况下队首和队尾都指向0的位置
    return 1;
}

int main(){
    struct Queue queue;
    initQueue(&queue);   
}

入队操作

_Bool offerQueue(ArrayQueue queue, E element){
    if((queue->rear + 1) % queue->capacity == queue->front)   //先判断队列是否已满，如果队尾下一个就是队首，那么说明已满
        return 0;
    queue->rear = (queue->rear + 1) % queue->capacity;   //队尾先向前移动一位，注意取余计算才能实现循环
    queue->array[queue->rear] = element;   //在新的位置插入元素
    return 1;
}

出队操作

_Bool isEmpty(ArrayQueue queue){   //在出队之前需要先看看容量是否足够
    return queue->rear == queue->front;
}

E pollQueue(ArrayQueue queue){
    queue->front = (queue->front + 1) % queue->capacity;   //先将队首指针后移
    return queue->array[queue->front];   //出队，完事
}

这里我们要记住，我们给的循环队列的大小看似是10，但我们写的这个代码会导致队头也就是front指着的空间始终是空的，他只是出队front+1的元素，与上方参考图有所不同

单链队列

同样的，队列也可以使用链表来实现，并且使用链表的话就不需要关心容量之类的问题了，会更加灵活一些：

当有新的元素入队时，只需要拼在队尾就行了，同时队尾指针也要后移一位：

出队时，只需要移除队首指向的下一个元素即可：

那么我们来编写代码：

typedef int E;

struct LNode {
    E element;
    struct LNode * next;
};

typedef struct LNode * Node;

struct Queue{
    Node front, rear;
};

typedef struct Queue * LinkedQueue;   //因为要存储首位两个指针，所以这里封装一个新的结构体吧

接着是初始化，初始化的时候，需要把头结点先创建出来：

_Bool initQueue(LinkedQueue queue){
    Node node = malloc(sizeof(struct LNode));
    if(node == NULL) return 0;
  	node->next = NULL;
    queue->front = queue->rear = node;   //一开始两个指针都是指向头结点的，表示队列为空
    return 1;
}

int main(){
    struct Queue queue;
    initQueue(&queue);
}

入队操作

首先是入队操作，入队其实直接在后面插入新的结点就行了：

_Bool offerQueue(LinkedQueue queue, E element){
    Node node = malloc(sizeof(struct LNode));
    if(node == NULL) return 0;
  	node->next = NULL;
    node->element = element;
    queue->rear->next = node;   //先让尾结点的下一个指向新的结点
    queue->rear = node;   //然后让队尾指针指向新的尾结点
    return 1;
}

出队操作

接着是出队操作，出队操作要相对麻烦一点：

E pollQueue(LinkedQueue queue){
    E e = queue->front->next->element;
    Node node = queue->front->next;
    queue->front->next = queue->front->next->next;  //直接让头结点指向下下个结点
    if(queue->rear == node) queue->rear = queue->front;   //如果队尾就是待出队的结点，那么队尾回到队首位置上
    free(node);   //释放内存
    return e;
}

效果和前面的顺序表实现是一样的，只不过使用链表会更加灵活一些。