C++双端队列知识点+习题

news/2025/3/18 4:53:43

        在C++中，双端队列（Deque，发音为“deck”）是标准模板库（STL）中的一种容器适配器，其全称为Double-Ended Queue。它结合了队列和栈的特点，允许在容器的两端（前端和后端）进行高效的插入和删除操作。std::deque是C++ STL中实现双端队列的具体类模板，它提供了丰富的成员函数和操作接口，使其在多种场景下都非常有用。

一、 C++双端队列知识点

1. std::deque的基本特性

  • 两端操作：可以在容器的前端（front）和后端（back）进行插入、删除和访问操作。

  • 随机访问：支持通过索引访问元素，类似于数组或std::vector。

  • 动态扩展：与std::vector类似，std::deque可以根据需要动态扩展内存，但它的扩展机制更复杂，因为它需要同时管理两端的内存。

  • 内存管理：std::deque内部通常使用多个固定大小的内存块（称为“缓冲区”）来存储元素。这种设计使得两端操作的效率很高，但随机访问的效率略低于std::vector。

2. std::deque的构造和初始化

std::deque可以通过多种方式构造：

  • 默认构造：创建一个空的双端队列。

  • 指定大小和默认值：创建一个具有指定大小的双端队列，并用默认值填充。

  • 初始化列表：使用初始化列表直接构造双端队列。

  • 从另一个容器复制或移动构造。

#include <deque>
#include <iostream>

int main() {
    // 默认构造
    std::deque<int> dq1;

    // 指定大小和默认值
    std::deque<int> dq2(5, 10); // 5个元素，每个值为10

    // 初始化列表
    std::deque<int> dq3 = {1, 2, 3, 4, 5};

    // 从另一个容器复制构造
    std::deque<int> dq4(dq3);

    std::cout << "dq1 size: " << dq1.size() << std::endl;
    std::cout << "dq2: ";
    for (int x : dq2) {
        std::cout << x << " ";
    }
    std::cout << "\ndq3: ";
    for (int x : dq3) {
        std::cout << x << " ";
    }
    std::cout << "\ndq4: ";
    for (int x : dq4) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

3. 常用操作

3.1 插入操作

  • 前端插入：push_front()，在容器前端插入一个元素。

  • 后端插入：push_back()，在容器后端插入一个元素。

  • 指定位置插入：insert()，可以在任意位置插入一个或多个元素。

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {1, 2, 3};

    // 前端插入
    dq.push_front(0);
    // 后端插入
    dq.push_back(4);

    std::cout << "Deque after insertions: ";
    for (int x : dq) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 指定位置插入
    auto it = dq.begin() + 2; // 指向索引2的位置
    dq.insert(it, 10);        // 在索引2的位置插入10

    std::cout << "Deque after insertion at position: ";
    for (int x : dq) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}
3.2 删除操作

  • 前端删除：pop_front()，删除容器前端的元素。

  • 后端删除：pop_back()，删除容器后端的元素。

  • 指定位置删除：erase()，删除任意位置的元素。

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {0, 1, 10, 2, 3, 4};

    // 前端删除
    dq.pop_front();
    // 后端删除
    dq.pop_back();

    std::cout << "Deque after deletions: ";
    for (int x : dq) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 指定位置删除
    auto it = dq.begin() + 2; // 指向索引2的位置
    dq.erase(it);             // 删除索引2的元素

    std::cout << "Deque after erasing at position: ";
    for (int x : dq) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}
3.3 访问操作

  • 访问前端元素：front()，返回前端元素的引用。

  • 访问后端元素：back()，返回后端元素的引用。

  • 通过索引访问：operator[] 或 at()，支持随机访问。

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {0, 1, 2, 3, 4};

    std::cout << "Front element: " << dq.front() << std::endl;
    std::cout << "Back element: " << dq.back() << std::endl;

    // 通过索引访问
    std::cout << "Element at index 2: " << dq[2] << std::endl;
    std::cout << "Element at index 3 (using at()): " << dq.at(3) << std::endl;

    return 0;
}
3.4 其他操作

  • 清空容器：clear()，删除所有元素。

  • 检查是否为空：empty()，判断容器是否为空。

  • 获取大小：size()，返回容器中元素的数量。

  • 交换内容：swap()，与另一个std::deque交换内容。

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {0, 1, 2, 3, 4};

    std::cout << "Is deque empty? " << (dq.empty() ? "Yes" : "No") << std::endl;
    std::cout << "Size of deque: " << dq.size() << std::endl;

    // 清空容器
    dq.clear();
    std::cout << "Deque size after clear: " << dq.size() << std::endl;

    // 交换内容
    std::deque<int> dq2 = {10, 20, 30};
    dq.swap(dq2);

    std::cout << "Deque after swap: ";
    for (int x : dq) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}

4. 迭代器支持

std::deque支持双向迭代器，可以使用begin()、end()、rbegin()和rend()等方法获取迭代器，并通过迭代器进行遍历、插入和删除操作。

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq = {0, 1, 2, 3, 4};

    // 使用迭代器遍历
    for (auto it = dq.begin(); it != dq.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用范围for循环
    for (int x : dq) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    // 使用反向迭代器
    for (auto it = dq.rbegin(); it != dq.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

5. 内存管理

std::deque的内存管理机制使其在两端操作时非常高效：

  • 它内部使用多个固定大小的内存块（缓冲区）来存储元素。

  • 每个缓冲区的大小通常与机器的页面大小（如4KB）对齐，以减少内存碎片。

  • 插入和删除操作通常只需要在缓冲区的头部或尾部进行，而不需要像std::vector那样频繁地重新分配整个内存。

这种设计使得std::deque在以下场景中非常有用：

  1. 需要频繁在两端插入和删除元素：如滑动窗口问题、任务调度等。

  2. 需要随机访问但又不希望像std::vector那样频繁重新分配内存。

6. 使用场景

6.1 滑动窗口问题

std::deque常用于解决滑动窗口的最大值或最小值问题。通过维护一个单调队列，可以在O(1)时间内获取窗口内的最大值或最小值。

#include <deque>
#include <iostream>
#include <vector>

std::vector<int> maxSlidingWindow(const std::vector<int>& nums, int k) {
    std::deque<int> dq; // 存储索引
    std::vector<int> result;

    for (int i = 0; i < nums.size(); ++i) {
        // 移除超出窗口范围的元素
        while (!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;
}

int main() {
    std::vector<int> nums = {1, 3, -1, -3, 5, 3, 6, 7};
    int k = 3;
    std::vector<int> result = maxSlidingWindow(nums, k);

    std::cout << "Max sliding window: ";
    for (int x : result) {
        std::cout << x << " ";
    }
    std::cout << std::endl;

    return 0;
}
6.2 回文检查

std::deque可以用于检查字符串或序列是否为回文。通过从两端同时读取元素，可以快速判断是否对称。

#include <deque>
#include <iostream>

bool isPalindrome(const std::string& str) {
    std::deque<char> dq(str.begin(), str.end());

    while (dq.size() > 1) {
        if (dq.front() != dq.back()) {
            return false;
        }
        dq.pop_front();
        dq.pop_back();
    }
    return true;
}

int main() {
    std::string str = "racecar";
    std::cout << str << " is palindrome? " << (isPalindrome(str) ? "Yes" : "No") << std::endl;

    return 0;
}

7. 性能对比

  • 与std::vector对比：

    • std::vector更适合随机访问，但在两端插入和删除时效率较低（尤其是前端操作）。

    • std::deque在两端操作时效率更高，但随机访问的效率略低于std::vector。

  • 与std::list对比：

    • std::list支持在任意位置高效插入和删除，但不支持随机访问。

    • std::deque支持随机访问，且在两端操作时效率更高。

8. 总结

std::deque是C++ STL中一个非常强大且灵活的容器，适用于需要在两端频繁操作的场景。它结合了队列和栈的特点，同时支持随机访问，具有较高的通用性和效率。通过合理使用std::deque，可以简化代码逻辑并提高程序性能。

二、练习 

例一、Problem - 6375

#include <deque>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int n, q; // n表示队列的数量，q表示操作的数量
    
    while (scanf("%d%d", &n, &q) != EOF) // 读取n和q，直到文件结束
    {
        deque<int> deq[n + 1]; // 创建n+1个双端队列（索引从0到n）
        
        for (int i = 0; i < q; i++) // 对每个操作进行循环
        {
            int a, u, w;
            scanf("%d%d%d", &a, &u, &w); // 读取操作类型a，以及参数u和w
            
            if (a == 1) // 如果操作类型是1，则执行插入操作
            {
                int value;
                scanf("%d", &value); // 读取要插入的值
                
                if (w == 0) // 根据w的值决定在队首还是队尾插入
                {
                    deq[u].push_front(value); // 在队首插入
                }
                else 
                {
                    deq[u].push_back(value); // 在队尾插入
                }
            }
            else if (a == 2) // 如果操作类型是2，则执行查询并删除操作
            {
                if (!deq[u].empty()) // 确保队列非空
                {
                    if (w == 0) // 根据w的值决定查询并删除队首还是队尾元素
                    {
                        printf("%d\n", deq[u][0]); // 打印队首元素
                        deq[u].pop_front(); // 删除队首元素
                    }
                    else
                    {
                        printf("%d\n", deq[u].back()); // 打印队尾元素
                        deq[u].pop_back(); // 删除队尾元素
                    }
                }
                else 
                {
                    printf("-1\n"); // 如果队列为空，打印-1
                }
            }
            else // 操作类型为3时，先交换w和v的含义，然后根据w决定是否翻转队列v，并将v的所有元素移动到队列u中
            {
                int v = w; // 注意这里先读入的是v的实际值，即原先的w
                scanf("%d", &w); // 再次读取w的真实值
                
                if (w == 1 && deq[v].size() >= 2) // 如果需要翻转且队列v至少有两个元素
                {
                    reverse(deq[v].begin(), deq[v].end()); // 翻转队列v
                }
                
                while (!deq[v].empty()) // 将队列v的所有元素移动到队列u
                {
                    deq[u].push_back(deq[v].front()); // 把队列v的队首元素添加到队列u的队尾
                    deq[v].pop_front(); // 移除队列v的队首元素
                }
            }
        }
    }
    return 0;
}

例二、 641. 设计循环双端队列 - 力扣（LeetCode）

设计实现双端队列。

实现 MyCircularDeque 类:

  • MyCircularDeque(int k) ：构造函数,双端队列最大为 k 。
  • boolean insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true ，否则返回 false 。
  • boolean insertLast() ：将一个元素添加到双端队列尾部。如果操作成功返回 true ，否则返回 false 。
  • boolean deleteFront() ：从双端队列头部删除一个元素。 如果操作成功返回 true ，否则返回 false 。
  • boolean deleteLast() ：从双端队列尾部删除一个元素。如果操作成功返回 true ，否则返回 false 。
  • int getFront() )：从双端队列头部获得一个元素。如果双端队列为空，返回 -1 。
  • int getRear() ：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1 。
  • boolean isEmpty() ：若双端队列为空，则返回 true ，否则返回 false  。
  • boolean isFull() ：若双端队列满了，则返回 true ，否则返回 false 。

示例 1：

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

解释
MyCircularDeque circularDeque = new MycircularDeque(3); // 设置容量大小为3
circularDeque.insertLast(1);			        // 返回 true
circularDeque.insertLast(2);			        // 返回 true
circularDeque.insertFront(3);			        // 返回 true
circularDeque.insertFront(4);			        // 已经满了，返回 false
circularDeque.getRear();  				// 返回 2
circularDeque.isFull();				        // 返回 true
circularDeque.deleteLast();			        // 返回 true
circularDeque.insertFront(4);			        // 返回 true
circularDeque.getFront();				// 返回 4

提示：

  • 1 <= k <= 1000
  • 0 <= value <= 1000
  • insertFront, insertLast, deleteFront, deleteLast, getFront, getRear, isEmpty, isFull  调用次数不大于 2000 次
class MyCircularDeque {
private:
    vector<int> elements;
    int rear, front;
    int capacity;

public:
    MyCircularDeque(int k) {
        capacity = k + 1;
        rear = front = 0;
        elements = vector<int>(k + 1);
    }

    bool insertFront(int value) {
        if (isFull()) {
            return false;
        }
        front = (front - 1 + capacity) % capacity;
        elements[front] = value;
        return true;
    }

    bool insertLast(int value) {
        if (isFull()) {
            return false;
        }
        elements[rear] = value;
        rear = (rear + 1) % capacity;
        return true;
    }

    bool deleteFront() {
        if (isEmpty()) {
            return false;
        }
        front = (front + 1) % capacity;
        return true;
    }

    bool deleteLast() {
        if (isEmpty()) {
            return false;
        }
        rear = (rear - 1 + capacity) % capacity;
        return true;
    }

    int getFront() {
        if (isEmpty()) {
            return -1;
        }
        return elements[front];
    }

    int getRear() {
        if (isEmpty()) {
            return -1;
        }
        return elements[(rear - 1 + capacity) % capacity];
    }   

    bool isEmpty() {
        return rear == front;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }
};

 


http://www.niftyadmin.cn/n/5891088.html

相关文章

Kubernetes学习笔记-移除Nacos迁移至K8s

Kubernetes学习笔记-移除Nacos迁移至K8s

项目服务的配置管理和服务注册发现由原先的Nacos全面迁移到Kubernetes上。 一、移除Nacos 移除Nacos组件依赖。 <dependency><groupId>com.alibaba.cloud</groupId><artifactId>spring-cloud-starter-alibaba-nacos-discovery</artifactId> <…
阅读更多...
ROS实践（三）机器人描述文件xacro（urdf扩展）

ROS实践（三）机器人描述文件xacro（urdf扩展）

目录 一、定义 二、xacro 文件常见组成部分 1. 命名空间声明 2. 定义宏 3. 调用宏 4. 定义参数 5. 条件语句 6. 转换 xacro 文件为 urdf 7. gazebo标签 三、代码示例 1. gazebo标签使用&#xff08;仿真参数配置&#xff09; 2. 引用仿真配置并定义机器人模型&#x…
阅读更多...
FSC森林认证：推动全球森林的可持续管理

FSC森林认证：推动全球森林的可持续管理

FSC森林认证是由森林管理委员会&#xff08;Forest Stewardship Council&#xff0c;简称FSC&#xff09;颁发的认证&#xff0c;旨在推动全球森林的可持续管理。该认证通过严格的评估标准&#xff0c;确保森林经营符合环境、社会和经济三方面的可持续性。 核心内容 环境可持续…
阅读更多...
【草堂笔记】ARM5到ARM6 分散文件加载错误问题

【草堂笔记】ARM5到ARM6 分散文件加载错误问题

一 、 背景 在最近的一次项目中&#xff0c;使用的是ciu32L系列的单片机&#xff0c;因为初始化时&#xff0c;需要对flash进行一些数据写入&#xff0c;发现其使用的是ARM5编译 用官方的历程编译一切正常&#xff0c;但我项目使用的是ARM6编译器&#xff0c;所以我也试了下&a…
阅读更多...
Adobe Acrobat Pro setting

Adobe Acrobat Pro setting

防火墙断网组织弹窗 Adobe软件突然弹窗“THIS APP HAS BEEN DISABLED”&#xff1f;别慌&#xff0c;几步教你轻松解决&#xff01; 禁用代理 解决Adobe出现This unlicensed Photoshop app has been disabled.禁止使用 rules:- DOMAIN-KEYWORD,adobe,REJECT
阅读更多...
C++20 `＜bit＞` 中的整数 2 的幂运算和 `std::bit_cast`：由浅入深的探索

C++20 `＜bit＞` 中的整数 2 的幂运算和 `std::bit_cast`：由浅入深的探索

文章目录 引言 1\. 整数 2 的幂运算1.1 检测是否为 2 的幂&#xff1a;std::has_single_bit1.2 计算不小于 x 的最小 2 的幂&#xff1a;std::bit_ceil1.3 计算不大于 x 的最大 2 的幂&#xff1a;std::bit_floor 2\. std::bit_cast2.1 基本用法2.2 实用场景&#xff1a;字节序…
阅读更多...
Vue3实战学习（Vue3快速搭建后台管理系统(网页头部、侧边导航栏、主体数据展示区的设计与实现)(超详细)）(9)

Vue3实战学习（Vue3快速搭建后台管理系统(网页头部、侧边导航栏、主体数据展示区的设计与实现)(超详细)）(9)

目录 一、Vue3工程环境配置、项目基础脚手架搭建、Vue3基础语法、Vue3集成Element-Plus的详细教程。(博客链接如下) 二、Vue3集成Element-Plus详细教程。(博客链接如下) 三、Vue3集成Vue-Router详细教程。(博客链接如下) 四、Vue3快速搭建后台管理系统。(实战学习) &#xff08…
阅读更多...
深入浅出C++ STL：统领STL全局

深入浅出C++ STL：统领STL全局

深入浅出C STL&#xff1a;统领STL全局 深入浅出C STL&#xff1a;统领STL全局github主页地址前言一、STL的前世今生1.1 什么是STL&#xff1f;1.2 STL版本演进 二、STL六大核心组件详解2.1 容器&#xff08;Containers&#xff09;容器性能对照表 2.2 算法&#xff08;Algorit…
阅读更多...
最新文章

Copyright @ 2022~2023