はじめに
データ構造は、効率的にデータにアクセスして変更できるように、コンピュータ内のストレージを整理します。 スタックとキューは、計算機科学で定義された最も初期のデータ構造の一部です。
学習が簡単で実装が簡単で、その用途は一般的であり、さまざまなタスクのためにソフトウェアに組み込むことが最も可能性が高いでしょう。
スタックとキューは、配列またはリンクリストで実装されるのが一般的です。 スタックとキューの両方に対応するために、Listデータ構造に依存します。彼らはどのように動作しますか？
スタック
スタックは、名前が示すように、LIFO（Last-in-First-Out）の原則に従います。 コインを積み重ねているかのように、私たちが一番上に置いた最後のコインは、後でスタックから最初に取り除かれるコインです。したがって、スタックを実装するには、次の2つの簡単な操作が必要です。
push-スタックの先頭に要素を追加します。push-スタックの先頭に要素を追加します。push
pop-スタックの先頭にある要素を削除します。
キュー
名前は、先入れ先出し（先入れ先出し）（先入れ先出し）の主義に続きます提案します。 映画のチケットを待ち行列で待っているかのように、最初に並んでいるのは、チケットを購入して映画を楽しむ最初のものです。したがって、キューを実装するには、次の2つの簡単な操作が必要です。
enqueue-キューの最後に要素を追加します。enqueue-キューの最後に要素を追加します。iv id=”2364377122:
dequeue-キューの先頭にある要素を削除します。
リストを使用したスタックとキュー
Pythonの組み込みの
Listデータ構造は、スタック操作とキュー操作の両方をシミュレートするメソッドにバンドルされています。文字のスタックを考えてみましょう：
キューを実装するために同じ関数を使用することができます。
pop0popappendpop操作を使用して、キューのコア操作をシミュレートします。Dequeライブラリを使用したスタックとキュー
Pythonには
deque（発音は’deck’）ライブラリがあり、スタックまたはキューとしdequeはDouble Ended Queueの略で、格納されている最初または最後の要素を取得できる一般化されたキューです。dequeライブラリやPythonが提供する他のタイプのコレクションについてもっと知りたい場合は、Pythonのコレクションモジュールの記事を読むことができます。あなたのコードがスタックを必要とし、あなたがListinsertremoveまたはあなたのスタックの順序に影響を与える他のリスト関数を呼び出すのを止めるものは何もありません！ これは、もはや必要な方法で機能しなくなるため、スタックを定義するポイントを根本的に台無しにします。データに対して有効な操作のみを実行できるようにしたい場合があります。
各データ構造に必要なメソッドのみを公開するクラスを作成できます。
これを行うには、
stack_queue.pyという新しいファイルを作成し、二つのクラスを定義しましょう。StackQueueを使用するプログラマは、代わりにデータを操作するために提供されているメソッドを使用することをお勧めします。例
あなたはブランドの新しいワードプロセッサに取り組んで開発者であると想像してみてください。 ユーザーがセッションの開始まで自分のアクションをバックトラックできるようにするために、元に戻す機能を作成することを任されています。
スタックはこのシナリオに理想的です。 スタックにプッシュすることで、ユーザーが取るすべてのアクションを記録できます。 ユーザーがアクションを元に戻したいときは、スタックからそれをポップします。 このような機能をすばやくシミュレートすることができます。
キューはプログラミングでも広く使用されています。 ストリートファイターや大乱闘スマッシュブラザーズのようなゲームを考えてみてください。 これらのゲームのプレイヤーは、ボタンの組み合わせを押すことによって特別な動きを実行することができます。 これらのボタンの組み合わせは、キューに格納できます。今、あなたは新しい格闘ゲームに取り組んで開発者であることを想像してみてください。
今、あなたは新しい格闘ゲームに取り組んで開発者であ ゲームでは、ボタンが押されるたびに入力イベントが発生します。 テスターは、ボタンがあまりにも速く押された場合、ゲームは最初のものだけを処理し、特別な動きが動作しないことに気づいた！あなたはキューでそれを修正することができます。 すべての入力イベントを入力時にエンキューすることができます。 このようにして、入力イベントがそれらの間にほとんど時間がない場合でも、それらはすべて保存され、処理に利用できるようになります。 動きを処理しているとき、私たちはそれらをデキューすることができます。 特別な移動は次のように行うことができます。
結論
スタックとキューは、データを順番に格納および取得できる単純なデータ構造です。 スタックでは、最後に入力した項目が最初に出てくるものです。 キューでは、最初に入力した項目が最初に出てくるものです。
pushpopenqueuedequeue操作を使用してアイテムを取得します。Pythonでは、組み込みのListデータ構造を使用するだけでスタックとキューを実装できます。 Pythonには、1つのオブジェクトでスタックとキューの操作を効率的に提供できるdequeライブラリもあります。 最後に、stackクラスとqueueクラスを作成して、データをより厳密に制御しました。スタックとキューには多くの実世界のユースケースがあり、それらを理解することで、多くのデータストレージの問題を簡単かつ効果的に解決できます。