队列

发表于 分类于 阅读次数： 本文字数： 4.7k

前面我们学习了栈，栈中元素只能栈顶出入，它是一种特殊的线性表，同样的，队列（Queue）也是一种特殊的线性表。

就像我们在超市、食堂需要排队一样，我们总是排成一列，先到的人就排在前面，后来的人就排在后面，越前面的人越先完成任务，这就是队列，队列有队头和队尾：
image
秉承先来后到的原则，队列中的元素只能从队尾进入，只能从队首出去，也就是说，入队顺序为1、2、3、4，那么出队顺序也一定是1、2、3、4，所以队列是一种先进先出（FIFO，First In, First Out）的数据结构。

想要实现队列也是很简单的，也可以通过两种线性表来实现，我们先来看看使用顺序表如何实现队列，假设一开始的时候队列中有0个元素，队首和队尾一般都初始都是-1这个位置：
image
此时有新的元素入队了，队尾向后移动一格（+1），然后在所指向位置插入新的元素：
image
之后都是同样的方式进行插入，队尾会一直向后移动：
image
现在我们想要执行出队操作了，那么需要将队首向后移动一格，然后删除队首指向的元素：
image
看起来设计的还挺不错的，不过这样有一个问题，这个队列是一次性的，如果队列经过反复出队入队操作，那么最后指针会直接指向数组的最后，如果我们延长数组的话，也不是一个办法，不可能无限制的延伸下去吧？所以一般我们采用循环队列的形式，来实现重复使用一个数组（不过就没办法扩容了，大小是固定的）
image
我们可以在移动队首队尾指针时，考虑循环的问题，也就是说如果到达了数组尽头，那么就直接从数组的前面重新开始计算，这样就相当于逻辑上都循环了，队首和队尾指针在一开始的时候都指向同一个位置，每入队一个新的元素，依然是先让队尾后移一位，在所指向位置插入元素，出队同理。

不过这样还是有问题，既然是循环的，那么怎么判断队列是否已满呢？
image
由于队首指针和队尾指针重合时表示队列为空，所以我们只能舍弃一个存储单元，当队尾距离队首一个单元的时候，表示队列已满。

开始编写代码：

1
2
3
4
5
6
7
8
9
typedef int E;

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

typedef struct Queue * ArrayQueue;//起别名

接着进行初始化

1
2
3
4
5
6
7
8
9
10
11
12
_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);//初始化
}

接着来编写一下入队操作：

1
2
3
4
5
6
7
8
//入队
_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;
}

测试一下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void printQueue(ArrayQueue queue){
    printf("<<< ");
    int i = queue->front;   //遍历队列需要从队首开始
    do {
        i = (i + 1) % queue->capacity;   //先向后循环移动
        printf("%d ", queue->array[i]);  //然后打印当前位置上的元素
    } while (i != queue->rear);   //当到达队尾时，结束
    printf("<<<\n");
}

int main(){
    struct Queue queue;
    initQueue(&queue);
    for (int i = 0; i < 5; ++i) {
        offerQueue(&queue, i * 100);
    }
    printQueue(&queue);
}

image
我们接着来是出队操作：

1
2
3
4
5
6
7
8
_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];   //出队，完事
}

测试：

1
2
3
4
5
6
7
8
9
10
11
int main(){
    struct Queue queue;
    initQueue(&queue);
    for (int i = 0; i < 5; ++i) {
        offerQueue(&queue, i * 100);
    }
    printQueue(&queue);
    while (!isEmpty(&queue)) {
        printf("%d ", pollQueue(&queue));
    }
}

结果：
image
可以看到，队列是先进先出的，我们是以什么顺序放入队列中，那么出来的就是是什么顺序。

同样的，队列也可以使用链表来实现，并且使用链表的话就不需要关心容量之类的问题了，会更加灵活一些：
image
注意我们需要同时保存队首和队尾两个指针，因为是单链表，所以队首需要存放指向头结点的指针，因为需要的是前驱结点，而队尾则直接是指向尾结点的指针即可，后面只需要直接在后面拼接就行。

当有新的元素入队时，只需要拼在队尾就行了，同时队尾指针也要后移一位：
image
出队时，只需要移除队首指向的下一个元素即可：
image
接下来就按照这个思路，来编写代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef int E;

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

typedef struct LNode * Node;

struct Queue{//因为要存储首位两个指针，所以这里封装一个新的结构体
    Node front, rear;
};

typedef struct Queue * LinkedQueue;   //别名

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

1
2
3
4
5
6
7
8
9
10
_Bool initQueue(LinkedQueue queue){
    Node node = malloc(sizeof(struct LNode));//创建节点
    if(node == NULL) return 0; //一开始两个指针都是指向头结点的，表示队列为空
    queue->front = queue->rear = node;  //尾结点等于头结点
    return 1;
}
int main(){
    struct Queue queue;//创建队列
    initQueue(&queue);//初始化
}

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

1
2
3
4
5
6
7
8
9
//入栈
_Bool offerQueue(LinkedQueue queue, E element){//添加元素
    Node node = malloc(sizeof(struct LNode));//创建节点
    if(node == NULL) return 0;
    node->element = element;
    queue->rear->next = node;   //先让尾结点的下一个指向新的结点
    queue->rear = node;   //然后让队尾指针指向新的尾结点
    return 1;
}

测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void printQueue(LinkedQueue queue){
    printf("<<< ");
    Node node = queue->front->next;
    while (1) {    //注意不能直接判空，因为前面我们没考虑，也就没将新结点next设定为NULL
        printf("%d ", node->element);
        if(node == queue->rear) break;    //当已经打印最后一个元素后，再结束
        else node = node->next;
    }
    printf("<<<\n");
}

int main(){
    struct Queue queue;
    initQueue(&queue);
    for (int i = 0; i < 5; ++i) {
        offerQueue(&queue, i*100);
    }
    printQueue(&queue);
}

测试结果:
image
接着是出队操作，出队操作要相对麻烦一点：

1
2
3
4
5
6
7
8
9
10
11
12
13
//出队
_Bool isEmpty(LinkedQueue queue){
    return queue->rear == queue->front;
}

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

打印出队顺序：

1
2
3
4
5
6
7
8
9
10
11
int main(){
    struct Queue queue;
    initQueue(&queue);
    for (int i = 0; i < 5; ++i) {
        offerQueue(&queue, i*100);
    }
    printQueue(&queue);
    while (!isEmpty(&queue)){
        printf("%d ", pollQueue(&queue));
    }
}

测试结果：
image