---
# System prepended metadata

title: 【5-8】雙向佇列 — deque

---

# 【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)$ |


### 宣告
```cpp
deque<int> dq; // 宣告一個存放整數的 deque
deque<int> dq2 = {10, 20, 30}; // 宣告並初始化 deque
```
### Python對照
```python
dq = deque()               # 建立空的 deque
dq2 = deque([10, 20, 30])  # 初始化
```
### 插入資料
```cpp
dq.push_back(value);  // 將元素 value 插入到 deque 尾端
dq.push_front(value); // 將元素 value 插入到 deque 前端
```
### Python對照
```python
dq.append(value)           # 插入到尾端（等同 push_back）
dq.appendleft(value)       # 插入到前端（等同 push_front）
```
### 移除資料
```cpp
dq.pop_back();  // 移除 deque 尾端的元素
dq.pop_front(); // 移除 deque 前端的元素
```
### Python對照
```python
dq.pop()                   # 移除尾端元素（等同 pop_back）
dq.popleft()               # 移除前端元素（等同 pop_front）
```
### 存取資料
```cpp
dq.front(); // 取得 deque 前端的元素
dq.back();  // 取得 deque 尾端的元素
dq[i];      // 以隨機存取方式取得第 i 個元素（類似陣列或 vector）
```
### Python對照
```python
dq[0]                      # 前端元素（等同 front()）
dq[-1]                     # 尾端元素（等同 back()）
dq[i]                      # 第 i 個元素（支援隨機存取）
```
### 其他操作
```cpp
dq.size();   // 回傳整數，表示 deque 的大小
dq.empty();  // 回傳布林值，若 deque 為空則返回 true，否則返回 false
dq.clear();  // 移除所有元素，使 deque 變為空
```
### Python對照
```python
len(dq)                    # 回傳 deque 的大小
not dq                     # 判斷是否為空
dq.clear()                 # 清空 deque
```
### 圖解程式
```cpp
deque<int> dq; // 宣告一個存放整數的 deque
dq.push_front(10); // 將元素 10 插入到 deque 前端
```
![螢幕擷取畫面 2025-06-08 193233](https://hackmd.io/_uploads/Sy0-rxQXeg.png)
```cpp
dq.push_front(20); // 將元素 20 插入到 deque 前端
```
![螢幕擷取畫面 2025-06-08 193248](https://hackmd.io/_uploads/B1mfHeQmel.png)
```cpp
dq.push_back(30); // 將元素 30 插入到 deque 尾端
```
![螢幕擷取畫面 2025-06-08 193302](https://hackmd.io/_uploads/SJFfBemXlx.png)
```cpp
cout << dq.front() << " ";
dq.pop_front(); // 移除 dq 前端的元素
```
```
輸出結果：20
```
![螢幕擷取畫面 2025-06-08 193314](https://hackmd.io/_uploads/SyAMSgX7ll.png)
```cpp
cout << dq.back() << " ";
dq.pop_back(); // 移除 dq 尾端的元素
```
```
輸出結果：30
```
![螢幕擷取畫面 2025-06-08 193233](https://hackmd.io/_uploads/BJGXSlmXlg.png)
```cpp
cout << dq.front() << " ";
dq.pop_front(); // 移除 dq 前端的元素
```
```
輸出結果：10
```

---

聯絡方式：codecodefunny@gmail.com
最後編修時間：2025/07/12 子柚筆