PythonistaのためのC++記法入門: それC++ではどう書くの4 ~queue / stack / deque~


[PythonistaのためのC++記法入門: それC++ではどう書くの3](https://qiita.com/nctp/items/919eb1464de6e8684da5)の続き。今回は競プロでよく用いられるようなデータ構造。

# queue / stack / deque

基本は`push(値)`してデータを格納、`pop()`でデータを取り出す。
Pythonとは異なり`pop()`した値を**他の変数に代入することはできない**（`auto val = q.pop();`とはできない）。
アクセスできる位置に制約がある代わりに非常に高速なアクセスが可能。

FIFO型かLIFO型かによって*先頭*の定義が変わり、それにより先頭へのアクセス方法が`front()`もしくは`top()`となる。この先頭要素へのアクセスが非常に高速であるのがこれらのコンテナの特徴。`Deque`は両端および*中間要素へのアクセスが可能*だが中間要素へのアクセスは高速ではない。

PythonではQueue / Stack単体に該当するものはなく、これらをまとめたDequeが利用できる。そのためここではまずC++での利用法から書いていく。

## Queue

FIFO(First In First Out)型のデータ構造。最初に`push`した値から順に`pop`される。

### C++ではこう書く

`queue<型> 変数名`で宣言でき、ここで指定したデータ型を格納する`queue`が作られる。
`front()`で`queue`における先頭、すなわち最も古く`push`されてまだ残っている要素へのアクセスが可能であり、`pop()`でその要素が`queue`から削除される。
`queue`の先頭からみた反対方向の末尾、すなわち最後に`push`された要素へも`back()`でアクセスが可能。しかしその要素を削除することはできない。

```cpp
// 宣言
queue<int> q;

// 要素の追加
q.push(0);
q.push(1);

// 先頭要素へのアクセス
cout << q.front() << endl;  // 0 が出力される

// 末尾要素へのアクセス
cout << q.back() << endl;  // 1 が出力される

// 要素の削除
q.pop();  // queueから0が削除される
cout << q.front() << endl;  // 1 が出力される

// 要素数チェック
cout << q.size() << endl; //  1 が出力される

// queueが空であるかのチェック
if (q.empty()){cout << "Empty" << endl;}
else {cout << "Not Empty" << endl;} // Not Emptyが出力される
```

## priority_queue

それまでに格納した値のうち最大のものを優先的に取り出す`queue`が`priority_queue`である。使い方は`queue`とほぼ同じだが、最大値を取り出すときに`top()`を使うことに注意。`front()`は使えない。

### C++ではこう書く

```cpp
// 宣言
priority_queue<int> pq;

// 値を格納していく
pq.push(10);
pq.push(1);
pq.push(1000);
pq.push(40);

// topは現時点での最大値を返す
cout << pq.top() << endl; // 1000が出力される

pq.pop();  // 最大値である1000が削除される
cout << pq.top() << endl; // 40が出力される
```

## Stack

LIFO(Last In First Out)型のデータ構造。**最後に**`push`した値から`pop`される。

### C++ではこう書く

`stack<型> 変数名`で宣言でき、ここで指定したデータ型を格納する`stack`が作られる。`stack`における*先頭*とは最後に`push`した要素であり、`queue`とは反対となるので注意。
`top()`で先頭要素にアクセスできる。`queue`とは異なり末尾要素（この場合最も古くpushされた要素）にアクセスする方法はない。

```cpp
// 宣言
stack<string> stk;

// 要素の追加
stk.push("John");
stk.push("Mary");

// 要素へのアクセス（先頭、つまり最後にpushされた要素へのアクセス）
cout << stk.top() << endl;  // Mary が出力される

// 要素の削除
stk.pop();  // 最後にpushされたMaryが削除される
cout << stk.top() << endl;  // John が出力される

// 要素数チェック
cout << stk.size() << endl; //  1 が出力される

// queueが空であるかのチェック
if (stk.empty()){cout << "Empty" << endl;}
else {cout << "Not Empty" << endl;} // Not Emptyが出力される
```

## Deque

Double-ended queueの略。`queue`と`stack`を合わせたようなもの。両端、すなわち先頭と末尾へのアクセスが高速であるコンテナ。インデックスを利用した中間の要素へのアクセスも可能だが、速度面で`vector`に劣る。

### C++ではこう書く

`deque<型> 変数名`で宣言でき、ここで指定したデータ型を格納する`deque`が作られる。

`push_front(値)` / `push_back(値)`で値を先頭 / 末尾へ格納し、
`pop_front()` / `pop_back()`で値を先頭 / 末尾から削除、
`front()` / `back()`で先頭 / 末尾の値へアクセス、
さらに`at(i)`または`変数名[i]`で`i`番目の値へアクセスする。`at(i)`で存在しない要素へアクセスしようとするとエラーとなる。
`insert()`で任意の位置への要素の追加が可能だが、`list`の`insert`と比べると実行速度は遅い。

```cpp
// 宣言
deque<string> deq;

// 要素の追加
deq.push_front("John");  // ["John"]
deq.push_back("Mary");  // ["John", "Mary"]
deq.push_front("Helen");  // ["Helen", "John", "Mary"]

// 末尾要素へのアクセス（backmost要素へのアクセス）
cout << deq.back() << endl;  // Mary が出力される

// 先頭要素へのアクセス（frontmost要素へのアクセス）
cout << deq.front() << endl;  // Helen が出力される


// 要素の削除
deq.pop_front();  // ["John", "Mary"]
cout << deq.front() << endl;  // John が出力される
deq.pop_back();  // ["John"]
cout << deq.back() << endl;  // John が出力される

// インデックスによるアクセス
cout << deq.at(0) << endl;  // John が出力される
cout << deq[0] << endl;  // John が出力される

deq.at(0) = "JOHN";  // 書き換えも可能
cout << deq.at(0) << endl;  // JOHN が出力される

// 要素数チェック
cout << deq.size() << endl; //  1 が出力される

// queueが空であるかのチェック
if (deq.empty()){cout << "Empty" << endl;}
else {cout << "Not Empty" << endl;} // Not Emptyが出力される
```

### Pythonではこう書いた

Pythonでも`collections.deque`で実装されている（が個人的に利用したことはない）。

利用可能なメソッドの名前がC++とは微妙に異なる。
`appendleft(値)` / `append(値)`で値を先頭 / 末尾へ格納し、
`popleft()` / `pop()`で値を先頭 / 末尾から削除、
`変数名[0]` / `変数名[-1]`で先頭 / 末尾の値へアクセス、
`変数名[i]`で`i`番目の値へアクセスする。存在しない要素へアクセスしようとするとエラーとなる。
他にも値が何番目に格納されているかを返す`index`や格納順をずらす`rotate`などのメソッドが用意されている。

```python
from collections import deque
# 定義
deq = deque()

# 要素の追加
deq.append("John")  # deque(['John'])
deq.append("Mary")  # deque(['John', 'Mary'])
deq.appendleft("Helen")  # deque(['Helen', 'John', 'Mary'])

# 末尾要素へのアクセス（backmost要素へのアクセス）
deq[-1]  # 'Mary' が出力される

# 先頭要素へのアクセス（frontmost要素へのアクセス）
deq[0]  # 'Helen' が出力される

# 要素の削除
_ = deq.popleft()  # deque(['John', 'Mary'])
deq[0]  # 'John' が出力される
_ = deq.pop()  # deque(['John'])
deq[-1]  # 'John' が出力される

# インデックスによるアクセス
deq[0]  # 'John' が出力される

# 要素数チェック
len(deq) #  1 が出力される

# queueが空であるかのチェック
if len(deq) == 0:
    print("Empty")
else:
    print("Not Empty")
# Not Emptyが出力される
```

#### まとめ

|  |  C++ | Python |
| --- | --- | --- |
| 宣言 / 定義 | deque<型> deq; | deq = collections.deque() |
| 先頭に要素を追加 | deq.push_front(); | deq.appendleft() |
| 先頭の要素を削除 | deq.pop_front(); | deq.popleft() |
| 先頭要素へのアクセス | deq.front(); | deq[0] |
| 末尾に要素を追加 | deq.push_back(); | deq.append() |
| 末尾の要素を削除 | deq.pop_back(); | deq.pop() |
| 末尾要素へのアクセス | deq.back(); | deq[-1] |
| 任意要素へのアクセス(1) [^1] | deq.at(i); | deq[i] |
| 任意要素へのアクセス(2) | deq[i]; [^2] | 同上 |
| 要素を任意位置に挿入 [^3] | deq.insert(位置, 要素);	| deq.insert(位置, 要素) |
| 任意要素の削除 | deq.erase(位置); [^4] | deq.remove(要素) |
| 要素数を取得 | deq.size(); | len(deq) |
| 全要素を削除 | deq.clear(); | deq.clear() |

[^1]: C++もPythonも境界チェックを行う。すなわち、範囲外にアクセスしたときにC++では`out_of_range`例外、Pythonでは`IndexError`例外が投げられる
[^2]: 境界チェックは行われず、範囲外のインデックスを指定しても動く可能性がある
[^3]: C++ではイテレータ / Pythonではインデックスを位置引数として受け取る
[^4]: 位置引数としてイテレータを受け取り、その位置の要素を削除する