#c

队列(Queue)

数据结构基础

#c
@鞠大龙
魅客科创中心

CONTENTS

目录

1. 队列的基本概念

1.1 队列的定义

  • 队列(Queue)的定义：
    • 队列是一种线性数据结构
    • 只允许在一端（队尾）进行插入，在另一端（队头）进行删除
    • 遵循 先进先出(FIFO, First In First Out) 原则
    • 可以类比为排队等候的场景
  • 队列的特点：
    • 操作受限的线性表
    • 插入操作在队尾，删除操作在队头
    • 最先插入的元素最先被删除
    • 只能访问队头和队尾元素，无法直接访问队列中间元素

1.2 FIFO原理

  • 先进先出(FIFO)原理：
    • 最先放入队列中的元素，会最先被取出
    • 最后放入队列中的元素，会最后被取出
    • 类似于日常生活中的"排队"场景
  • FIFO与LIFO的区别：
    • FIFO(First In First Out)：队列的特性
    • LIFO(Last In First Out)：栈的特性
    • 两者是相反的操作原则

1.3 队列的特性

队列的基本特性：

  1. 有序性：
    • 元素在队列中的存储是有序的
    • 按照插入顺序排列，先入先出
  2. 公平性：
    • 所有元素按照到达顺序依次处理
    • 保证先到的请求先被服务
  3. 受限访问：
    • 只能访问队头和队尾元素
    • 要访问队列中间元素，必须先删除前面的所有元素
  4. 动态大小：
    • 队列的大小可以动态变化
    • 但在某些实现中可能有容量限制

2. 队列的基本操作

2.1 队列的基本操作概述

队列支持的主要操作：

  • enqueue：将元素加入队尾
  • dequeue：移除队头元素
  • front：查看队头元素但不移除
  • back：查看队尾元素
  • empty：检查队列是否为空
  • size：获取队列中元素个数

2.2 Enqueue操作

  • Enqueue操作：
    • 将一个元素添加到队尾
    • 时间复杂度：
  • 实现步骤：
    1. 检查队列是否已满（数组实现时）
    2. 将元素放入队尾位置
    3. 队尾指针加1
  • 示例代码：
void enqueue(int value) {
    if (isFull()) {
        cout << "Queue is Full" << endl;
        return;
    }
    if (isEmpty()) {
        front = rear = 0;
    } else {
        rear = (rear + 1) % capacity;
    }
    arr[rear] = value;
    size++;
}

注意事项：

  • 数组实现时需要检查队列是否已满
  • 循环队列实现时需要使用取模运算
  • 链表实现时通常不需要检查容量
  • STL实现时会自动处理内存分配

2.3 Dequeue操作

  • Dequeue操作：
    • 移除队头元素
    • 时间复杂度：
  • 实现步骤：
    1. 检查队列是否为空
    2. 获取队头元素
    3. 队头指针加1（循环队列时取模）
    4. 返回之前的队头元素
  • 示例代码：
int dequeue() {
    if (isEmpty()) {
        cout << "Queue is Empty" << endl;
        return -1;
    }
    int item = arr[front];
    if (front == rear) {
        front = rear = -1;
    } else {
        front = (front + 1) % capacity;
    }
    size--;
    return item;
}

注意事项：

  • 必须检查队列是否为空
  • 删除元素后，该位置的内存仍然保留原值
  • 但该位置逻辑上已不属于队列
  • 连续dequeue操作会按照FIFO顺序删除元素

2.4 Front操作

Front操作：

  • 返回队头元素但不移除
  • 时间复杂度：
    实现步骤：
  1. 检查队列是否为空
  2. 返回队头元素的值
    示例代码：
int front() {
    if (isEmpty()) {
        cout << "Queue is Empty" << endl;
        return -1;
    }
    return arr[front];
}

注意事项：

  • 与dequeue操作不同，front操作不会修改队列的状态
  • 常用于需要查看队头元素但不想移除它的场景
  • 在C++ STL中，front()返回队头元素的引用

2.5 其他操作

  • Back操作：
    • 返回队尾元素
    • 时间复杂度：
int back() {
    if (isEmpty()) {
        cout << "Queue is Empty" << endl;
        return -1;
    }
    return arr[rear];
}
  • Empty操作：
    • 检查队列是否为空
    • 时间复杂度：
bool isEmpty() {
    return (front == -1 && rear == -1);
}
  • Size操作：
    • 返回队列中元素的数量
    • 时间复杂度：
int size() {
    if (isEmpty()) return 0;
    return size;
}
  • isFull操作（数组实现时）：
    • 检查队列是否已满
    • 时间复杂度：
bool isFull() {
    return ((rear + 1) % capacity == front);
}
  • Clear操作：
    • 清空队列中的所有元素
    • 时间复杂度：
void clear() {
    front = rear = -1;
    size = 0;
}

3. 队列的实现方式

3.1 数组实现队列

数组实现队列：

  • 使用固定大小的数组存储元素
  • 需要维护队头和队尾指针
  • 可能面临"假溢出"问题

实现代码：

class ArrayQueue {
private:
    int* arr;
    int capacity;
    int front;
    int rear;
    int size;
    
public:
    ArrayQueue(int cap) {
        capacity = cap;
        arr = new int[capacity];
        front = rear = -1;
        size = 0;
    }
    
    bool isEmpty() {
        return front == -1;
    }
    
    bool isFull() {
        return (rear + 1) % capacity == front;
    }
    
    void enqueue(int item) {
        if (isFull()) return;
        
        if (isEmpty()) {
            front = rear = 0;
        } else {
            rear = (rear + 1) % capacity;
        }
        arr[rear] = item;
        size++;
    }
    
    int dequeue() {
        if (isEmpty()) return -1;
        
        int item = arr[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % capacity;
        }
        size--;
        return item;
    }
};

数组实现的优缺点：

优点：

  • 内存连续，访问速度快
  • 实现简单，易于理解
  • 不需要额外的指针开销

缺点：

  • 固定大小，可能浪费空间
  • 面临"假溢出"问题
  • 需要处理边界条件

适用场景：

  • 队列大小固定的场景
  • 对性能要求较高的场景
  • 内存受限的环境

3.2 链表实现队列

链表实现队列：

  • 使用链表动态存储元素
  • 需要维护队头和队尾指针
  • 可以动态调整大小

实现代码：

struct Node {
    int data;
    Node* next;
    Node(int d) : data(d), next(nullptr) {}
};

class LinkedListQueue {
private:
    Node* front;
    Node* rear;
    int size;
    
public:
    LinkedListQueue() {
        front = rear = nullptr;
        size = 0;
    }
    
    bool isEmpty() {
        return front == nullptr;
    }
    
    void enqueue(int item) {
        Node* temp = new Node(item);
        if (isEmpty()) {
            front = rear = temp;
        } else {
            rear->next = temp;
            rear = temp;
        }
        size++;
    }
    
    int dequeue() {
        if (isEmpty()) return -1;
        
        Node* temp = front;
        int item = temp->data;
        front = front->next;
        
        if (front == nullptr) {
            rear = nullptr;
        }
        
        delete temp;
        size--;
        return item;
    }
};

链表实现的优缺点：

优点：

  • 动态大小，无需预分配
  • 不会出现"假溢出"问题
  • 内存利用率高

缺点：

  • 需要额外的指针空间
  • 访问速度相对较慢
  • 实现相对复杂

适用场景：

  • 队列大小不确定的场景
  • 需要频繁插入删除的场景
  • 内存充足的环境

3.3 循环队列

循环队列：

  • 数组实现的优化版本
  • 通过取模运算实现循环使用
  • 解决"假溢出"问题

实现代码：

class CircularQueue {
private:
    int* arr;
    int capacity;
    int front;
    int rear;
    int size;
    
public:
    CircularQueue(int cap) {
        capacity = cap;
        arr = new int[capacity];
        front = rear = -1;
        size = 0;
    }
    
    bool isEmpty() {
        return front == -1;
    }
    
    bool isFull() {
        return (rear + 1) % capacity == front;
    }
    
    void enqueue(int item) {
        if (isFull()) return;
        
        if (isEmpty()) {
            front = 0;
        }
        rear = (rear + 1) % capacity;
        arr[rear] = item;
        size++;
    }
    
    int dequeue() {
        if (isEmpty()) return -1;
        
        int item = arr[front];
        if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % capacity;
        }
        size--;
        return item;
    }
};

循环队列的特性：

核心思想：

  • 将数组视为环形结构
  • 通过取模运算实现循环
  • 充分利用数组空间

优势：

  • 解决"假溢出"问题
  • 提高内存利用率
  • 保持的时间复杂度

注意事项：

  • 需要区分空队列和满队列
  • 队满条件：(rear + 1) % capacity == front
  • 队空条件：front == -1

3.4 C++ STL中的队列

STL队列：

  • #include <queue>
  • 基于deque或list实现
  • 提供完整的队列功能

基本用法：

#include <queue>
#include <iostream>
using namespace std;

int main() {
    queue<int> q;
    
    // 入队操作
    q.push(10);
    q.push(20);
    q.push(30);
    
    // 访问队头
    cout << "Front: " << q.front() << endl;
    
    // 出队操作
    q.pop();
    cout << "Front after pop: " << q.front() << endl;
    
    // 队列大小
    cout << "Size: " << q.size() << endl;
    
    return 0;
}

STL队列操作：

主要成员函数：

  • push()：在队尾插入元素
  • pop()：删除队头元素
  • front()：返回队头元素
  • back()：返回队尾元素
  • empty()：检查队列是否为空
  • size()：返回队列大小

性能特点：

  • 所有操作时间复杂度：
  • 自动处理内存管理
  • 线程不安全（需要手动同步）

使用建议：

  • 优先使用STL队列
  • 避免手动实现，除非有特殊需求
  • 注意异常安全性

4. 队列的应用场景

4.1 操作系统中的应用

进程调度：

  • 多任务操作系统使用队列管理进程
  • 按照FIFO原则分配CPU时间
  • 保证公平性和响应性

打印队列：

  • 多个打印任务排队等待
  • 按照提交顺序依次打印
  • 避免资源冲突

消息队列：

  • 进程间通信的机制
  • 异步处理消息传递
  • 解耦生产者和消费者

4.2 网络通信中的应用

数据包排队：

  • 网络路由器使用队列缓存数据包
  • 按照到达顺序转发
  • 处理网络拥塞

请求队列：

  • Web服务器处理客户端请求
  • 防止服务器过载
  • 保证请求处理的顺序性

缓冲区管理：

  • 流媒体播放的缓冲机制
  • 平滑数据传输速率
  • 提高用户体验

4.3 算法设计中的应用

广度优先搜索(BFS)：

  • 图遍历算法的基础
  • 使用队列管理待访问节点
  • 保证按层次遍历

缓存淘汰算法：

  • FIFO缓存淘汰策略
  • 按照进入顺序淘汰最旧数据
  • 简单有效的缓存管理

任务调度算法：

  • 轮询调度算法
  • 公平分配计算资源
  • 适用于时间片轮转

5. 经典例题

5.1 广度优先搜索(BFS)

问题描述：
使用队列实现图的广度优先搜索

算法思路：

  1. 从起始节点开始
  2. 将节点加入队列
  3. 依次处理队列中的节点
  4. 将未访问的邻居加入队列

代码实现：

void BFS(int start, vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    queue<int> q;
    
    visited[start] = true;
    q.push(start);
    
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        cout << current << " ";
        
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

BFS特性分析：

时间复杂度：

  • ，其中V是顶点数，E是边数

空间复杂度：

  • ，用于存储访问标记和队列

应用场景：

  • 最短路径问题（无权图）
  • 连通分量检测
  • 层次遍历树或图

队列的作用：

  • 保证按层次遍历
  • 管理待访问节点
  • 实现FIFO访问顺序

5.2 滑动窗口最大值

问题描述：
给定数组和窗口大小，求每个窗口的最大值

算法思路：
使用双端队列维护窗口内的最大值索引

代码实现：

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
    vector<int> result;
    deque<int> dq;
    
    for (int i = 0; i < nums.size(); i++) {
        // 移除超出窗口的元素
        if (!dq.empty() && dq.front() == i - k) {
            dq.pop_front();
        }
        
        // 维护递减队列
        while (!dq.empty() && nums[dq.back()] < nums[i]) {
            dq.pop_back();
        }
        
        dq.push_back(i);
        
        // 记录窗口最大值
        if (i >= k - 1) {
            result.push_back(nums[dq.front()]);
        }
    }
    
    return result;
}

算法分析：

时间复杂度：

  • ，每个元素入队出队一次

空间复杂度：

  • ，队列大小不超过k

关键技巧：

  • 使用双端队列维护候选最大值
  • 及时移除无效的候选值
  • 保证队列的单调性

队列变种：

  • 双端队列(deque)
  • 支持两端操作
  • 适合滑动窗口问题

5.3 循环队列实现

问题描述：
设计循环队列，支持enqueue、dequeue等操作

设计要点：

  • 区分空队列和满队列
  • 正确处理边界条件
  • 高效利用数组空间

完整实现：

class MyCircularQueue {
private:
    vector<int> data;
    int head;
    int tail;
    int size;
    int capacity;
    
public:
    MyCircularQueue(int k) {
        data.resize(k);
        head = -1;
        tail = -1;
        size = 0;
        capacity = k;
    }
    
    bool enQueue(int value) {
        if (isFull()) return false;
        
        if (isEmpty()) {
            head = 0;
        }
        tail = (tail + 1) % capacity;
        data[tail] = value;
        size++;
        return true;
    }
    
    bool deQueue() {
        if (isEmpty()) return false;
        
        if (head == tail) {
            head = tail = -1;
        } else {
            head = (head + 1) % capacity;
        }
        size--;
        return true;
    }
    
    int Front() {
        if (isEmpty()) return -1;
        return data[head];
    }
    
    int Rear() {
        if (isEmpty()) return -1;
        return data[tail];
    }
    
    bool isEmpty() {
        return size == 0;
    }
    
    bool isFull() {
        return size == capacity;
    }
};

实现细节：

边界处理：

  • 空队列：head == -1 && tail == -1
  • 满队列：size == capacity
  • 单个元素：head == tail

指针移动：

  • 使用取模运算实现循环
  • 注意负数取模的处理
  • 保持指针的有效性

测试用例：

  • 空队列操作
  • 满队列操作
  • 边界条件测试
  • 性能压力测试

6. 优化技巧

6.1 内存优化

预分配空间：

  • 根据业务需求预分配队列大小
  • 避免频繁的内存分配
  • 减少内存碎片

对象池技术：

  • 复用队列节点对象
  • 减少new/delete开销
  • 提高内存使用效率

内存对齐：

  • 优化数据结构布局
  • 提高缓存命中率
  • 减少内存访问时间

6.2 性能优化

批量操作：

  • 支持批量入队出队
  • 减少函数调用开销
  • 提高吞吐量

无锁队列：

  • 多线程环境下的优化
  • 避免锁竞争
  • 提高并发性能

缓存友好：

  • 优化数据访问模式
  • 提高缓存局部性
  • 减少缓存失效

6.3 功能扩展

优先级队列：

  • 支持按优先级处理
  • 结合堆数据结构
  • 适用于任务调度

延迟队列：

  • 支持延迟执行
  • 基于时间戳排序
  • 适用于定时任务

阻塞队列：

  • 支持线程同步
  • 生产者-消费者模式
  • 适用于并发编程

7. 总结

7.1 核心知识点回顾

基本概念：

  • FIFO（先进先出）原则
  • 队头、队尾操作
  • 受限访问特性

实现方式：

  • 数组实现（包括循环队列）
  • 链表实现
  • STL队列使用

时间复杂度：

  • 所有基本操作：
  • 适合频繁插入删除的场景

7.2 重点难点分析

循环队列的实现：

  • 区分空队列和满队列
  • 正确处理边界条件
  • 取模运算的应用

BFS算法中的队列：

  • 层次遍历的实现
  • 访问标记的管理
  • 性能优化的技巧

多线程队列：

  • 线程安全问题
  • 锁机制的选择
  • 性能与安全的平衡

8. 练习题目

8.1 基础练习题

题目1：队列基本操作

  • 实现队列的enqueue、dequeue、front操作
  • 测试各种边界条件
  • 难度：★☆☆☆☆

题目2：循环队列实现

  • 设计完整的循环队列类
  • 支持所有基本操作和状态查询
  • 难度：★★☆☆☆

题目3：BFS遍历

  • 使用队列实现图的广度优先搜索
  • 输出遍历顺序和层次信息
  • 难度：★★☆☆☆

8.2 进阶练习题

题目4：滑动窗口最大值

  • 使用双端队列解决滑动窗口问题
  • 优化时间复杂度到
  • 难度：★★★☆☆

题目5：多线程队列

  • 实现线程安全的队列
  • 支持生产者和消费者模式
  • 难度：★★★★☆

题目6：优先级队列应用

  • 结合堆实现优先级队列
  • 解决任务调度问题
  • 难度：★★★★☆

8.3 竞赛题目推荐

LeetCode相关题目：

    1. 用队列实现栈
    1. 用栈实现队列
    1. 滑动窗口最大值
    1. 设计循环队列

算法竞赛经典：

  • BFS求最短路径
  • 拓扑排序
  • 网络流算法
  • 消息队列模拟

谢谢！

问题与讨论

#c

联系方式：

  • 邮箱：example@xmaker.org
  • 网站：www.xmaker.org

演讲者备注不会在演示模式中显示给观众，仅供演讲者参考。 每个关键页面都添加了备注，帮助演讲者更好地讲解内容。

封面页： - 欢迎学生，简要介绍本次课程的主题和目标 - 强调队列在数据结构和算法中的重要性 - 本讲义将从基本概念到实际应用，系统讲解队列的原理和应用

目录页： - 简要介绍讲义结构 - 队列的基本概念、操作、实现、应用、例题等

转场页： - 介绍队列的基本概念 - 引入FIFO原理

队列的定义： - 基础知识介绍 - 与其他数据结构的区别

转场页： - 介绍队列的基本操作 - 引入enqueue、dequeue等核心操作

转场页： - 介绍队列的不同实现方式 - 包括数组、链表、循环队列等

转场页： - 介绍队列在实际中的应用 - 包括操作系统、网络、算法等

转场页： - 介绍队列相关的经典问题 - 包括算法竞赛和实际应用

转场页： - 介绍队列使用的优化技巧 - 提高性能和效率

转场页： - 总结队列的核心知识点 - 强调重点和难点

转场页： - 提供练习题供学生巩固 - 包括基础题和进阶题