在 C++ STL 中的deque::pop_front() 和 deque::pop_back() 应用

什么是 deque？

deque（双端队列）是 C++ STL 中的一种容器，可以实现双端插入和双端删除。它类似于 vector，但因为使用了链表而不是数组实现，所以其在两端插入和删除元素的速度更快，同时也不会造成元素迁移。因此，deque 在处理连续插入和删除元素的场景下有更好的性能表现。

使用 deque

使用 deque 非常简单，可以直接使用 STL 提供的操作符号，比如 []、size()、push_front()、pop_back() 等等。下面是一个展示如何使用 deque 的示例代码：

#include <deque>
#include <iostream>

int main() {
    std::deque<int> dq;
    dq.push_back(1);
    dq.push_front(2);
    dq.push_back(3);

    std::cout << "deque size: " << dq.size() << std::endl;
    std::cout << "deque front: " << dq.front() << std::endl;
    std::cout << "deque back: " << dq.back() << std::endl;

    dq.pop_front();
    dq.pop_back();
    std::cout << "deque size after pop: " << dq.size() << std::endl;

    for (auto& i : dq) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

上面的代码定义了一个 int 类型的 deque，先在头部插入了一个值为 2 的元素，再在尾部插入了 1 和 3。我们可以通过 deque 的操作函数获取 deque 大小、头部值和尾部值。然后对 deque 执行了 pop_front() 和 pop_back() 操作，最后遍历 deque 打印其所有值。

deque::pop_front() 和 deque::pop_back()

pop_front() 和 pop_back() 是 deque 容器定义的操作，分别用于删除 deque 头部和尾部的元素。它们的参数为空，因为它们总是删除容器当前头部和尾部的元素。

下面是一个演示 pop_front() 和 pop_back() 的示例代码：

#include <deque>
#include <iostream>

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

    std::cout << "deque size: " << dq.size() << std::endl;
    std::cout << "deque front: " << dq.front() << std::endl;
    std::cout << "deque back: " << dq.back() << std::endl;

    dq.pop_front();
    dq.pop_back();
    std::cout << "deque size after pop: " << dq.size() << std::endl;

    for (auto& i : dq) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

上面的代码中，我们定义了一个包含 5 个元素的 deque，然后使用 pop_front() 和 pop_back() 分别删除其头部和尾部元素。注意，当我们执行 pop_front() 和 pop_back() 操作后，deque 的容量并没有改变，只有元素个数减少了。

deque::pop_front() 和 pop_back() 的时间复杂度

deque::pop_front() 和 pop_back() 的时间复杂度为 O(1)，因为 deque 通过双向链表实现的，可以直接访问到头节点和尾节点，所以删除元素的操作时间是固定的，与 deque 的大小无关。

deque::pop_front() 和 pop_back() 的使用场景

deque::pop_front() 和 pop_back() 的使用场景很多，例如在动态变化的队列中，deque::pop_front() 可以非常方便的弹出队头元素。此外，在对数据滑动窗口求解时，deque 可以实现更高效的计算。下面举一个实际应用场景的例子，使用 deque::pop_front() 和 pop_back() 处理滑动窗口求解问题：

假设我们有一个长度为 n 的数组 A 和一个正整数 k，我们要求 A 的所有长度为 k 的子数组中的最大值。可以使用滑动窗口的方式，每次窗口移动一格，然后更新滑动窗口内的最大值。因为滑动窗口是可以重叠的，所以我们可以用 deque 记录滑动窗口内的最大值和下标。

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

std::vector<int> maxSlidingWindow(std::vector<int>& nums, int k) {
    std::vector<int> res{};
    std::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) {
            res.push_back(nums[dq.front()]);
        }
    }

    return res;
}

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

    std::vector<int> res = maxSlidingWindow(A, k);

    for (auto& i : res) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

上面的代码中，我们定义了一个 maxSlidingWindow() 函数，用于处理滑动窗口中的最大值。在每次滑动窗口移动时，我们都先判断 deque 中头部元素是否已经不在滑动窗口范围内，然后再将当前元素与 deque 的末尾元素比较，如果当前元素更大，则将末尾元素出队，不断重复该操作，直到 deque 中所有元素都小于等于当前元素。接着，将当前元素入队，最后判断滑动窗口是否已经扫描完毕，如果是，则将 deque 头部元素（即最大值的下标）对应的元素加入结果数组 res 中。

结论

deque::pop_front() 和 pop_back() 是 C++ STL 提供的用于删除 deque 头部和尾部元素的函数。它们的时间复杂度是 O(1)，因为 deque 内部利用双向链表实现，可以直接访问头节点和尾节点，所以删除元素的操作时间是固定的，与 deque 的大小无关。deque::pop_front() 和 pop_back() 可以广泛应用于动态变化的队列中，例如在滑动窗口求解问题中，使用 deque 记录滑动窗口内的最大值和下标。