数据结构——双端队列

我们今天来看队列的变形——双端队列：

什么是双端队列

双端队列（Double-Ended Queue, 简称deque）是一种特殊的数据结构，它结合了队列（Queue）和栈（Stack）的特性，允许在两端进行插入（enqueue）和删除（dequeue）操作。双端队列可以在前端（front）进行入队（push）和出队（pop），也可以在后端（rear）进行入队和出队。这种灵活性使得双端队列在很多应用场景中非常实用，特别是在需要高效地处理双向数据流或需要快速访问两端元素的场合。

基本特征：

1. 两端操作： 双端队列允许在队列的头部（front）和尾部（rear）同时进行插入和删除操作。这意味着您可以从队列的开始或结束处添加或移除元素。
2. 先进先出（FIFO）与后进先出（LIFO）共存： 根据操作端的不同，双端队列可以表现出队列（FIFO）或栈（LIFO）的行为。在前端出队遵循FIFO原则（最先加入的元素最先离开），在后端出队则遵循LIFO原则（最后加入的元素最先离开）。
3. 动态大小： 双端队列的大小通常不是固定的，可以根据需要动态增长或缩小。当元素被添加到队列中时，队列会自动扩容以容纳新元素；当元素被移除时，队列空间会被释放，以保持高效的空间利用率。
4. 多用途： 双端队列在许多算法和应用程序中都有广泛应用，如实现回溯、滑动窗口、缓存、双向链表等。它既可用于常规的队列操作，如任务调度、消息队列等，也可用于需要栈功能的场景，如撤销/重做操作记录、深度优先搜索的回溯等。

常见操作：

• push_front: 在队列前端插入元素。
• push_rear: 在队列后端插入元素。
• pop_front: 从队列前端移除并返回元素。
• pop_rear: 从队列后端移除并返回元素。
• peek_front: 查看但不移除队列前端的元素。
• peek_rear: 查看但不移除队队后端的元素。
• is_empty: 判断双端队列是否为空。
• size: 返回双端队列中元素的数量。

实现双端队列的数据结构可以是数组、链表或更复杂的数据结构。使用数组实现时，可能需要进行动态扩容或移动元素以维持高效的插入和删除操作。链表实现则更为灵活，无需考虑连续内存空间的限制，但访问性能可能略逊于数组实现。现代编程语言中通常有内置的双端队列数据结构或第三方库提供高效实现。

总之，双端队列是一种提供两端插入和删除能力的数据结构，它结合了队列和栈的优点，适用于需要高效处理双向数据流或频繁操作两端元素的场景。

在C++中，双向队列，在头文件deque中：

我们可以使用一下它的接口：

#include <iostream>
#include<deque>

void PrintDque(const std::deque<int>& dq)
{
    std::deque<int>::const_iterator it = dq.cbegin();
    while( it != dq.cend())
    {
        std::cout << *it++ << ' ';
    }
    std::cout<<std::endl;

}

int main()
{
    std::deque<int> dq;

    dq.push_back(12);
    dq.push_back(13);
    dq.push_back(14);
    dq.push_back(15);

    PrintDque(dq);

    dq.push_front(16);
    dq.push_front(17);
    dq.push_front(18);
    dq.push_front(19);

    PrintDque(dq);

    dq.pop_back();
    dq.pop_back();
    dq.pop_back();
    dq.pop_back();

    PrintDque(dq);

    dq.pop_front();
    dq.pop_front();
    dq.pop_front();
    dq.pop_front();

    PrintDque(dq);

    if(dq.empty())
    {
        std::cout << "dque is empty" << std::endl;
    }
    
    return 0;
}


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

双端队列的实现

为了节省时间，我们这里使用vector来作为deque的底层结构：

#include<iostream>
#include<vector>

// 定义一个名为 Deque（双端队列）的类
class Deque{
public:
    // 默认构造函数，创建一个空的双端队列
    Deque() = default;

    // 返回一个布尔值，表示当前双端队列是否为空
    bool is_empty() const
    {
        return items.empty();
    }

    // 在双端队列的前端添加一个整数元素（item）
    void add_front(int item)
    {
        items.insert(items.begin(), item); // 使用 insert 函数将新元素插入到 vector 开头
    }

    // 在双端队列的后端添加一个整数元素（item）
    void add_rear(int item)
    {
        items.push_back(item); // 使用 push_back 函数将新元素添加到 vector 末尾
    }

    // 从双端队列的前端移除并返回一个整数元素
    int remove_front()
    {
        if (is_empty()) // 检查队列是否为空
        {
            return -1; // 若为空，返回 -1 表示操作失败
        }
        
        int front_item = items.front(); // 获取队列前端元素的值
        items.erase(items.begin()); // 使用 erase 函数移除 vector 开头的元素
        return front_item; // 返回移除的元素值
    }

    // 从双端队列的后端移除并返回一个整数元素
    int remove_rear()
    {
        if (is_empty()) // 检查队列是否为空
        {
            return -1; // 若为空，返回 -1 表示操作失败
        }
        
        int rear_item = items.back(); // 获取队列后端元素的值
        items.pop_back(); // 使用 pop_back 函数移除 vector 末尾的元素
        return rear_item; // 返回移除的元素值
    }

private:
    // 使用 std::vector 存储双端队列中的整数元素
    std::vector<int> items;
};
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

int main()
{
    Deque deque;
    deque.add_front(1);
    deque.add_front(2);
    deque.add_rear(3);
    deque.add_rear(4);

    std::cout << "Deque front: " << deque.remove_front()<< std::endl;
    std::cout << "Deque rear: " << deque.remove_rear()<< std::endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

双端队列的使用场景

双端队列作为一种特殊的数据结构，具有在两端同时进行插入和删除操作的能力，这使得它适用于多种需要灵活增删元素的场景。以下是双端队列的一些典型使用场景：

1. 滑动窗口算法：
   双端队列常被用于实现滑动窗口相关的问题，如计算数据流中一定时间段内的统计信息（如平均值、最大值、最小值等）。当新的数据进入窗口时，旧的数据会从另一端移出，双端队列能很好地模拟这种动态窗口的更新过程。
2. 队列管理：
   在生产者-消费者模型中，双端队列可以用来高效地管理和同步任务。生产者在队列一端（通常是后端）添加任务，消费者则从另一端（通常是前端）取出并执行任务。双端队列支持高效并发操作，有利于提高系统吞吐量。
3. 回溯算法：
   在解决某些需要进行路径搜索或状态回溯的问题（如深度优先搜索、迷宫求解等）时，双端队列可以作为“待探索节点”列表。新发现的节点可以快速地加入队列尾部，而回溯时则可以从队列头部移除已探索节点，实现高效的节点管理。
4. 图形/网页布局：
   在处理图形用户界面（GUI）或网页布局时，双端队列可用于维护待布局元素的列表。新添加或修改的元素可以快速插入队列尾部，而布局引擎可以从队列前端开始处理元素，同时移除已布局完成的元素。
5. 文字处理软件的撤销/重做功能：
   双端队列可以用来存储编辑历史记录，撤销操作相当于从队首移除并恢复之前的状态，而重做操作则是从队尾添加最近撤销的更改重新应用。这样可以方便地实现多次撤销和重做的功能。
6. 事件处理：
   在事件驱动编程中，双端队列可以作为一个事件缓冲区，新发生的事件被添加到队尾，事件处理器则从队首取出并处理事件。这种结构有助于保证事件处理的顺序性和避免事件丢失。
7. 缓存管理：
   双端队列可以作为缓存结构的一部分，用于实现最近最少使用（LRU）缓存淘汰策略。新访问的项加入队尾，当缓存满时，最近最少使用的项（即队首的项）会被移除。
8. 排序算法辅助：
   在某些排序算法（如归并排序、拓扑排序等）中，双端队列可以作为中间数据结构，用于暂存待合并的子序列或待处理的节点，支持在序列两端进行快速的插入和提取操作。
9. 任务调度：
   在实时系统或操作系统中，双端队列可用于实现优先级调度。高优先级任务可以快速地插入队首，低优先级任务则在队尾等待。调度器按照优先级从队首取出任务执行。
10. 数据流处理：
    在处理数据流或流式计算时，双端队列可以作为缓冲区存储短暂的历史数据，便于进行窗口内计算或根据最近数据做出决策。

总之，双端队列因其独特的双端操作特性，适用于任何需要在数据结构两端高效插入和删除元素的场景，特别是在处理动态数据流、历史记录管理、任务调度和搜索算法中表现出色。

下面是双端队列的使用场景：

1. 滑动窗口最大值：给定一个数组 nums, 有一个大小为 k 的滑动窗口从数组的最左侧移动至数组的右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。这个问题可以使用双端队列来高效地找到每个窗口的最大值。
2. 接雨水问题：给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。这个问题的一个解法是使用两个双端队列，分别处理左右两侧的柱子，通过维护单调递减的队列来快速计算每个柱子上方能接到的雨水量。
3. 队列实现栈：使用两个双端队列来实现一个栈，使得栈的 push、pop 操作的时间复杂度都是 O(1)。
4. 回文判断：给定一个字符串，判断它是否为回文字符串。可以使用双端队列来存储字符串的前半部分，然后依次弹出队列中的字符与字符串的后半部分进行比较。
5. 合并区间：给出一个区间的集合，请合并所有重叠的区间。可以使用双端队列来存储区间，并按照区间的起始点进行排序，然后合并相邻的区间。
6. 最大子序和（Kadane算法）：虽然这个问题通常使用动态规划解决，但也可以使用双端队列来优化求解过程，尤其是在需要多次查询最大子序和的情况下。
7. 股票交易：模拟股票交易过程，包括买入、卖出和强制平仓等操作。双端队列可以用来维护一个买卖订单簿，快速匹配买卖订单。

这些算法题目中，双端队列可以帮助我们高效地管理数据，尤其是在需要快速访问序列的两端或者维护一个有序序列的时候。

比如说力扣上的滑动窗口的最大值：
用C++的话，可以这样写：

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        std::deque<int> dq;
        std::vector<int> result;

        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;
    }
};
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