JuliaでStackを実装する

1 min read読了の目安(約1200字

下心

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

Stackとは(簡単な説明)

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

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

このため、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

つまり、構成要素のlastdataを宣言した後、構造体と同じ名前の関数stacklast=0data=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つの関数の挙動は仕様通りです。