queue.md

See http://www.erlang.org/doc/man/queue.html

A queue is modelled as a tuple with 2 lists.

iex(45)> q = :queue.new     
{[], []}

If you add to q queue, 1 item at a time, the right list will always contain the head and the left list the tail in reverse order.

iex(46)> q = :queue.in(1, q)
{[1], []}
iex(47)> q = :queue.in(2, q)
{[2], [1]}
iex(48)> q = :queue.in(3, q)
{[3, 2], [1]}
iex(49)> q = :queue.in(4, q)
{[4, 3, 2], [1]}
iex(50)> q = :queue.in(5, q)
{[5, 4, 3, 2], [1]}
iex(51)> :queue.out(q)
{{:value, 1}, {[5, 4, 3], [2]}}

That seems a bit pointless, but when we increase the size fun things happen.

iex(54)> q = 1..20 |> Enum.to_list |> :queue.from_list
{[20, 19, 18, 17, 16, 15, 14, 13, 12], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}
iex(55)> 

The queue is split. The left list is the last half, in reverse order; the second half is the first half in forward order.

Queue removal happen on the right list.

iex(55)> {_, q} = :queue.out(q)
{{:value, 1},
 {[20, 19, 18, 17, 16, 15, 14, 13, 12], [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}}
iex(56)> {_, q} = :queue.out(q)
{{:value, 2},
 {[20, 19, 18, 17, 16, 15, 14, 13, 12], [3, 4, 5, 6, 7, 8, 9, 10, 11]}}
iex(57)> {_, q} = :queue.out(q)
{{:value, 3},
 {[20, 19, 18, 17, 16, 15, 14, 13, 12], [4, 5, 6, 7, 8, 9, 10, 11]}}
iex(58)> {_, q} = :queue.out(q)
{{:value, 4}, {[20, 19, 18, 17, 16, 15, 14, 13, 12], [5, 6, 7, 8, 9, 10, 11]}}
iex(59)> {_, q} = :queue.out(q)
{{:value, 5}, {[20, 19, 18, 17, 16, 15, 14, 13, 12], [6, 7, 8, 9, 10, 11]}}
iex(60)> {_, q} = :queue.out(q)
{{:value, 6}, {[20, 19, 18, 17, 16, 15, 14, 13, 12], '\a\b\t\n\v'}}
iex(61)> {_, q} = :queue.out(q)
{{:value, 7}, {[20, 19, 18, 17, 16, 15, 14, 13, 12], '\b\t\n\v'}}
iex(62)> {_, q} = :queue.out(q)
{{:value, 8}, {[20, 19, 18, 17, 16, 15, 14, 13, 12], '\t\n\v'}}
iex(63)> {_, q} = :queue.out(q)
{{:value, 9}, {[20, 19, 18, 17, 16, 15, 14, 13, 12], '\n\v'}}
iex(64)> {_, q} = :queue.out(q)
{{:value, 10}, {[20, 19, 18, 17, 16, 15, 14, 13, 12], '\v'}}
iex(65)> {_, q} = :queue.out(q)
{{:value, 11}, {[20, 19, 18, 17, 16], [12, 13, 14, 15]}}

The queue is reordered when the right list is emptied.

Addition occurs on the left list.

iex(68)> q = 1..20 |> Enum.to_list |> :queue.from_list
{[20, 19, 18, 17, 16, 15, 14, 13, 12], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}
iex(69)> :queue.in(21, q)                             
{[21, 20, 19, 18, 17, 16, 15, 14, 13, 12], [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}

If we build up the queue gradually, the split only occurs when we remove something from the front (or possibly on other operations.)

iex(70)> q = 1..20 |> Enum.reduce(:queue.new, & :queue.in(&1, &2))
{[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2], [1]}
iex(71)> :queue.out(q)
{{:value, 1},
 {[20, 19, 18, 17, 16, 15, 14, 13, 12, 11], [2, 3, 4, 5, 6, 7, 8, 9, 10]}}

Update 1: realised that small queues don't really behave differently - it's a matter of how the queue was built.