数据结构——队列（C++实现）

今天我们接着来看队列：

什么是队列

队列是一种基础且广泛应用的数据结构，它具有以下核心特征：

定义：

• 线性表：队列是一种特殊的线性表，其中的元素呈线性排列，每个元素都有一个直接前驱和一个直接后继（除了第一个元素无前驱，最后一个元素无后继）。

操作特性：

• 先进先出 (FIFO)：队列遵循“先进先出”原则，即最早进入队列的元素将最先离开队列。这意味着新元素总是被添加到队列的末端（称为队尾），而删除或访问元素则发生在队列的另一端（称为队头）。

基本操作：

1. 入队（Enqueue）：在队尾添加一个新元素。新元素成为队列中的最新成员，并且在任何已存在的元素之后等待被处理。
2. 出队（Dequeue）：从队头移除并返回最先进入队列的元素。这个操作确保了队列中最早加入的元素优先被处理。
3. 查看队头（Peek 或 Front）：返回队头元素但不移除它，允许查看即将被出队的元素而不改变队列状态。
4. 判空（IsEmpty）：检查队列是否为空，即没有任何元素。

实现方式：

• 顺序队列：使用固定大小的数组来存储元素。队头和队尾的索引需要进行适当的调整以确保正确的插入和删除。当队列满时，可能需要循环利用数组空间（环形缓冲区）或动态扩容。
• 链式队列：使用链表结构来存储元素，队头和队尾分别对应链表的首节点和尾节点。链式队列通常更易于处理队列满和队列空的情况，因为节点的增删不受固定数组大小的限制。

应用：
队列在计算机科学和许多实际应用场景中广泛使用，例如：

• 任务调度：安排任务按照提交顺序依次执行。
• 资源管理：如打印机任务队列，请求按照到达顺序打印文档。
• 消息传递：在分布式系统中，消息队列用于异步通信，发送者将消息放入队列，接收者按照消息进入队列的顺序进行消费。
• 缓存失效策略：如最近最少使用 (LRU) 缓存算法可以用双端队列来实现。
• 广度优先搜索 (BFS)：在图算法中，队列用于存储待探索的节点，确保按层级顺序遍历。

总结来说，队列是一个线性数据结构，它按照先进先出的原则组织和管理元素，支持在队尾进行插入（入队）和在队头进行删除（出队）的操作，常用于实现排队、任务调度、消息传递等场景，并可通过数组或链表等方式实现。

顺序队列

我们这里可以用一个数组来模拟队列（就是一个插入删除受限的顺序表）：

#pragma once
#include<iostream>
#include<cassert>
#include<algorithm>

template<class T>
class MyQueue
{
public:
    // 默认构造函数，初始容量为 10
    MyQueue()
        : _capacity(10)
        , _size(0)
    {
        _data = new T[_capacity]; // 分配动态数组，大小为初始容量
    }

    // 自定义容量的构造函数
    MyQueue(const size_t capacity)
        : _capacity(capacity)
        , _size(0)
    {
        _data = new T[_capacity]; // 分配动态数组，大小为指定容量
    }

    // 判断是否需要扩容，并在必要时进行扩容
    T* resizeIfNecessary()
    {
        if (_size >= _capacity) // 当元素数量达到或超过当前容量时，需要扩容
        {
            size_t newcapceity = _capacity * 2; // 新容量为原容量的两倍

            T* tmp = new T[newcapceity]; // 分配新内存

            if (tmp == nullptr)
            {
                exit(EXIT_FAILURE); // 如果内存分配失败，程序终止
            }

            std::copy_n(_data, _size, tmp); // 将原有数据复制到新内存

            delete[] _data; // 释放旧内存
            _data = tmp; // 更新数据指针
            _capacity = newcapceity; // 更新容量

            std::cout<< "has resize!!" << std::endl; // 输出扩容提示信息
        }

        return _data; // 返回当前数据指针
    }

    // 在队尾添加一个元素
    void push(const T& data)
    {
        // 判断是否需要扩容并执行扩容操作
        resizeIfNecessary();

        _data[_size] = data; // 将新元素添加到队尾
        _size++; // 增加元素数量
    }

    // 移除并返回队头元素
    T pop()
    {
        assert(_size > 0); // 断言队列非空

        T first = _data[0]; // 保存队头元素

        for(int i = 0; i < (int)_size - 1; i++) // 通过元素移动而非元素拷贝的方式移除队头元素
        {
            _data[i] = _data[i+1];
        }

        _size--; // 减少元素数量

        return first; // 返回已移除的队头元素
    }

    // 返回队头元素（不移除）
    const T& front() const
    {
        assert(_size > 0); // 断言队列非空

        return _data[0]; // 返回队头元素
    }

    // 判断队列是否为空
    bool empty() const
    {
        return _size == 0; // 若元素数量为 0，则队列为空
    }

    // 打印队列中的所有元素
    void PrintQueue()
    {
        for(int i = 0; i < _size; i++) // 输出队列中的每个元素
        {
            std::cout << _data[i] << " ";
        }

        std::cout<<std::endl; // 输出换行
    }

    // 析构函数，释放动态数组
    ~MyQueue()
    {
        delete[] _data; // 释放动态数组内存
    }

private:
    T* _data; // 动态数组，用于存储队列元素

    size_t _capacity; // 队列当前容量

    size_t _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
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

链式队列实现

我们这里用带头结点和带尾指针的单链表来实现：

#pragma once
#include<iostream>
#include<cassert>

// 结点类模板
// 用于存储链式队列中的数据元素和指向下一个结点的指针
template<class T>
struct Node
{
    // 默认构造函数，初始化数据域为默认构造的T对象，并将_next设为nullptr
    Node() : _next(nullptr), _data(T()) {}

    // 构造函数，接收一个T类型的参数data，用以初始化数据域，并将_next设为nullptr
    Node(const T& data) : _next(nullptr), _data(data) {}

    // 数据域，存储链式队列中实际的数据
    T _data;

    // 指向下一个结点的指针
    Node<T>* _next;
};

// 链式队列模板类
// 提供入队、出队、查看队首元素、判断队列是否为空等操作
template<class T>
class MyQueue
{
    // 内部类型别名，简化代码中的结点类型名称
    typedef Node<T> _Node;

public:
    // 构造函数，初始化队列为空，头尾指针均指向空结点
    MyQueue() : _size(0)
    {
        _head = new _Node();
        _tail = _head;
    }

    // 创建新结点，接收一个T类型的参数data，返回新建的结点指针
    _Node* createNode(const T& data)
    {
        _Node* newnode = new _Node(data);

        if (newnode == nullptr)
        {
            exit(EXIT_FAILURE); // 如果内存分配失败，程序退出
        }

        return newnode;
    }

    // 入队操作，将给定数据插入队尾
    void push(const T& data)
    {
        _Node* newnode = createNode(data);

        if (_head->_next == nullptr)
        {
            _head->_next = newnode;
            _tail = newnode;
        }
        else
        {
            _tail->_next = newnode;
            _tail = newnode;
        }
        _size++; // 入队成功后，队列大小增一
    }

    // 出队操作，移除并返回队首元素
    T pop()
    {
        assert(_size > 0); // 若队列为空，程序终止

        _Node* first = _head->_next;

        T first_data = first->_data; // 保存队首元素的值

        _Node* second = first->_next;

        _head->_next = second; // 更新头结点的_next，使其指向原队首元素的下一个结点

        delete first; // 删除原队首结点

        --_size; // 出队成功后，队列大小减一

        return first_data; // 返回原队首元素的值
    }

    // 查看队首元素（不移除）
    const T& front() const
    {
        assert(_size > 0); // 若队列为空，程序终止
        return _head->_next->_data; // 直接返回队首元素的值
    }

    // 判断队列是否为空
    bool empty() const
    {
        return _size == 0; // 如果队列大小为0，说明队列为空
    }

    // 打印队列中的所有元素
    void PrintQueue()
    {
        _Node* cur = _head->_next;

        while (cur)
        {
            std::cout << cur->_data << " "; // 输出当前结点的值
            cur = cur->_next; // 移动到下一个结点
        }

        std::cout << "END" << std::endl; // 打印结束标记
    }

private:
    // 头结点，其_next指向队首元素
    _Node* _head;

    // 尾结点，始终指向队尾元素
    _Node* _tail;

    // 队列中元素的数量
    size_t _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
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

我们这里简单介绍一下，我们要看的几种队列的变形——双端队列，循环队列。