↓跳到主要内容

顺序队列和链式队列

·10634 字·22 分钟
DS
目录

顺序队列

顺序队列的假溢出

基于对栈的理解，队列也是一种操作受限的线性表，既然是线性表，那么就与栈一样，有顺序栈和链式栈，也就有顺序队列和链式队列。它们也一样都可基于数组或者链表实现。且它支持的操作与栈不同，栈是一种后进先出的数据结构，栈顶出栈和栈顶入栈，天生决定了，后插入的元素，就一定会先被删除，它只能通过一个方向进行插入和删除。但是队列不同，想象一下日常生活中的排队买饭，谁在最前面，谁就先买到饭，也就是说谁先入队，那么谁就会先出队。它的特点是：

  1. 在队头出队，也就是删除元素

  2. 在队尾入队，也就是插入元素

它是可以在两个方向上进行操作，但是一个方向只能支持一种操作，队头删除，队尾插入。栈是一个方向的插入和删除，那就是栈顶

circle_queue_01.svg

在上图中，queue_head指向队头元素，它的值就是数组中的索引0，queue_tail指向最后一个元素的下一个位置，是数组中的索引3，以便直接入队。让我们做一个小的实验，假设上述图中的顺序队列的容量是5，那么索引的有效范围就是[0,4]。

模拟一下入队和出队的操作，还是上图，目前已经入队了三个元素，那么我现在要求出队两个元素，那么一定是1、2出队，一次出队的操作是将queue_head的值增加1。出队之后的队列是：

circle_queue_02.svg

可以看出，目前queue_head指向的是队列的队头，它的值不再是0，而是索引2，索引0和1的位置上不再是有效数据，为了防止被误解，我将其没有写上数据，那么队尾目前还没动，现在在队列中，插入1个元素5，入队的操作是：

  • 在当前队尾指针所在的索引赋值新的元素值

  • 队尾指针+1

circle_queue_03.drawio.svg

此时queue_head的值不变，queue_tail的值更新为了索引4，此时索引3的位置上插入了一个新的元素5。那么重点来了， 此时来了两个新的元素，分别是10和20，要求入队，那么还会成功入队吗？还是画图，在图中找答案：

circle_queue_04.svg

可以将元素10入队，但是20是绝对不可以入队的？为什么？因为在10入队之后，queue_tail的值已经是5，这对于数组来说已经越界了，之前假设数组的容量为5，那么它的有效下标是[0,4]，此时它的值为5，就产生了数组索引越界的情况，但明明前面还有2个有效位置可以插入的。这种情况称为假溢出。

那么如果我们每次出队的时候，都将后面的元素向后移动呢？可以这么做，但是这是基于数组这种物理结构实现，它的特点的是所有有效元素的地址都是连续的，要移动就要移动后面所有的元素的，那么之前出队O(1)的复杂度直接变成了O(n)，这是不可接受的。

环形队列

既然不可接受出队的时间复杂度从O(1)直接退为O(n)，那么既要按照原来的方式进行出队，还需要在入队的时候保证没有假溢出，充分利用有效的内存空间存储元素。那么想一想，既然不要假溢出，就需要在队尾指针的值更新的时候，不是等于5，而是等于数组索引0，那不就可以将元素20入队了吗？当然这需要判断队列是否满，这里讨论未满的情况。

那若是这样的话，队列的首尾不再是视觉上的首尾，这和栈不同。队列的首尾直接相连，彻底通过对头指针和对尾指针来观察。称这种首尾相连的队列为环形队列。

先复习一下入队时的操作：先基于当前队尾指针的值，也就是数组索引进行赋值，随后将队尾指针的值增加1。那么如果将元素20也进行入队，且不产生假溢出，再插入元素10之后，队尾指针的值应该是0，那么如何从5变成0呢？

  • 在插入元素10之后，将队尾指针(此时为4)+1，再减去5呢？那么它不就是0了吗？ok，按照这种方法，插入元素20，此时将20赋值给索引为0(也就是队尾指针的值，当前时0)，随后增加1减去5，得到队列指针的新值，可它的值是-4了，这更溢出了，所以减去5是不行的。

  • 采用模运算，当元素10入队之后，队尾指针的值从原来的4变为5导致假溢出，那么5与5的模运算是等于0的啊，采用模运算试试，此时将20入队，那么队尾指针需要增加1再模5，(0 + 1)%5，它的值为多少？那是1，刚好是索引1的值，以此类推，这是完全符合要求的。而且，这个模5，这个5刚好还是数组容量的值，因此为了避免这种假溢出的情况出现，入队的操作不再是简单的将队尾指针的值➕1，而是在➕1的基础上再对数组容量进行模运算。

计算的公式：queue_tail = (queue_tail + 1) % capacity，其实就是下一次入队的索引值等于当前索引值+1之后再对容量进行模运算。这种使得原来的顺序队列变成了环形队列，它的核心思想就是让连续的线性内存，在逻辑上首尾相连。下面是一张容量为8环形队列

circle_queue_05.svg

逻辑上是首尾相连的，但是在物理结构中，它还是一个连续的线性内存，是一个容量为8的数组。此时队头指针与队尾指针的值都初始化尾0。环形队列解决了假溢出的问题，但是同样带来了新的问题：

  1. 从图中可以看出，环形队列为空时，head == tail，也就是队头指针式等于队尾指针的。

  2. 那么环形队列满的情况如何判断呢？可想象一下，假设上述图中head == 0，tail == 7，此时需要进行入队元素100，执行入队操作

    • arr[tail] = 100
    • (tail + 1) % 8;

    此时tail的值更新为0，head的值也为0，head == tail的时候环形队列满，这是不是与队列为空的时候是一样的判断条件？这是不允许的，因此，还需要解决如何设置环形队列满或者空的条件

在教材中，采用的方法是浪费一个有效位置，按照上面的例子，当head == 0，tail == 7的时候，此时判断(tail + 1) % capacity 是否等于head。若等于，则环形队列满了， 若不等于，则不满，因此，索引为7的这个位置就不可能再被插入新的元素，造成了浪费。容量为8的环形队列，你却只能插入7个有效元素。但是假溢出的问题比浪费一个有效空间更加严重，基于数组实现的顺序队列必须是环形队列，当然，若不想假溢出，采用链式队列，它没有假溢出的烦恼，也没有扩容的性能损耗，但是它每个结点都不连续，缓存不友好。

出队时越界

通过上述入队操作带来的假溢出现象，以及使用环形队列来进行解决假溢出的理解。那么对于出队操作，会不会出现这种数组索引越界的情况呢？看一下出队的操作：

  • 将指向队头的队头指针的值+1。

对于这种线性的+1操作，当队头指针等于7的时候，对于环形队列来说，下一个出队的索引应该是索引0，但是按照上述的操作的话，索引为7 + 1 == 8了，这会产生数组越界。那么出队的操作也不能是单纯的+1了，而是与入队一样，采用环形的操作，也就是将其+1之后，再对数组容量进行模运算。(queue_head + 1) % capacity

获取队尾元素

环形队列中，队头指针一直指向的是当前队列的队头元素，那么访问队头元素时，直接使用下标访问运算符即可访问，也就是arr[queue_head]。

但是访问队尾元素时，却不是这样。因为队尾指针指向的是下一个待入队的位置。直接使用队尾指针 - 1如何呢？当然是不可以的

  • 当队尾指针的值为0时，减去1之后的值为-1，负数可作为数组下标吗，当然是不可以的。

  • 若队尾指针的值大于0，减去1之后的值大于等于0，这是可以，而且也是正确的方案。

但是两种方案不统一，这也是不可以的，而且出现负数的情况也是不对的。

回顾一下出队和入队导致的假溢出，它们导致的是正向溢出，通过+1之后对其容量取模的方式使得索引回到起始索引0，而其他未导致假溢出的情况也满足这个计算公式。因此采用这个方式来进行更新出队和入队的队头指针和队尾指针的值。

那么，现在这种情况，当队尾指针的值大于0时，可直接减去一即可，这不就相当于未导致假溢出大多数的情况嘛。当队尾指针等于0时，减去一不就相当于当队尾指针和队头指针等于最大有效索引的时候，再次入队和再次出队导致的假溢出的情况嘛。那么我们只需要对这个队尾指针等于0时的异常操作进行处理，再去使用正确的计算公式去测试正常情况(队尾指针大于0减去一的操作)是否满足不就可以了嘛？

再次回顾一下导致假溢出的情况，我称为正向溢出，最后通过+1取模的方式回到起始索引0，也就是队列开头。那么这个队尾指针减一为负数(-1)的情况，这不就是反向溢出？我也想让它回到最后一个索引不行吗？当然可以，这是最正常的操作，那么如何回到呢？

  • 正向溢出，回到起始索引0的操作是，队尾指针7加一之后对队列容量取模。

  • 反向溢出，回到末尾索引7的操作是，队尾指针0减一之后对队列容量取模呢？显然是不行的，因为在当前例子中，-1 % 8的值还是-1。既然采用正向溢出的思路不行，那么队尾指针0减一之后再加上环形队列容量呢？也就是0 - 1 + capacity，还就是等于7，这种异常情况解决，但是对于非异常情况呢？因为我们需要操作保持一致。对于非异常情况，假设此时队尾指针为1，1 - 1 + capacity的值是8，这导致正向溢出了，队尾指针为7的时候，7-1+8 = 15，也是正向溢出，但是我发现对于非异常情况，queue_tail - 1 + capacity的值的区间是[8,15]，还未到容量的2倍，这就代表回到正常有效索引区间[0,7]，只需要对queue_tail - 1 + capacity整体取模即可，而且得到的值还正好是队尾指针的上一个有效索引，可拿到有效队尾元素的值。那么对于异常情况0 - 1 + capacity整体取模是否满足呢？0 - 1 + capacity 等于7，7%8还是7，因此，这也是满足的。 其实，对于当前这个例子来说，7和9分别对8进行模运算得到的值是一样的。1和15是一样的，0和16是一样的。也就是说[1,7]与[9,15]以此类推是一直的，整数倍0、8、16、32这都是9。

所以，对于获取队尾元素的索引的计算公式就是：(queue_tail - 1 + capccity) % capacity。

三个异常

其实，之所以采用这些复杂的计算公式来获取有效索引，就是因为个别的异常的情况，而又要满足异常与非异常的统一操作。

  1. 入队时，队尾指针+1的越界导致的假溢出，假队满的现象

  2. 出队时，队头指针+1的越界导致的假队空的现象

  3. 队满时，队尾指针+1的越界导致判断队满的条件不对

以上异常可通过队尾指针+1再整体取模取解决

  1. 获取队尾元素时，队尾指针减一导致的索引为负数的异常

这个异常可通过队尾指针 - 1 + capacity在整体取模解决。

环形队列的实现

我就基于上图中容量为8的环形队列，实现一个支持常见操作，比如入队、出队、判断队空、判断队满、扩容、获取队尾元素，在大多数情况下，一般都是出队获取队头元素，队尾元素是谁不重要，因为你第一时间拿到它也执行不了什么操作，那样的话会导致逻辑很混乱。

获取队尾元素的场景

生产者端的“撤销”与“合包”机制（Rollback / Merging）

在写高性能网络服务器的接收缓冲区（Receive Buffer）时，环形队列常被用作字节流缓冲区：

  • 合并操作： 假设你的网络线程刚刚收到一个小包，写入了队列尾部。此时又来了一个极小的碎片包，为了减少系统调用和后续解析线程的负担，生产者（网络线程）可以先获取队尾元素查看一下，如果发现它和刚收到的包属于同一次传输，可以直接在队尾把它们“合并”成一个大包，而不需要重新入队新节点。

  • 撤销操作（Rollback）： 生产者在尝试写入一个大包时，写到一半发现校验和（Checksum）错误，或者连接突然中断。此时，生产者可以通过计算公式获取队尾最后一个有效元素的位置进而找到刚才写入的脏数据，直接将队尾指针的值更新为队尾最后一个有效元素所在的索引值。实现秒级撤销，而无需等这些脏数据流经整个队列去被消费者处理。

任务窃取

当主线程空闲且发现其他繁忙的线程的环形队列中的任务较多时，为了提高效率，主线程可获取其环形队列队尾元素，也就是窃取一个任务来去自己执行，将被窃取任务的线程中的环形队列的队尾指针更新为被窃取元素的索引值即可。

调试

若系统中采用环形日志缓冲区来保存日志，那么当前系统崩溃前最后写入的一条日志是什么，就可通过获取队尾元素来获取这条日志。

获取队尾元素还是很重要的。

数据结构定义

确定环形队列中的数据成员：

  1. 指向一块连续的堆内存的指针

  2. 队头指针

  3. 队尾指针

  4. 环形队列容量

环形队列有效元素的大小，可设置也可不设置，通过计算也可。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <iostream>

using std::cout;
using std::endl;

class CircleQueue {
public:
    CircleQueue(size_t capacity = 10)
        : ptr_{new int[capacity]{}},
          head_{0},
          tail_{0},
          capacity_{capacity} {}
    ~CircleQueue() {
        delete[] ptr_;
        ptr_ = nullptr;
    }

private:
    int* ptr_;
    int head_;
    int tail_;
    size_t capacity_;
};

构造函数

主要初始化环形队列中数据成员的值

  1. 队头指针和队尾指针的值初始化为0

  2. 容量设置了一个默认值

1
2
3
4
5

CircleQueue(size_t capacity = 10)
        : ptr_{new int[capacity]{}},
          head_{0},
          tail_{0},
          capacity_{capacity} {}

析构函数

主要就是释放所拥有的动态资源，防止内存泄漏

1
2
3
4

 ~CircleQueue() {
        delete[] ptr_;
        ptr_ = nullptr;
    }

环形队列的队空与队满

判断当前环形队列是否为空和是否已满

1
2
3
4
5

// 队空
bool empty() const { return tail_ == head_; }

// 队满
bool full() const { return ((tail_ + 1) % capacity_) == head_; }

环形队列的遍历

在对一个线性结构遍历的时候，找出关键的终止条件与前进公式是非常重要的。环形队列中，虽然逻辑结构是一个环形，但是底层数据结构还是一个数组，无论队头指针还是队尾指针按照(head/tail + 1) % cap的方式更新值，tail是永远在head后面的，因为入队是tail控制的，head是控制出队的，tail是绝对head后面的，head需要追赶tail，追赶的停止条件就是head == tail，此时head与tail的值相等，tail值就是下一个元素要插入的索引或者是预留的那个用不到的位置，代表整个环形队列已经遍历完毕

  1. 终止条件：head == tail

  2. head的前进条件：(head + 1) % cap;

在当前CircleQueue类中重载输出运算符函数中遍历环形队列，输出环形队列中的元素值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

std::ostream& operator<<(std::ostream& os, const CircleQueue& cq) {
    // 若环形队列为空
    if (cq.empty()) {
        return os;
    }

    // 遍历不更新head_的值，因此使用p来代替head_
    int p = cq.head_;
    while (p != cq.tail_) {
        // 输出当前p索引在当前数组中的值
        os << cq.ptr_[p] << " ";
        // 更新p
        p = (p + 1) % cq.capacity_;
    }

    return os;
}

获取环形队列中的队头队尾

获取队头

获取队头元素的方式非常简单，head_的值就是队头在环形队列中的索引

1
2

// 获取队头元素
int head() const { return ptr_[head_]; }

获取队尾

由于tail_是指向尾部元素的下一个位置，因此，若想求出队尾元素，那么需要tail_1获取队尾元素的索引值是吗？由于tail_的更新不是简单的+1，因此它的-1也绝对不是这么简单的，它也会产生异常情况，这个异常情况上述介绍过了，就是当tail_ == 0的时候，0 - 1是等于-1的，索引值是绝对不可以为负数的，因此，针对这种异常情况需要特定的解决方式。

采用的方式就是(tail - 1 + cap) % cap。思路来自于head_与tail_会导致假溢出，使其成为环形。在当前环形队列的数据结构中，容量为10。想象一下 0 - 1之后如何回到索引为9，0 - 1 + 10 == 9，刚好容量的值就是10，反复测试之后，加上容量的值就是可以回到真正的队尾。

再测试tail_ ≠ 0的时候，也完全符合，所以可以合并起来，使用这个计算公式

1
2

 // 获取队尾元素
 int tail() const { return ptr_[(tail_ - 1 + capacity_) % capacity_]; }

获取环形队列中的有效元素个数

在环形队列中，有三种方式可以获取有效元素的个数：

  1. 遍历环形队列，在head_ ≠ tail_时终止，返回得出元素的个数

     1
 2
 3
 4
 5
 6
 7
 8
 9
10

    int size() {
    int size = 0;
    int p = head_;
    while (p != tail_) {
        ++size;
        p = (p + 1) % capacity_;
    }

    return size;
}

    这种遍历方式的时间复杂度是O(n)

  2. 增加一个size_数据成员，在入队的时候自身增加1，出队的时候自身减1。时间复杂度是O(1)，通过增加一个数据成员来减少时间复杂度的操作很常用，一定要熟练。

  3. 还有一种是目前我根据head_以及tail_导致的假溢出的解决方案和求出队尾元素索引导致的异常并成功解决的方案得出的经验：

    • 在tail_大于head_的时候，tail - head就是当前环形队列中有效元素的个数

    • 但由于它是环形的，那么tail就有可能小于head，因此tail - head就会出现负数，这也是一种异常，既然是异常，那就可以解决。比如在当前环形队列中，head若等于5，tail = 1，先不使用计算公式，直接数，有效元素个数是6个，tail - head = -4，那么如果使其等于6呢，加上10啊，恰巧环形队列的容量就是10，于是tail - head + cap就可以解决当前为负数的异常。但是，若tail - head > 0的时候，再加上cap就不满足了，那没关系，将这个tail - head + cap整体与cap进行模运算即可，还是计算队尾元素索引的方案，而且这种计算的方式的时间复杂度也是O(1)，也不需要遍历和增加数据成员

    1
2

    // 获取有效元素的个数
int size() const { return ((tail_ - head_) + capacity_) % capacity_; }

从学习链表开始，对于不同的情况先分类讨论，分别得出各个情况的解决方案，最后通过分析查看是否可以合并；从环形队列中可以看到有很多异常情况，但是异常情况是绝对的少数，先处理好异常情况，最后对比异常情况与正常情况的差别，查看是否可以合并为一个计算公式，掌握思想是非常重要的。

环形队列的出队

在出队之前，查看当前环形队列是否已空，若为空，抛出异常，学习阶段，抛出异常即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 出队
void dequeue() {
    // 判断是否队空
    if (empty()) {
        throw "circle_queue is empty!";
    }

    // 更新队头指针的值
    head_ = (head_ + 1) % capacity_;
}

环形队列的出队与顺序栈的出栈的思想是一样的，只不过栈顶指针的更新与队头指针的更新方式是不同的。

环形队列的入队

在入队之前，判断当前队列是否已满，若队列已满，则进行扩容，先不讨论，先直接看入队的代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void enqueue(int val) {
    // 判断是否队满
    if (full()) {
        // 扩容
        expand(capacity_ * 2);
    }
    // 入队
    ptr_[tail_] = val;

    // 更新队尾指针的值
    tail_ = (tail_ + 1) % capacity_;
}

扩容

环形队列的扩容与顺序表以及顺序栈的扩容是不同的，因为顺序表以及顺序栈的起始元素的索引一直都是0，且数据在内存中是线性且连续的，直接使用memcpy拷贝数据的时候，不会破坏顺序表和顺序栈的逻辑。不像环形队列，它的数据在内存中并不是线性的，而是一个环形。且它的逻辑顺序和物理顺序经常是不一致的。看一个例子，假设一个环形队列的容量为5，经过入队、出队之后，它的物理结构是这样的：

circle_queue_06.svg

它的逻辑结构是这样的：C→Z→D→E->B，看到了吗，head_的值为3，tail_的值为2。逻辑结构和物理结构它不是一致的。现在申请2倍的空间，按照顺序栈或者顺序表的那种方式进行扩容和拷贝：

circle_queue_07.svg

可以看到，按照顺序表或者顺序栈的直接拷贝方式进行拷贝数据，且head_与tail_的值不变，这也是与顺序表和顺序栈保持一致。此时只有环形队列容量进行更新，它的新容量是12

此时，你若进行入队，tail_的值为2，在索引为2的位置插入一个新元素，此时需要更新tail的值，tail = (tail + 1) % cap，那就是(2 + 1) % 12 == 0的，也就是下次入队就是索引3了，这直接覆盖索引为3的数据了，导致错误。正确的拷贝之后，应该是从索引6的地方插入新的元素。

所以，正常的拷贝应该是从head_开始到tail_按照逻辑顺序一一拷贝到新的内存空间里：

circle_queue_08.svg

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void expand(size_t cap) {
    // 创建新的内存空间
    int* tmp = new int[cap]{};

    int index = 0;
    while (!empty()) {
        tmp[index] = ptr_[head_];
        // 更新队头指针的值
        head_ = (head_ + 1) % capacity_;
        index++;
    }

    // 释放旧环形队列所在的内存空间
    delete[] ptr_;

    // 更新新环形队列的值
    ptr_ = tmp;
    head_ = 0;
    tail_ = index;
    capacity_ = cap;
}

此时使用head_的值去遍历环形队列是可以的，因为拷贝完成之后，head_的值是需要重新更新的。

链式队列

链式队列本质上是一个链表，只不过链表的操作被限制在了只能在一端删除，另外一端插入新的元素。与栈还是不一样的，栈的特点是只能在一端插入和删除。在学习链式栈的时候，讨论了是将链表的头作为栈顶还是尾作为栈顶，分别从单向链表、单向循环链表、双向链表、双向循环链表的角度去分析。

那么链式队列就要分析链表头和尾谁来做队头和队尾了，因为队头是被限制只能删除结点数据的，队尾被限制在只能插入结点数据的。

首先确定一点的是：无论是单向链表、单向循环链表、双向链表、双向循环链表无论是将链表的头部作为队头还是队尾，出队入队的时间复杂度都是O(1)。

但是链表的尾部就不同，队列是有两个指针的哈，队尾指针和队头指针，假设都有。

  • 单向链表

    • 作为队头：队头是需要删除结点数据的，那么本质上就是单向链表的尾删，即使有一个队头指针(链表尾指针)，删除尾结点，还是需要找到此结点的上一个结点，删除的操作是O(1)，但是搜索上一个结点的时间复杂度是O(n)，不可取

    • 作为队尾：队尾是需要插入结点数据的，那么本质上就是单向链表的尾插，在有队尾指针(链表尾指针)的情况下，不需要搜索尾结点，可直接插入新结点，时间复杂度为O(1)

  • 单向循环链表：与单向链表是一致的。

  • 双向链表：

    • 作为队头：队头是需要删除结点数据的，那么本质上就是双向链表的尾删，在有队头指针(链表尾指针)的情况下，可直接找到尾结点，由于尾结点中有一个pre指针保存了上一个结点的地址，那么可利用这个pre指针完成删除，不需要搜索尾结点的上一个结点，时间复杂度为O(1)。可取

    • 作为队尾：与单向链表是一致的，时间复杂度也还是O(1)。

  • 双向循环链表：

    • 作为队头：队头是需要删除结点数据的，本质上也是双向循环链表的尾删，没有队头指针也是可以的，因为头结点或者第一个有效结点中的pre保存的就是尾结点的地址，可作为队头指针，删除的复杂度还是O(1)

    • 作为队尾：一样是尾结点的地址保存在头结点/第一个有效结点的pre，插入新结点数据的操作也还是O(1)

因此，对于单向链表与单向循环链表来说，使用链表的尾部作为链式队列的队头用来删除结点数据是需要搜索到尾结点的上一个结点的，时间复杂度为O(n)，而双向链表与双向循环链表都是O(1)，其中，双向链表需要有一个尾指针，也就是链式队列的队头指针。这些内容只是了解一下，最最常用的依然是无论是哪种类型的链表，都是将链表头部作为链式队列的队头的。

所以，由于链式队列需要队尾指针，那么可采用单向链表来去实现链式队列，简单实用，而且链表不需要判满，不需要扩容，没有假溢出，没有莫名其妙的异常，只有最简单的头部删除，尾部插入，时间复杂度都是O(1)，而且为了知道链式队列中有效元素的个数，增加一个size_数据成员，以免在后续还需要遍历单向链表来获取链式队列的有效元素个数。

数据结构定义

基于单向链表实现的链式队列，并添加一个尾指针tail_用于插入(入队)，size_用于在每次出队和入队的时候更新链式队列中有效元素的个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class SinglyLinkedQueue {
    struct Node {
        Node(int data = 0)
            : data_{data},
              next_{nullptr} {}
        int data_;
        Node* next_;
    };

public:
    SinglyLinkedQueue()
        : head_{new Node{}},
          tail_{head_},
          size_{0} {}
    ~SinglyLinkedQueue() {
        Node* p = head_->next_;

        while (p) {
            head_->next_ = p->next_;
            delete p;
            p = head_->next_;
        }

        delete head_;
    }
    friend std::ostream& operator<<(std::ostream& os, const SinglyLinkedQueue& slq);

private:
    Node* head_;
    Node* tail_;
    int size_;
};

在构造函数中：创建一个头结点(dummy node)

  • head_：存储这个头结点的地址值

  • tail_：将head_的值赋值给tail_，因为此时链式队列中无有效结点，头结点既是第一个结点也是最后一个结点。

  • size_：初始化为0

在析构函数中：逐一释放链式队列中的结点

  • 先循环释放有效结点

  • 最后释放头结点

重载输出运算符函数：逐一输出链式队列中的有效结点中的data数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

std::ostream& operator<<(std::ostream& os, const SinglyLinkedQueue& slq) {
    if (slq.empty()) {
        return os;
    }

    SinglyLinkedQueue::Node* p = slq.head_->next_;

    while (p) {
        std::cout << p->data_ << " -> ";
        p = p->next_;
    }
    std::cout << "nullptr";
    return os;
}

链式队列的判空

当队头指针head_与队尾指针tail_相等的时候链式队列为空

1
2

 // 判断链式队列是否为空
 bool empty() const { return head_ == tail_; }

链式队列的出队(单向链表的头删)

大概的思路：

  • 定义一个指向第一个有效结点的指针p

  • 队头指针head_的next成员指向第一个有效结点的下一个结点

  • 释放p

  • size_自身减去一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

// 出队 -- 单向链表的头删
void dequeue() {
    // 判断链式队列是否为空
    if (empty()) {
        throw "linked_queue is empty!";
    }

    // 定义指针p指向队头
    Node* p = head_->next_;

    // 队头指针指向下一个元素
    head_->next_ = p->next_;

    // 释放队头
    delete p;

    // 更新size_的值
    --size_;
}

链式队列的入队(尾插)

大概的思路就是：

  • 新建一个新的结点，将要插入的数据赋值给新结点的数据域

  • tail_尾指针的next域存储新结点的地址

  • size_自身加1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// 入队 -- 单向链表的尾插
void enqueue(int val) {
    // 定义新结点
    Node* new_node = new Node{val};

    // 插入新结点
    tail_->next_ = new_node;

    // tail_指向新尾结点
    tail_ = new_node;

    // 更新size_的值
    ++size_;
}

获取链式队列的队头、队尾、有效元素个数

  • 队头存储的数据在第一个有效结点的data域，head_→next_→data_

  • 队尾存储的数据在尾结点的data域 tail→data_

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// 获取队头元素
int front() const {
    // 判断队列是否为空
    if (empty()) {
        throw "singly_linked_queue is empty!";
    }
    return head_->next_->data_;
}

// 获取队尾元素
int back() const {
    // 判断队列是否为空
    if (empty()) {
        throw "singly_linked_queue is empty!";
    }
    return tail_->data_;
}

// 获取有效元素的个数
int size() const { return size_; }

基于双向循环链表的链式队列

虽然不需要定义尾结点，但是每个结点需要多存储一个pre指针，目前自己还不知道这样做的优势在哪里，因为链式队列也不需要中间插入和删除，只是在链式队列一端删除，另外一端插入。但还是写一下它的实现，有bug的话，后面在改吧，目前简单的测试没有bug

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145

#include <iostream>
#include <ostream>

class DoublyCircleLinkedQueue {
    struct Node {
        Node(int data = 0)
            : data_{data},
              pre_{nullptr},
              next_{nullptr} {}
        int data_;
        Node* pre_;
        Node* next_;
    };

public:
    DoublyCircleLinkedQueue()
        : head_{new Node{}},
          size_{0} {
        head_->next_ = head_;
        head_->pre_ = head_;
    }
    ~DoublyCircleLinkedQueue() {
        Node* p = head_->next_;
        while (p != head_) {
            head_->next_ = p->next_;
            delete p;
            p = head_->next_;
        }

        delete head_;
        head_ = nullptr;
    }

    // 判断当前链式队列是否为空
    bool empty() const { return head_->pre_ == head_; }

    // 出队(头删)
    void dequeue() {
        // 判断当前链式队列是否为空
        if (empty()) {
            throw "DoublyCircleLinkedQueue is empty!";
        }
        // 定义指针p指向第一个有效结点(队头结点)
        Node* p = head_->next_;

        // 头结点的next指向第一个有效结点的后一个结点
        // 后一个结点成为新的有效结点
        head_->next_ = p->next_;

        // 新的有效结点的pre指向头结点
        p->next_->pre_ = head_;

        // 释放p指向的结点
        delete p;

        // 元素个数自身减1
        --size_;
    }

    // 入队(尾插)
    void enqueue(int val) {
        // 定义新的结点
        Node* new_node = new Node{val};

        // 更新新结点的指向
        // 新结点只要成功插入就是新的尾结点，那么它的next指向头结点
        new_node->next_ = head_;
        // 它的pre指向旧的尾结点
        new_node->pre_ = head_->pre_;

        // 更新尾结点的next
        head_->pre_->next_ = new_node;

        // 更新头结点的pre
        head_->pre_ = new_node;
        // 元素个数自身加1
        ++size_;
    }

    // 获取队头元素
    int front() const {
        // 判断队列是否为空
        if (empty()) {
            throw "doubly_circle_linked_queue is empty!";
        }
        return head_->next_->data_;
    }

    // 获取队尾元素
    int back() const {
        // 判断队列是否为空
        if (empty()) {
            throw "doubly_circle_linked_queue is empty!";
        }

        return head_->pre_->data_;
    }

    // 获取元素个数
    int size() const { return size_; }
    friend std::ostream& operator<<(std::ostream& os, const DoublyCircleLinkedQueue& dclq);

private:
    Node* head_;
    size_t size_;
};
std::ostream& operator<<(std::ostream& os, const DoublyCircleLinkedQueue& dclq) {
    if (dclq.empty()) {
        return os;
    }
    DoublyCircleLinkedQueue::Node* p = dclq.head_->next_;

    while (p != dclq.head_) {
        os << p->data_ << " -> ";
        p = p->next_;
    }
    os << "nullptr";
    return os;
}

int main() {
    DoublyCircleLinkedQueue dclq;
    dclq.enqueue(20);
    dclq.enqueue(30);
    dclq.enqueue(40);
    dclq.enqueue(50);

    std::cout << dclq << std::endl;
    std::cout << "front: " << dclq.front() << std::endl;
    std::cout << "back: " << dclq.back() << std::endl;
    std::cout << "size: " << dclq.size() << std::endl;
    // 出队
    dclq.dequeue();
    std::cout << dclq << std::endl;
    std::cout << "front: " << dclq.front() << std::endl;
    std::cout << "back: " << dclq.back() << std::endl;
    std::cout << "size: " << dclq.size() << std::endl;

    // 入队
    dclq.enqueue(300);
    std::cout << dclq << std::endl;
    std::cout << "front: " << dclq.front() << std::endl;
    std::cout << "back: " << dclq.back() << std::endl;
    std::cout << "size: " << dclq.size() << std::endl;
}