JuliaでQueueを実装する

下心

「JuliaでStackを実装する」という記事で実装したstackは直前に追加した要素を取り出せるデータ構造でした。
しかし、古い要素を取り出すデータ構造も欲しいです。これがqueueと呼ばれる物です。

queueの操作(簡単な説明)

stackと同様、queueの構成要素は以下の3つです。

1. 要素の初期化
2. 要素の追加
3. 要素の削除
4. 空(カラ)かの確認

しかし、今回は要素の追加は配列の末尾に、要素の取り出しは配列の先頭から行うため、queueには配列と、その末尾の要素の位置情報の他に先頭の情報も必要です。

実装

まずは初期化です。

mutable struct queue{T}
   last :: Int 
   front :: Int 
   length :: Int
   data :: Array{T,1}
   function queue{T}(N::Int) where T
       new(1,1,N+1,Array{T,1}(undef,N+1))  #空か満杯かを区別するために、N+1個の要素を用意
   end 
end

構造体の構成要素はlast, front, length, dataです。ここで以下の2つの工夫があります。

1. lengthを定義
2. 配列を1つ大きく確保

2つとも後の実装を見ていただくと理由がわかりますが、端的にはそれぞれ

1. 要素の追加、削除を繰り返すとindexがどんどん増えるので、それを抑えるため
2. queueが空か満室かを区別するため

です。

次に、要素の追加です。ほとんどstackと同様ですが、今回はlastに配列の最後の要素の次のindexを記憶しています。
加えて、lastがどんどん大きくなることを防ぐために、last=lengthになったら次のindexを1に戻しています。

function push!(q :: queue, sth)
    q.data[q.last] = sth
    q.last = ifelse(q.last == q.length, 1 , q.last+1)
end

要素の削除もあまり変わりません。frontの要素を削除すると、次の要素の位置はfront+1となります。ここでも同様に、frontが大きくなりすぎないようにlengthで引き戻しています。

function pop!(q :: queue)
    if !isempty(q)
        tmp = q.data[q.front]
        q.front = ifelse(q.front == q.length, 1 , q.front+1)
        return tmp
    else
        error("queue is empty")
    end
end

最後はqueueが空かの確認です。これはlastがfrontと同じ位置かを調べれば良いです。

function isempty(q :: queue)
    q.last==q.front
end

動作確認

動作確認には以下のコードを用意しました。今回の実装の良いところはCharもqueueに追加できることです。

q = queue{Char}(10)

for s in 'A':'J'
    push!(q,s)
end

while !isempty(q)   
    println(pop!(q))
end

for s in 'A':'J'
    push!(q,s)
end

while !isempty(q)   
    println(pop!(q))
end

AtCoderなどで使う際には念のため確認してください。