# 書き換え可能なデータ構造を使ったキュー

いつもの如くまずは型の定義。

```# type 'a mlist = MNil | MCons of 'a * 'a mlist ref;;
type 'a mlist = MNil | MCons of 'a * 'a mlist ref
# type 'a queue = {mutable head : 'a mlist; mutable tail : 'a mlist};;
type 'a queue = { mutable head : 'a mlist; mutable tail : 'a mlist; }
```

キューを作る関数の定義。

```# let create () = {head = MNil; tail = MNil};;
val create : unit -> 'a queue = <fun>
# let q : int queue = create ();;
val q : int queue = {head = MNil; tail = MNil}
```

キューに要素を加える関数の定義。

```# let add a = function
{head = MNil; tail = MNil} as q ->
let c = MCons (a, ref MNil) in
q.head <- c; q.tail <- c
| {tail = MCons (_, next)} as q ->
let c = MCons (a, ref MNil) in
next := c; q.tail <- c
| _ -> failwith "enqueue: input queue broken";;
val add : 'a -> 'a queue -> unit = <fun>
- : unit = ()
# q;;
- : int queue =
MCons (1,
{contents = MCons (2, {contents = MCons (3, {contents = MNil})})});
tail = MCons (3, {contents = MNil})}
```

```# let peek = function
{head = MNil; tail = MNil} -> failwith "peek: queue is empty"
| {head = MCons(a, _)} -> a
| _ -> failwith "peek: queue is empty";;
val peek : 'a queue -> 'a = <fun>
# peek q;;
- : int = 1
```

```# let take = function
{head = MNil; tail = MNil} -> failwith "take: queue is empty"
| {head = MCons (a, next)} as q when !next = MNil ->
q.head <- MNil; q.tail <- MNil; a
| {head = MCons (a, next)} as q -> q.head <- !next; a
| _ -> failwith "take: queue is broken";;
val take : 'a queue -> 'a = <fun>
```