🐩

JuliaでStackを実装する

2020/12/30に公開

下心

Atcoderでグラフ問題を解こうとしたのですが、juliaにはstackやqueueなどが実装されておらず、DataStructures.jlというパッケージになっています。
これらの構造が使えないのは競プロをする際に大きなデメリットになるので、実装しておこうと思いました。

stackはデータ構造の1つで、直近に追加したデータを取り出しやすい構造です。
stackの構成要素は以下の3つです。

このため、stackには配列データのほかに、配列の中の1番最後の要素のindexの情報が必要です。

まずは初期化です。

mutable struct stack{T}
   last :: Int
   data :: Array{T,1}
   function stack{T}(N::Int) where T
       new(0,Array{T,1}(undef,N))
   end 
end

つまり、構成要素のlastとdataを宣言した後、構造体と同じ名前の関数stackでlast=0、data=Array{T,1}(undef,N)と初期化しています。

次に、要素の追加です。以下の実装では、要素の追加で配列が1つ大きくなるのでlastも1つ大きくしています。その後、新しいlastの位置に要素を書き込んでいます。

function push!(s :: stack, sth)
    s.last+=1
    s.data[s.last] = sth
end

次は要素の削除です。実際にグラフ問題を解く際などは、削除した要素の情報を使って新しい操作(繋がっている頂点の情報を取得するなど)を行いたいです。
そこでこの関数の返り値は削除した要素の情報になるようにします。

function pop!(s :: stack)
    s.last-=1
    s.data[s.last+1]
end

最後はstackが空かの確認です。これはlastが0かを調べればいいので

function isempty(s :: stack)
    s.last==0
end

これから分かるように、常に配列の中には何か入っていますし、pop!をしたからと言ってデータは消えません。ただ、push!,pop!,isemptyの3つの関数の挙動は仕様通りです。