Python のスタックとキュー

8月 12, 2021
| コメントはまだありません

はじめに

データ構造は、データに効率的にアクセスし変更できるように、コンピュータのストレージを組織化するものです。

習得が簡単で実装も簡単なため、その用途は一般的で、さまざまなタスクのソフトウェアにそれらを組み込んでいることがほとんどでしょう。

スタックとキューの両方に対応するために List データ構造に依存します。

Stack

スタックは、名前が示すように、後入れ先出し (LIFO) の原則に従っています。 コインを1枚ずつ積み重ねるように、最後に上に置いたコインは、後でスタックから取り除かれる最初のコインとなるのです。

したがって、スタックを実装するには、2つの簡単な操作が必要です。

  • push – スタックの一番上に要素を追加する。

  • pop – スタックの一番上にある要素を削除：

Queue

キューは名前が示すように、FIFO (先入先出し) 原則に従うものです。 映画のチケットを買うために行列に並ぶように、最初に並んだ人が最初にチケットを買って映画を楽しむことができるのです。

キューを実装するには、したがって、2つの簡単な操作が必要です：

  • enqueue – キューの最後に要素を追加する：

  • dequeue – キューの最初に要素を除去する。

リストを使ったスタックとキュー

Python の組み込み List データ構造には、スタックとキューの両方の操作をシミュレートするためのメソッドがバンドルされています。

文字のスタックを考えてみましょう。

同じ関数を使ってキューを実装することができます。 pop 関数はオプションで引数として取得したい項目のインデックスを取ります。

ですから、pop をリストの最初のインデックス、つまり 0 とともに使用すれば、キューのような動作が得られます。

Consider a “queue” of fruits:

Again, here we use the append and pop operations of the list to simulate the core operations of a queue.

Stacks and Queues with the Deque Library

Python has a deque (pronounced ‘deck’) library with a sequence with efficient methods to work as a stack or a queue.Python には、スタックとして動作する、またはキューとして動作する、効率的な方法を提供するライブラリがあります。

deque は Double Ended Queue の略で、格納されている最初または最後の要素を取得できる一般的なキューです。

deque ライブラリと Python の他のコレクションタイプについてもっと学びたい場合は、 Python のコレクションモジュール紹介の記事を読んでください。

Python におけるストリッカーの実装

あなたのコードがスタックを必要とし、List を提供した場合、プログラマーが insert、remove またはスタックの順序に影響を与える他のリスト関数を呼び出すことを止めるものは何もありません!

データに対して有効な操作のみを実行できるようにしたい場合があります。

各データ構造に対して必要なメソッドのみを公開するクラスを作成できます。

これを行うには、stack_queue.py という新しいファイルを作成し、2 つのクラスを定義します。

ここで Stack と Queue を使用するプログラマは、データを操作するために提供されるメソッドを代わりに使用するよう促されます。 あなたは、元に戻す機能 (ユーザーが自分の行動をセッションの初めまでさかのぼることができる) を作成することを課されました。 スタックにプッシュすることで、ユーザーが取るすべてのアクションを記録することができます。 ユーザーがアクションを元に戻したい場合、スタックからそれをポップします。

Queue は、プログラミングでも広く使用されています。 ストリートファイター」や「スーパー・スマッシュ・ブラザーズ」のようなゲームを考えてみてください。 これらのゲームのプレイヤーは、ボタンの組み合わせを押すことで必殺技を繰り出すことができます。

ここで、あなたが新しい格闘ゲームに取り組んでいる開発者であると想像してみてください。 あなたのゲームでは、ボタンが押されるたびに、入力イベントが発生します。 あるテスターは、ボタンがあまりにも早く押された場合、ゲームは最初のものだけを処理し、必殺技は機能しないことに気づきました。 入力イベントが来ると、すべての入力イベントをキューに入れることができます。 この方法では、入力イベントが少し間をおいてやってきても問題なく、それらはすべて保存され、処理に利用できます。 移動の処理をするときは、キューを解除することができます。 特別な手は、次のように作業できます。

Conclusion

スタックとキューは、データを順次保存および取得することができる簡単なデータ構造です。 スタックでは、最後に入力した項目が最初に出てきます。 キューでは、最初に入力した項目が最初に出てきます。

スタックに項目を追加するにはpushオペレーションを使い、項目を取り出すにはpopオペレーションを使います。 キューでは、enqueueオペレーションを使ってアイテムを追加し、dequeueオペレーションを使ってアイテムを取り出す。

Pythonでは、組み込みのListデータ構造を使って、スタックとキューを実装することができる。 また、Pythonにはdequeライブラリがあり、1つのオブジェクトでスタックとキューの操作を効率的に提供することができます。 最後に、スタックとキューをクラス化して、データをより厳密に制御できるようにしました。

スタックとキューの実際の使用例はたくさんあり、それらを理解することによって、多くのデータ保存問題を簡単かつ効果的に解決することができるようになります。

Articles