スタックとキュー

概要

スタック および キュー は、コンピュータ サイエンスにおける一般的なデータ構造で、要素を追加および削除する順序を指定します。スタックとキューを使用して、データを操作する順序を制御することができます。

• スタック：積み上げられた状態 (スタック) の上から読む本を選択するなど、先入れ後出し (FIRO) の順序で要素を挿入および削除するコンテナ。

• キュー：行列にならんで食事を待つ顧客の処理など、先入れ先出し (FIFO) の順序で要素を挿入したり削除したりするコンテナ。

スタックとキューの基本的なコードは似ているものの、それぞれに高速で効率的かつ直感的な操作性を実現するために活用できる、重要な違いと強みがあります。

スタック

スタックは、積み重ねた状態 (スタック) のパンケーキと考えることができます。朝食レストランで、ウェイターがエンドレスにスタックされるパンケーキをあなたに提供してくれるとしましょう。礼儀正しさを尊重するあなたは、スタックの一番上にあるパンケーキを一度に 1 枚のみ食べることにしました。あなたはウェイターに頼んで新しいパンケーキをスタックの一番上に プッシュ (追加) してもらうことができます。お腹が空いたらスタックの一番上のパンケーキを自分のお皿に ポップ (取り出し) して食べることができます。スタックの真ん中にある特定のパンケーキを食べたい場合は、目的のパンケーキにたどり着くまで上から食べ続けなければなりません。最初に追加されたパンケーキは、あなたがスタックから取り出す最後のパンケーキになります。このスタックは FILO、つまり先入れ後出しのデータ構造です。

使用すべきケース

スタックは、バックトラッキングが必要な場合や、どの順番でイベントを実行したかを記憶しておく機能が必要な場合に役立ちます。これはアンドゥ機能、一連のイベント、連続する選択などが考えられます。たとえば、枝分かれする道で構成される迷路を解かなければならないロボットがあるとします。ロボットは迷路の分岐に遭遇すると道を選択し、その選択をスタックにプッシュします。行き止まりに遭遇すると、ロボットはスタックの内容をバックトラッキング (撤回) します。つまり、新たな経路が見つかるまで、選択をポップ (取り出し) します。

Verse での実装

Verse API にはスタックの組み込みの実装はないものの、自分で作成することができます。

スタックの要素は、配列や 連結リスト などの任意の順序付きのデータ構造を使用して表すことができます。この例では、スタックの一番上に簡単にアクセスできるため、配列を使用します。

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}
Copy full snippet

stack<public>(t:type) := class: Elements<internal>:[]t = array{}

Elements 配列は、t 型のスタックのオブジェクトを格納します。つまり、int、float、stack など、どのような型の要素でもスタックを初期化できます。スタック クラスの引数として type を使用しているのは、パラメトリック型 (parametric-types-in-verse) の一例です。

まず、ヘルパー関数をいくつか定義しましょう。スタックの一番上から要素を Push() および Pop() するには、スタックの一番上がどこであるかを把握している必要があります。そのためには、3 つの関数 Size()、IsEmpty()、および Peek() が必要です。

# スタックのサイズを返します。
    Size<public>()<transacts>:int=
        Elements.Length

    # スタックが空の場合は、成功します。
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # スタックの一番上の要素を返します。
    Peek<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]
Copy full snippet

# スタックのサイズを返します。 Size<public>()<transacts>:int= Elements.Length # スタックが空の場合は、成功します。 IsEmpty<public>()<decides><transacts>:void= Size() = 0 # スタックの一番上の要素を返します。 Peek<public>()<decides><transacts>:t= Elements[Elements.Length - 1]

Size() 関数は単に Elements 配列の Length を返します。IsEmpty() 関数は Size() 関数を呼び出し、<transacts> 指定子を持っています、つまり、Size() が 0 に等しくない場合は、失敗します。

Peek() 関数は、要素配列の一番上 (Length - 1) のインデックスにある要素を返します。この配列が空の場合に配列へのアクセスが失敗する可能性があるため、この関数は <decides><transacts> 指定子を持っています。

スタックをインスタンス化するには、コンストラクタ 関数を使用することができます。コンストラクタは、関連付けられているクラスのインスタンスを作成する特殊な関数です。コンストラクタはオブジェクトに初期値を設定し、Elements の値にアクセスして、要素の初期配列に割り当てることができます。

# 要素の初期配列 InitialElements からスタックを作成して返します。
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements
Copy full snippet

# 要素の初期配列 InitialElements からスタックを作成して返します。 CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t): Elements := InitialElements

プッシュおよびポップ

スタックに要素を追加したり、スタックから要素を削除するには、新しい要素をスタックの一番上に push するか、スタックの一番上から新しい要素 pop する必要があります。

# NewElement を一番上とする新しいスタックを返すことによって、
# NewElement をスタックの一番上に追加します。
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# スタックの一番上の要素を削除し、
# 一番上の要素が削除された新しいスタックと削除された要素の両方で構成されるタプルを返します。
Pop<public>()<decides><transacts>:tuple(stack(t),t)=
    FirstElement := Peek[]
    (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)
Copy full snippet

# NewElement を一番上とする新しいスタックを返すことによって、 # NewElement をスタックの一番上に追加します。 Push<public>(NewElement:t):stack(t)= stack(t){Elements := Elements + array{NewElement}} # スタックの一番上の要素を削除し、 # 一番上の要素が削除された新しいスタックと削除された要素の両方で構成されるタプルを返します。 Pop<public>()<decides><transacts>:tuple(stack(t),t)= FirstElement := Peek[] (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

Push() 関数は、スタックの一番上に配置したい要素を受け取り、その要素を一番上に持つ新しいスタックを返します。現在のスタックを変更するのではなく、新しいスタックを返すことは、関数型プログラミング の一例であり、副次的エフェクト のリスクを減らすことができます。

Pop() 関数を実装するには、まず Peek() を使用してスタックの一番上にある要素を見つける必要があります。次に、(RemoveElement[] 関数を使用して) 一番上にある要素を削除し、その要素を含まない新しいスタックを返す必要があります。タプルを使用すると、新しいスタックと削除した要素の両方を同時に返すことができます。配列へのアクセスと Peek() の呼び出しは失敗する可能性がある式であるため、Pop() は <decides><transacts> 指定子を持っている必要があります。

完全なコード

以下は、スタック クラスの完全なコードです。

stack<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # NewElement を一番上とする新しいスタックを返すことによって、
    # NewElement をスタックの一番上に追加します。
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # スタックの一番上の要素を削除し、
    # 一番上の要素が削除された新しいスタックと削除された要素の両方で構成されるタプルを返します。
    Pop<public>()<decides><transacts>:tuple(stack(t),t)=
        FirstElement := Peek[]
        (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement)

    # スタックのサイズを返します。
    Size<public>()<transacts>:int=
        Elements.Length

    # スタックが空の場合は、成功します。
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # スタックの一番上の要素を返します。
    Peek<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]
Copy full snippet

stack<public>(t:type) := class: Elements<internal>:[]t = array{} # NewElement を一番上とする新しいスタックを返すことによって、 # NewElement をスタックの一番上に追加します。 Push<public>(NewElement:t):stack(t)= stack(t){Elements := Elements + array{NewElement}} # スタックの一番上の要素を削除し、 # 一番上の要素が削除された新しいスタックと削除された要素の両方で構成されるタプルを返します。 Pop<public>()<decides><transacts>:tuple(stack(t),t)= FirstElement := Peek[] (stack(t){Elements := Elements.RemoveElement[Elements.Length - 1]}, FirstElement) # スタックのサイズを返します。 Size<public>()<transacts>:int= Elements.Length # スタックが空の場合は、成功します。 IsEmpty<public>()<decides><transacts>:void= Size() = 0 # スタックの一番上の要素を返します。 Peek<public>()<decides><transacts>:t= Elements[Elements.Length - 1]

キュー

キューは回転寿司のベルト コンベアのようなものと考えることができます。回転寿司店では、ベルト コンベアで一度に一皿ずつ、注文した順番で寿司が運ばれてきます。あなたは列の前にある皿を デキュー (取り出し) して、手に取って食べることができますが、一度に手に取ることができるのは一皿だけです。新しい皿を注文したいときは、店員に頼んで列の後ろに皿を エンキュー (追加) してもらいます。列に他の寿司の皿がすでに並んでいる場合は、列の後ろにある目的の皿に到達するまで、列の前にある皿の寿司を食べ続ける必要があります。つまり、最初に追加された寿司の皿が、最初に取り出されます。これがキュー (FIFO)、つまり先入れ先出しのデータ構造です。

使用すべきケース

キューは、データがいつ到着するかに基づいて処理する必要がある場合に役立ちます。これは、ドライブスルーでの接客、コールセンターの通話待ちの処理、インタビューでの選手への一連の質問の処理などが考えられます。たとえば、プレイヤーがタスクを実行したり、一度に 1 つずつ体験を行う間、プレイヤーのための待機ルームを作成する必要がある場合、キューを使用すると、プレイヤーがいつ到着したかに基づいて先着順で順序付けすることができます。

Verse での実装

Verse API にはキューの組み込みの実装はないものの、自分で作成することができます。

スタックと同様に、キューの要素は、配列や連結リストなどの任意の順序付きのデータ構造を使用して表すことができます。この例では、キューの前と後両方に簡単にアクセスできるため、配列を使用します。連結リストを使用したキューの実装については、「このコード スニペット」を確認してください。

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}
Copy full snippet

queue<public>(t:type) := class: Elements<internal>:[]t = array{}

Elements 配列は、t 型のキューのオブジェクトを格納します。つまり、int、float、queue など、どのような型の要素でもキューを初期化できます。キュー クラスの引数として type を使用するのは、パラメトリック型 (parametric-types-in-verse) の一例です。

スタックと同様に、キューにもいくつかのヘルパー関数が必要です。Enqueue() および Dequeue() を実行するためには、キューの前と後ろの位置を把握しておく必要があります。また、キューのサイズや、キューが空であるかどうかを把握しておくと役立ちます。これらは 4 つの関数、Size()、IsEmpty()、Front()、および Back() で定義します。

# キューのサイズを返します。
Size<public>()<transacts>:int=
    Elements.Length

# キューが空の場合は、成功します。
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# キューの前の要素を返します。
Front<public>()<decides><transacts>:t=
    Elements[0]

# キューの後ろの要素を返します。
Rear<public>()<decides><transacts>:t=
    Elements[Elements.Length - 1]
Copy full snippet

# キューのサイズを返します。 Size<public>()<transacts>:int= Elements.Length # キューが空の場合は、成功します。 IsEmpty<public>()<decides><transacts>:void= Size() = 0 # キューの前の要素を返します。 Front<public>()<decides><transacts>:t= Elements[0] # キューの後ろの要素を返します。 Rear<public>()<decides><transacts>:t= Elements[Elements.Length - 1]

Size() 関数は Elements 配列の Length を返します。IsEmpty() 関数は Size() 関数を呼び出し、<transacts> 指定子を持っています、つまり、Size() が 0 に等しくない場合は、失敗します。

Front() 関数と Rear() と関数は、要素配列の前 (インデックス 0) と後 (Length - 1) のインデックスにある要素を返します。配列が空の場合に配列へのアクセスが失敗する可能性があるため、これら両方の関数が <decides><transacts> 指定子を持っています。

stack と同様に、queue クラスもコンストラクタ関数を使用して Elements 配列を割り当てる必要があります。コンストラクタ関数は Elements の値にアクセスして、要素の初期配列に割り当てることができます。

# 要素の初期配列 InitialElements からキューを作成して返します。
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements
Copy full snippet

# 要素の初期配列 InitialElements からキューを作成して返します。 CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t): Elements := InitialElements

エンキューとデキュー

キューに要素を追加したり、キューから要素を削除するには、キューの後ろに新しい要素を エンキュー (追加) するか、前から要素を デキュー (取り出し) する必要があります。

# NewElement を後ろに持つ新しいキューを返すことで、
# キューの後ろに新しい要素を追加します。
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# キューの前にある要素を削除し、
# 要素が削除された新しいキューと削除された要素の両方で構成されるタプルを返します。
Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
    FirstElement := Front[]
    (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)
Copy full snippet

# NewElement を後ろに持つ新しいキューを返すことで、 # キューの後ろに新しい要素を追加します。 Enqueue<public>(NewElement:t):queue(t)= queue(t){Elements := Elements + array{NewElement}} # キューの前にある要素を削除し、 # 要素が削除された新しいキューと削除された要素の両方で構成されるタプルを返します。 Dequeue<public>()<decides><transacts>:tuple(queue(t),t)= FirstElement := Front[] (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

Enqueue() 関数はキューに挿入したい要素を受け取り、新しい要素を後ろに持つ新しいキューを返します。現在のキューを変更するのではなく、新しいキューを返すことは、関数型プログラミング の一例であり、副次的エフェクト のリスクを減らすことができます。

Dequeue() 関数では、キューの前にある要素を削除して返す必要があります。また、(RemoveElement[] 関数を使用して) 最初の要素を削除した新しいキューを返す必要もあります。配列へのアクセスと Front() の呼び出しは失敗する可能性がある式であるため、Dequeue() は <decides><transacts> 指定子を持っている必要があります。

完全なコード

以下は、キュー クラスの完全なコードです。

queue<public>(t:type) := class:
    Elements<internal>:[]t = array{}

    # NewElement を後ろに持つ新しいキューを返すことで、
    # キューの後ろに新しい要素を追加します。
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # キューの前にある要素を削除し、
    # 要素が削除された新しいキューと削除された要素の両方で構成されるタプルを返します。
    Dequeue<public>()<decides><transacts>:tuple(queue(t),t)=
        FirstElement := Front[]
        (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement)

    # キューのサイズを返します。
    Size<public>()<transacts>:int=
        Elements.Length

    # キューが空の場合は、成功します。
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # キューの前の要素を返します。
    Front<public>()<decides><transacts>:t=
        Elements[0]

    # キューの後ろの要素を返します。
    Rear<public>()<decides><transacts>:t=
        Elements[Elements.Length - 1]
       
# 要素の初期配列 InitialElements からキューを作成して返します。
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements
Copy full snippet

queue<public>(t:type) := class: Elements<internal>:[]t = array{} # NewElement を後ろに持つ新しいキューを返すことで、 # キューの後ろに新しい要素を追加します。 Enqueue<public>(NewElement:t):queue(t)= queue(t){Elements := Elements + array{NewElement}} # キューの前にある要素を削除し、 # 要素が削除された新しいキューと削除された要素の両方で構成されるタプルを返します。 Dequeue<public>()<decides><transacts>:tuple(queue(t),t)= FirstElement := Front[] (queue(t){Elements := Elements.RemoveElement[0]}, FirstElement) # キューのサイズを返します。 Size<public>()<transacts>:int= Elements.Length # キューが空の場合は、成功します。 IsEmpty<public>()<decides><transacts>:void= Size() = 0 # キューの前の要素を返します。 Front<public>()<decides><transacts>:t= Elements[0] # キューの後ろの要素を返します。 Rear<public>()<decides><transacts>:t= Elements[Elements.Length - 1] # 要素の初期配列 InitialElements からキューを作成して返します。 CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t): Elements := InitialElements

応用編

スタックおよびキューをイテレートして、拡張する方法は複数あります。そのため、機能を追加するさまざまな方法を検討する必要があります。ここでは、作業を開始する際に役立つアイデアを紹介します。

• キューを、最後の要素が最初の要素に接続され、キューがループし続けるような、循環キューにすることはできるでしょうか？

• オブジェクトがキューに入ったタイミングと、その他の値の両方に基づいてオブジェクトが順序付けされる優先順位キューを作成してみてはどうでしょうか？

• Tower of Hanoi のようなスタックを使ったゲームを作成できるでしょうか？顧客が行列で待たなければならないレストラン ゲームを作成してみてはどうでしょうか？