スタックとキュー

概要

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

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

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

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

スタック

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

使用すべきケース

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

Verse での実装

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

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

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() が必要です。

# Returns the size of the stack.
    Size<public>()<transacts>:int=
        Elements.Length

    # Succeeds if the stack is empty.
    IsEmpty<public>()<decides><transacts>:void=
        Size() = 0

    # Returns the top element of the stack.
    Peek<public>()<decides><transacts>:t=

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

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

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

# Creates and returns a stack from an initial array of elements InitialElements.
CreateStack<public><constructor>(InitialElements:[]t where t:type) := stack(t):
    Elements := InitialElements

プッシュおよびポップ

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

# Adds NewElement to the top of the stack by returning a new
# stack with NewElement as the top
Push<public>(NewElement:t):stack(t)=
    stack(t){Elements := Elements + array{NewElement}}

# Removes the element on top of the stack and returns a tuple of both a new
# stack with the top element removed and the removed element.
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{}

    # Adds NewElement to the top of the stack by returning a new
    # stack with NewElement as the top
    Push<public>(NewElement:t):stack(t)=
        stack(t){Elements := Elements + array{NewElement}}

    # Removes the element on top of the stack and returns a tuple of both a new
    # stack with the top element removed and the removed element.

キュー

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

使用すべきケース

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

Verse での実装

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

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

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() で定義します。

# Returns the size of the queue
Size<public>()<transacts>:int=
    Elements.Length

# Succeeds if the queue is empty
IsEmpty<public>()<decides><transacts>:void=
    Size() = 0

# Returns the element at the front of the queue.
Front<public>()<decides><transacts>:t=

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

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

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

# Creates and returns a queue from an initial array of elements InitialElements.
CreateQueue<public><constructor>(InitialElements:[]t where t:type) := queue(t):
    Elements := InitialElements

エンキューとデキュー

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

# Adds a new element to the back of the queue by returning a
# new queue with NewElement at the back.
Enqueue<public>(NewElement:t):queue(t)=
    queue(t){Elements := Elements + array{NewElement}}

# Removes the element at the front of the queue and returns a tuple of
# both a new queue with the element removed and the removed element.
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{}

    # Adds a new element to the back of the queue by returning a
    # new queue with NewElement at the back.
    Enqueue<public>(NewElement:t):queue(t)=
        queue(t){Elements := Elements + array{NewElement}}

    # Removes the element at the front of the queue and returns a tuple of
    # both a new queue with the element removed and the removed element.

応用編

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

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

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

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