隊列

本頁面介紹和隊列有關的數據結構及其應用。

引入

隊列（queue）是一種具有「先進入隊列的元素一定先出隊列」性質的表。由於該性質，隊列通常也被稱為先進先出（first in first out）表，簡稱 FIFO 表。

數組模擬隊列

通常用一個數組模擬一個隊列，用兩個變量標記隊列的首尾。

int q[SIZE], ql = 1, qr;

隊列操作對應的代碼如下：

• 插入元素：q[++qr] = x;
• 刪除元素：ql++;
• 訪問隊首：q[ql]
• 訪問隊尾：q[qr]
• 清空隊列：ql = 1; qr = 0;

雙棧模擬隊列

還有一種冷門的方法是使用兩個 棧 來模擬一個隊列。

這種方法使用兩個棧 F, S 模擬一個隊列，其中 F 是隊尾的棧，S 代表隊首的棧，支持 push（在隊尾插入），pop（在隊首彈出）操作：

• push：插入到棧 F 中。
• pop：如果 S 非空，讓 S 彈棧；否則把 F 的元素倒過來壓到 S 中（其實就是一個一個彈出插入，做完後是首尾顛倒的），然後再讓 S 彈棧。

容易證明，每個元素只會進入/轉移/彈出一次，均攤複雜度 \(O(1)\)。

C++ STL 中的隊列

C++ 在 STL 中提供了一個容器 std::queue，使用前需要先引入 <queue> 頭文件。

STL 中對 queue 的定義

// clang-format off
template<
    class T,
    class Container = std::deque<T>
> class queue;

T 為 queue 中要存儲的數據類型。

Container 為用於存儲元素的底層容器類型。這個容器必須提供通常語義的下列函數：

• back()
• front()
• push_back()
• pop_front()

STL 容器 std::deque 和 std::list 滿足這些要求。如果不指定，則默認使用 std::deque 作為底層容器。

STL 中的 queue 容器提供了一眾成員函數以供調用。其中較為常用的有：

• 元素訪問
  • q.front() 返回隊首元素
  • q.back() 返回隊尾元素
• 修改
  • q.push() 在隊尾插入元素
  • q.pop() 彈出隊首元素
• 容量
  • q.empty() 隊列是否為空
  • q.size() 返回隊列中元素的數量

此外，queue 還提供了一些運算符。較為常用的是使用賦值運算符 = 為 queue 賦值，示例：

std::queue<int> q1, q2;

// 向 q1 的隊尾插入 1
q1.push(1);

// 將 q1 賦值給 q2
q2 = q1;

// 輸出 q2 的隊首元素
std::cout << q2.front() << std::endl;
// 輸出: 1

特殊隊列

雙端隊列

雙端隊列是指一個可以在隊首/隊尾插入或刪除元素的隊列。相當於是棧與隊列功能的結合。具體地，雙端隊列支持的操作有 4 個：

• 在隊首插入一個元素
• 在隊尾插入一個元素
• 在隊首刪除一個元素
• 在隊尾刪除一個元素

數組模擬雙端隊列的方式與普通隊列相同。

C++ STL 中的雙端隊列

C++ 在 STL 中也提供了一個容器 std::deque，使用前需要先引入 <deque> 頭文件。

STL 中對 deque 的定義

// clang-format off
template<
    class T,
    class Allocator = std::allocator<T>
> class deque;

T 為 deque 中要存儲的數據類型。

Allocator 為分配器，此處不做過多説明，一般保持默認即可。

STL 中的 deque 容器提供了一眾成員函數以供調用。其中較為常用的有：

• 元素訪問
  • q.front() 返回隊首元素
  • q.back() 返回隊尾元素
• 修改
  • q.push_back() 在隊尾插入元素
  • q.pop_back() 彈出隊尾元素
  • q.push_front() 在隊首插入元素
  • q.pop_front() 彈出隊首元素
  • q.insert() 在指定位置前插入元素（傳入迭代器和元素）
  • q.erase() 刪除指定位置的元素（傳入迭代器）
• 容量
  • q.empty() 隊列是否為空
  • q.size() 返回隊列中元素的數量

此外，deque 還提供了一些運算符。其中較為常用的有：

• 使用賦值運算符 = 為 deque 賦值，類似 queue。
• 使用 [] 訪問元素，類似 vector。

<queue> 頭文件中還提供了優先隊列 std::priority_queue，因其與 堆 更為相似，在此不作過多介紹。

Python 中的雙端隊列

在 Python 中，雙端隊列的容器由 collections.deque 提供。

示例如下：

實現

from collections import deque

# 新建一個 deque，並初始化內容為 [1, 2, 3]
queue = deque([1, 2, 3])

# 在隊尾插入元素 4
queue.append(4)

# 在隊首插入元素 0
queue.appendleft(0)

# 訪問隊列
# >>> queue
# deque([0, 1, 2, 3, 4])

循環隊列

使用數組模擬隊列會導致一個問題：隨着時間的推移，整個隊列會向數組的尾部移動，一旦到達數組的最末端，即使數組的前端還有空閒位置，再進行入隊操作也會導致溢出（這種數組裏實際有空閒位置而發生了上溢的現象被稱為「假溢出」）。

解決假溢出的辦法是採用循環的方式來組織存放隊列元素的數組，即將數組下標為 0 的位置看做是最後一個位置的後繼。（數組下標為 x 的元素，它的後繼為 (x + 1) % SIZE）。這樣就形成了循環隊列。

例題

LOJ6515「雅禮集訓 2018 Day10」貪玩藍月

一個雙端隊列（deque），m 個事件：

1. 在前端插入 (w,v)
2. 在後端插入 (w,v)
3. 刪除前端的二元組
4. 刪除後端的二元組

5. 給定 l,r，在當前 deque 中選擇一個子集 S 使得 \(\sum_{(w,v)\in S}w\bmod p\in[l,r]\)，且最大化 \(\sum_{(w,v)\in S}v\).

   \(m\leq 5\times 10^4,p\leq 500\).

解題思路

每個二元組是有一段存活時間的，因此對時間建立線段樹，每個二元組做 log 個存活標記。因此我們要做的就是對每個詢問，求其到根節點的路徑上的標記的一個最優子集。顯然這個可以 DP 做。\(f[S,j]\) 表示選擇集合 S 中的物品餘數為 j 的最大價值。（其實實現的時侯是有序的，直接 f[i,j] 做）

一共有 \(O(m\log m)\) 個標記，因此這麼做的話複雜度是 \(O(mp\log m)\) 的。

---

這是一個在線算法比離線算法快的神奇題目。而且還比離線的好寫。

上述離線算法其實是略微小題大做的，因為如果把題目的 deque 改成直接維護一個集合的話（即隨機刪除集合內元素），那麼離線算法同樣適用。既然是 deque，不妨在數據結構上做點文章。

---

如果題目中維護的數據結構是一個棧呢？

直接 DP 即可。\(f[i,j]\) 表示前 i 個二元組，餘數為 j 時的最大價值。

\[ f[i,j]=\max(f[i-1,j],f[i-1,(j-w_i)\bmod p]+v_i) \]

妥妥的揹包啊。

刪除的時侯直接指針前移即可。這樣做的複雜度是 \(O(mp)\) 的。

---

如果題目中維護的數據結構是隊列？

有一種操作叫雙棧模擬隊列。這就是這個東西的用武之地。因為用棧是可以輕鬆維護 DP 過程的，而雙棧模擬隊列的複雜度是均攤 \(O(1)\) 的，因此，複雜度仍是 \(O(mp)\)。

---

回到原題，那麼 Deque 怎麼做？

類比推理，我們嘗試用棧模擬雙端隊列，於是似乎把維護隊列的方法擴展一下就可以了。但如果每次是全部轉移棧中的元素的話，單次操作複雜度很容易退化為 \(O(m)\)。

於是乎，神仙的想一想，我們可以丟一半過去啊。

這樣的複雜度其實均攤下來仍是常數級別。具體地説，丟一半指的是把一個棧靠近棧底的一半倒過來丟到另一個棧中。也就是説要手寫棧以支持這樣的操作。

---

似乎可以用 勢能分析法 證明。其實本蒟蒻有一個很仙的想法。我們考慮這個雙棧結構的整體複雜度。m 個事件，我們希望儘可能增加這個結構的複雜度。

首先，如果全是插入操作的話顯然是嚴格 \(\Theta(m)\) 的，因為插入的複雜度是 \(O(1)\) 的。

「丟一半」操作是在什麼時侯觸發的？當某一個棧為空又要求刪除元素的時侯。設另一個棧的元素個數是 \(O(k)\)，那麼丟一半的複雜度就是 \(O(k)\geq O(1)\) 的。因此我們要儘可能增加「丟一半」操作的次數。

為了增加丟一半的操作次數，必然需要不斷刪元素直到某一個棧為空。由於插入操作對增加複雜度是無意義的，因此我們不考慮插入操作。初始時有 m 個元素，假設全在一個棧中。則第一次丟一半的複雜度是 \(O(m)\) 的。然後兩個棧就各有 \(\frac{m}{2}\) 個元素。這時就需要 \(O(\frac{m}{2})\) 刪除其中一個棧，然後就又可以觸發一次複雜度為 \(O(\frac{m}{2})\) 的丟一半操作……

考慮這樣做的總複雜度。

\[ T(m)=2\cdot O(m)+T\left(\frac{m}{2}\right) \]

解得 \(T(m)=O(m)\)。

於是，總複雜度仍是 \(O(mp)\)。

---

在詢問的時侯，我們要處理的應該是「在兩個棧中選若干個元素的最大價值」的問題。因此要對棧頂的 DP 值做查詢，即兩個 \(f,g\) 對於詢問 [l,r] 的最大價值：

\[ \max_{0\leq i<p}\left\{f[i]+\max_{l\leq i+j\leq r}g_j\right\} \]

這個問題暴力做是 \(O(p^2)\) 的，不過一個妥妥的單調隊列可以做到 \(O(p)\)。

參考代碼

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
/******************heading******************/
const int M = 5e4 + 5, P = 505;  // 定义常数
int I, m, p;

int _(int d) { return (d + p) % p; }  // 用于取模

namespace DQ {                // 双栈模拟双端队列
pair<int, int> fr[M], bc[M];  // 二元组，详见题目3.4
int tf = 0, tb = 0;           // 一端的top,因为是双端队列所以有俩
int ff[M][P], fb[M][P];

void update(pair<int, int> *s, int f[][P], int i) {  // 用f[i-1]更新f[i]
  for (int j = 0; j <= (p - 1); j++) {
    f[i][j] = f[i - 1][j];
    if (~f[i - 1][_(j - s[i].first)])  // 按位取反
      f[i][j] = max(f[i][j], f[i - 1][_(j - s[i].first)] + s[i].second);
  }
}

// 以下两行代码表示push入队列，很好理解
void push_front(pair<int, int> x) { fr[++tf] = x, update(fr, ff, tf); }

void push_back(pair<int, int> x) { bc[++tb] = x, update(bc, fb, tb); }

// 以下两行代码表示从队列pop出元素
void pop_front() {
  if (tf) {
    --tf;
    return;
  }
  int mid = (tb + 1) / 2, top = tb;
  for (int i = mid; i >= 1; i--) push_front(bc[i]);
  tb = 0;
  for (int i = (mid + 1); i <= top; i++) push_back(bc[i]);
  --tf;
  // 上面的代码，逻辑和普通队列是一样的
}

void pop_back() {
  if (tb) {
    --tb;
    return;
  }
  int mid = (tf + 1) / 2, top = tf;
  for (int i = mid; i >= 1; i--) push_back(fr[i]);
  tf = 0;
  for (int i = (mid + 1); i <= top; i++) push_front(fr[i]);
  --tb;
  // 上面的代码，逻辑和普通队列是一样的
}

int q[M], ql, qr;  // 题目任务5要求的

int query(int l, int r) {
  const int *const f = ff[tf], *const g = fb[tb];
  int ans = -1;
  ql = 1, qr = 0;
  for (int i = (l - p + 1); i <= (r - p + 1); i++) {
    int x = g[_(i)];
    while (ql <= qr && g[q[qr]] <= x) --qr;
    q[++qr] = _(i);
  }
  for (int i = (p - 1); i >= 0; i--) {
    if (ql <= qr && ~f[i] && ~g[q[ql]]) ans = max(ans, f[i] + g[q[ql]]);
    // 删 l-i，加 r-i+1
    if (ql <= qr && _(l - i) == q[ql]) ++ql;
    int x = g[_(r - i + 1)];
    while (ql <= qr && g[q[qr]] <= x) --qr;
    q[++qr] = _(r - i + 1);
  }
  return ans;
}

void init() {
  for (int i = 1; i <= (P - 1); i++) ff[0][i] = fb[0][i] = -1;
}  // 初始化
}  // namespace DQ

int main() {
  DQ::init();
  scanf("%d%d%d", &I, &m, &p);
  for (int i = 1; i <= m; i++) {
    char op[5];
    int x, y;
    scanf("%s%d%d", op, &x, &y);
    if (op[0] == 'I' && op[1] == 'F')
      DQ::push_front(make_pair(_(x), y));
    else if (op[0] == 'I' && op[1] == 'G')
      DQ::push_back(make_pair(_(x), y));
    else if (op[0] == 'D' && op[1] == 'F')
      DQ::pop_front();
    else if (op[0] == 'D' && op[1] == 'G')
      DQ::pop_back();
    else
      printf("%d\n", DQ::query(x, y));
  }
  return 0;
}

/* example.in
0
11 10
QU 0 0
QU 1 9
IG 14 7
IF 3 5
QU 0 9
IG 1 8
DF
QU 0 4
IF 1 2
DG
QU 2 9
 */
/* example.out
0
-1
12
8
9
 */
/* LOJ:https://loj.ac/s/1149797*/

參考資料

1. std::queue - zh.cppreference.com
2. std::deque - zh.cppreference.com

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用