【Erlang】queueモジュールのデータ構造

Erlang の標準ライブラリである`queue`モジュールについて解説する。

https://erlang.org/doc/man/queue.html

# Deque

公式ドキュメントによると、`queue`モジュールはDequeである。ここではDequeについて説明する。

Deque (Double enabled queue)とは、要素の追加、削除をQueueの先頭と末尾の両方で行えるデータ構造である。
通常のQueueに対する操作の in （rearへの要素追加） / out （frontからの要素削除） に加え、in_r （frontへの要素追加） / out_r （rearからの要素削除）が提供される。 ※操作名は、Erlangの`queue`モジュール内のAPI名、用語を利用して説明する。
画像内では、通常のQueueに対する操作が青、Dequeで提供される操作が赤で示される。

![名称未設定-Page-2 (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/480312/30478e68-8c5d-18b2-a467-d4301edc46be.png)


# `queue`モジュール

## Queueの作成

`queue`モジュールでは、二つのリストを用いてQueueのデータ構造を表現している。

```erlang
1> Q0 = queue:new().
{[],[]}
```

二つのリストのHeadは、Queueの両端を表している。
**タプルの１番目の要素がrear、２番目の要素がfrontを表している。**
また、Erlangのリストは連結リスト構造なので、先頭要素へのアクセスがO(1), 末尾要素へのアクセスがO(n)で行われる。

参考画像のように、元々のQueueの図をググッと曲げた形だと考えると、Erlangにおけるリストでの実装イメージがつきやすい。

![名称未設定-Page-3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/480312/5481a4bb-131c-ea93-86f9-cbb0b236aef6.png)


## 要素の追加

in

```erlang
2> Q1 = queue:in(1, Q0).
{[1],[]}
3> Q2 = queue:in(2, Q1).
{[2],[1]}
4> Q3 = queue:in(3, Q2).
{[3,2],[1]}
5> Q4 = queue:in(4, Q3).
{[4,3,2],[1]}
```

in_r

```erlang
6> Q1R = queue:in_r(1, Q0).
{[],[1]}
7> Q2R = queue:in_r(2, Q1R).
{[1],[2]}
8> Q3R = queue:in_r(3, Q2R).
{[1],[3,2]}
9> Q4R = queue:in_r(4, Q3R).
{[1],[4,3,2]}
```

## 要素の削除

削除時に片側のリストから要素が無くなる場合、もう片方のリストから要素の半分を提供するような実装になっていた。
（本記事では、この操作をバランスと呼ぶ）。

out

```erlang

1> Q0 = {[1,2,3,4,5], [6,7,8]}.     
{[1,2,3,4,5],[6,7,8]}
2> {{value, _}, Q1} = queue:out(Q0). % frontの先頭要素が取り出されているだけなのでO(1)
{{value,6},{[1,2,3,4,5],[7,8]}}
3> {{value, _}, Q2} = queue:out(Q1). % frontの先頭要素が取り出されているだけなのでO(1)
{{value,7},{[1,2,3,4,5],"\b"}}
4> {{value, _}, Q3} = queue:out(Q2). % frontの先頭要素が取り出され、frontとrearがバランスされるためO(n)
{{value,8},{[1,2,3],[5,4]}}
```

out_r

```erlang
5> Q0R = {[1,2,3], [4,5,6,7,8]}.    
{[1,2,3],[4,5,6,7,8]}
6> {{value, _}, Q1R} = queue:out_r(Q0R). % rearの先頭要素が取り出されているだけなのでO(1)
{{value,1},{[2,3],[4,5,6,7,8]}}
7> {{value, _}, Q2R} = queue:out_r(Q1R). % rearの先頭要素が取り出されているだけなのでO(1)
{{value,2},{[3],[4,5,6,7,8]}}
8> {{value, _}, Q3R} = queue:out_r(Q2R). % rearの先頭要素が取り出され、frontとrearがバランスされるためO(n)
{{value,3},{[8,7],[4,5,6]}}
```

## 操作の計算量

| 操作 | 条件 | 計算量 |
|:-|:-|:-|
|in|常時|O(1)|
|in_r|常時|O(1)|
|out|front+rearの要素数が3以上かつrearの要素数が1以下の時|O(n)
|out|それ以外の時|O(1)|
|out_r|front+rearの要素数が3以上かつfrontの要素数が1以下の時|O(n)
|out_r|それ以外の時|O(1)|

なお、削除操作のO(n)となるバランス操作は、頻発することがないように実装されていた。

```erlang
15> lists:foldl(
15>     fun(_, Acc) ->
15>         {{value, V}, Q} = queue:out(Acc),
15>         io:format("V: ~p, Q: ~p~n", [V, Q]),
15>         Q
15>     end,
15>    {lists:seq(1,20), [21]},
15>    lists:seq(1, 20)
15> ).
V: 21, Q: {[1,2,3,4,5,6,7,8,9,10,11],[20,19,18,17,16,15,14,13,12]} % バランス
V: 20, Q: {[1,2,3,4,5,6,7,8,9,10,11],[19,18,17,16,15,14,13,12]}
V: 19, Q: {[1,2,3,4,5,6,7,8,9,10,11],[18,17,16,15,14,13,12]}
V: 18, Q: {[1,2,3,4,5,6,7,8,9,10,11],[17,16,15,14,13,12]}
V: 17, Q: {[1,2,3,4,5,6,7,8,9,10,11],[16,15,14,13,12]}
V: 16, Q: {[1,2,3,4,5,6,7,8,9,10,11],[15,14,13,12]}
V: 15, Q: {[1,2,3,4,5,6,7,8,9,10,11],[14,13,12]}
V: 14, Q: {[1,2,3,4,5,6,7,8,9,10,11],"\r\f"}
V: 13, Q: {[1,2,3,4,5,6,7,8,9,10,11],"\f"}
V: 12, Q: {[1,2,3,4,5,6],[11,10,9,8,7]} % バランス
V: 11, Q: {[1,2,3,4,5,6],[10,9,8,7]}
V: 10, Q: {[1,2,3,4,5,6],[9,8,7]}
V: 9, Q: {[1,2,3,4,5,6],[8,7]}
V: 8, Q: {[1,2,3,4,5,6],[7]}
V: 7, Q: {[1,2,3,4],[6,5]}
V: 6, Q: {[1,2,3,4],[5]}
V: 5, Q: {[1,2,3],[4]} % バランス
V: 4, Q: {[1,2],[3]}
V: 3, Q: {[1],[2]} % バランス
V: 2, Q: {[],[1]}
{[],[1]}
```


# 参考

- https://programming-place.net/ppp/contents/algorithm/data_struct/011.html#deque
- https://note.nkmk.me/python-collections-deque/
- https://github.com/erlang/otp/blob/master/lib/stdlib/src/queue.erl