# 【5-8】雙向佇列 — deque

在現實生活中，有些排隊狀況不只是從「尾端加入、前端離開」，而是需要從兩端都能進出。例如：公車有前後門，都可以上下車，這時候就不能只用 `queue`，我們需要一個更靈活的資料結構：`deque`。

## deque
deque（double-ended queue）是 C++ 標準模板庫（STL）中的一種容器，具有以下特性：

* 支援從前端與尾端插入與移除元素
* 允許隨機訪問元素（類似 vector）

### 複雜度分析

| 操作 | 時間複雜度 | 空間複雜度 |
| ------------- | -------- | -------- |
| 插入（前端/尾端） | $O(1)$ | $O(n)$ |
| 移除（前端/尾端） | $O(1)$ | $O(n)$ |
| 隨機存取 | $O(1)$ | $O(n)$ |

### 宣告

deque<int> dq; // 宣告一個存放整數的 deque
deque<int> dq2 = {10, 20, 30}; // 宣告並初始化 deque

### Python對照

dq = deque()               # 建立空的 deque
dq2 = deque([10, 20, 30])  # 初始化

### 插入資料

dq.push_back(value);  // 將元素 value 插入到 deque 尾端
dq.push_front(value); // 將元素 value 插入到 deque 前端

### Python對照

dq.append(value)           # 插入到尾端（等同 push_back）
dq.appendleft(value)       # 插入到前端（等同 push_front）

### 移除資料

dq.pop_back();  // 移除 deque 尾端的元素
dq.pop_front(); // 移除 deque 前端的元素

### Python對照

dq.pop()                   # 移除尾端元素（等同 pop_back）
dq.popleft()               # 移除前端元素（等同 pop_front）

### 存取資料

dq.front(); // 取得 deque 前端的元素
dq.back();  // 取得 deque 尾端的元素
dq[i];      // 以隨機存取方式取得第 i 個元素（類似陣列或 vector）

### Python對照

dq[0]                      # 前端元素（等同 front()）
dq[-1]                     # 尾端元素（等同 back()）
dq[i]                      # 第 i 個元素（支援隨機存取）

### 其他操作

dq.size();   // 回傳整數，表示 deque 的大小
dq.empty();  // 回傳布林值，若 deque 為空則返回 true，否則返回 false
dq.clear();  // 移除所有元素，使 deque 變為空

### Python對照

len(dq)                    # 回傳 deque 的大小
not dq                     # 判斷是否為空
dq.clear()                 # 清空 deque

### 圖解程式

deque<int> dq; // 宣告一個存放整數的 deque
dq.push_front(10); // 將元素 10 插入到 deque 前端


dq.push_front(20); // 將元素 20 插入到 deque 前端


dq.push_back(30); // 將元素 30 插入到 deque 尾端


cout << dq.front() << " ";
dq.pop_front(); // 移除 dq 前端的元素

輸出結果：20


cout << dq.back() << " ";
dq.pop_back(); // 移除 dq 尾端的元素

輸出結果：30


cout << dq.front() << " ";
dq.pop_front(); // 移除 dq 前端的元素

輸出結果：10

---

聯絡方式：[e-mail]
最後編修時間：2025/07/12 子柚筆