04、队列

厨子大约 6 分钟数据结构算法基础面试题解析队列程序厨校招社招

队列

队列模型

像栈一样，队列（queue）也是表。然而使用队列时插入在一端进行而删除在另一端进行，遵守先进先出的规则。所以队列的另一个名字是（FIFO）。

队列的基本操作

入队（enqueue）：它是在表的末端(队尾(rear)插入一个元素。

出队（dequeue）: 出队他是删除在表的开头（队头(front)）的元素。

注：下面模型只象征着输入输出操作

具体模型

队列的实现

下面给大家说一下队列的简单使用

#include <queue>
#include <iostream>
#include <string>

int main() {
    // 创建不同类型的队列
    std::queue<int> int_queue;
    std::queue<std::string> string_queue;
    std::queue<double> double_queue;
    
    int_queue.push(10);
    int_queue.push(20);
    int_queue.push(30);
    int_queue.push(40);
    int_queue.push(50);
    
    std::cout << "队列的大小: " << int_queue.size() << std::endl;
    std::cout << "队首元素: " << int_queue.front() << std::endl;
    std::cout << "队尾元素: " << int_queue.back() << std::endl;
    
    while (!int_queue.empty()) {
        std::cout << "出队: " << int_queue.front() << std::endl;
        int_queue.pop();
    }
    
    string_queue.push("苹果");
    string_queue.push("香蕉");
    string_queue.push("橙子");
    string_queue.push("葡萄");
    
    std::cout << "队列的大小: " << string_queue.size() << std::endl;
    std::cout << "队首元素: " << string_queue.front() << std::endl;
    
    while (!string_queue.empty()) {
        std::cout << "出队: " << string_queue.front() << std::endl;
        string_queue.pop();
    }
    
    double_queue.push(3.14);
    double_queue.push(2.718);
    double_queue.push(1.414);
    
    // 演示队列的其他操作
    std::queue<int> demo_queue;
    
    std::cout << "队列是否为空: " << (demo_queue.empty() ? "是" : "否") << std::endl;
    
    demo_queue.push(100);
    demo_queue.push(200);
    demo_queue.push(300);
    
    std::cout << "压入3个元素后，队列的大小: " << demo_queue.size() << std::endl;
    std::cout << "队首元素: " << demo_queue.front() << std::endl;
    
    demo_queue.pop();
    std::cout << "出队1个元素后，队列的大小: " << demo_queue.size() << std::endl;
    std::cout << "新的队首元素: " << demo_queue.front() << std::endl;

    return 0;
}

我们想一下，既然我们只需要先入先出，顺序入队，那是否可以使用 vector 来实现队列呢？

必须可以

// 使用vector实现队列类
template<typename T>
class Queue {
private:
    std::vector<T> data;
    
public:
    // 入队操作
    void push(const T& item) {
        data.push_back(item);
    }
    
    // 出队操作
    void pop() {
        if (!empty()) {
            data.erase(data.begin());
        }
    }
    
    // 查看队首元素
    T front() const {
        if (!empty()) {
            return data.front();
        }
        throw std::runtime_error("队列为空");
    }
    
    // 查看队尾元素
    T back() const {
        if (!empty()) {
            return data.back();
        }
        throw std::runtime_error("队列为空");
    }
    
    // 判断队列是否为空
    bool empty() const {
        return data.empty();
    }
    
    // 获取队列大小
    size_t size() const {
        return data.size();
    }
    
    // 清空队列
    void clear() {
        data.clear();
    }
};

循环队列

循环队列的出现就是为了解决队列的假溢出问题。

何为假溢出呢？我们运用数组实现队列时，数组长度为 5，我们放入了[1,2,3,4,5].

我们将 1，2 出队，此时如果继续加入 6 时，因为数组末尾元素已经被占用，再向后加则会溢出，但是我们的下标 0，和下标 1 还是空闲的。

所以我们把这种现象叫做“假溢出”。

例如，我们在学校里面排队洗澡一人一个格，当你来到澡堂发现头部有两个空格，但是其余格子已经满了，你是去前面洗，还是等其他格子的哥们洗完再洗？

肯定是去前面的格子洗。除非澡堂的所有格子都满了，我们才会等。

所以我们用来解决假溢出的方法就是后面满了，就再从头开始，也就是头尾相接的循环，我们把队列的这种头尾相接的顺序存储结构成为循环队列。

我们发现队列为空时 front == rear，队列满时也是 front == rear，那么问题来了，我们应该怎么区分满和空呢？

我们可以通过以下两种方法进行区分，

1.设置标记变量 flag; 当 front == rear 时且 flag = 0 时为空，当 front == rear 且 flag == 1 时为满

2.当队列为空时，front == rear, 当队列满时，我们保留一个元素空间，也就是说，队列满时，数组内还有一个空间（故意不放置内容）。

两种方式的具体介绍：

循环队列中，由于队头（front）和队尾（rear）指针会循环移动，当 front == rear 时可能表示队列空或满，需要通过特殊方式区分。常用两种两种常用方案：

标记变量法
1. 增设一个布尔型标记变量 flag（初始为 false）。
2. 空队列：front == rear 且 flag == false（初始状态或所有元素出队后）。
3. 满队列：front == rear 且 flag == true（当元素入队导致队尾追上队头时，将 flag 置为 true）。
4. 入队时，若操作后 front == rear，则 flag = true；出队时，若操作后 front == rear，则 flag = false。
5. 优点：队列空间可完全利用（数组大小为 n 时，最多存储 n 个元素）。
6. 缺点：需额外维护标记变量，逻辑稍复杂。
预留空间法
1. 不设标记，而是通过预留一个空元素空间区分状态。
2. 空队列：front == rear（初始状态或所有元素出队后）。
3. 满队列：(rear + 1) % maxSize == front（队尾指针的下一个位置是队头时，视为满）。
4. 此时队列最大存储量为 maxSize - 1（maxSize 为数组长度），始终保留一个空闲位置。
5. 优点：无需额外变量，逻辑简单，实现方便。
6. 缺点：浪费一个存储空间，当队列容量较小时，空间利用率略低。