スタックとキュー

スタック、キューの概念

スタック

データ構造

スタックでサポートされているアクションのリスト

push:データを積み重ねた演算

pop:スタック減算データの演算

top:スタック上部のデータを返す演算

空:スタックが空であるか否かを返す演算

後の資料は先に印刷されます.

「第1バッチアウト」(List In First Out)資料構造とも呼ばれる.

Pythonのリストはappend、popなどの操作をサポートしています.

リストを使用してスタックを実装できます.

キュー

資料構造

入口と出口はそれぞれ一端に位置する

キューでサポートされているアクションリスト

push:キューにデータを挿入する演算

pop:キューからデータを削除する演算

front:キューの一番前のデータを返す演算

back:キューの一番後ろのデータを返す演算

空:キューが空であるか否かを返す演算

プッシュ-後方位置に材料を添加し、後方に

を1個増加する.

pop-head位置のデータ消去、head増加1

import queue
q = queue.Queue()

キューを使用するには、Pythonマスターライブラリの

を使用します.

キューモジュールのキュークラスを使用できます.

えんけいキュー

データ構造

は、アレイキューを実装する際に発生する問題を補う

の円形キューの場合、バックエンドまたはヘッダがキューの末尾に到達すると

となる.

キューの先頭に送信して問題を解決します.

リンクキュー

接続リストによって実装されるキューを「リンクキュー」と呼ぶ.

挿入と削除は制限されず、サイズは制限されず、便利

整理する

スタックとキューは線形構造です.

線形構造は,資料が順番に連続する資料構造である.

スタックはまず、後に入力されたデータを出力します.

Qは、先に入力した資料を先に出力します.

Pythonのリスト(配列)を用いてスタックを実装する場合,容易に実装できる.

キューの状況では多くの問題が発生します.

スタックとキューを実際に使用する場合

スタックはPythonのリストを使用し、キューはqueueモジュールのQueueクラスを使用します.

スタック、キューの意味

スタックの使用例

コールスタック

コンピュータプログラムでは、現在実行されている関数(サブルーチン)を格納する役割を果たす.

スタックは依存関係のある状態を格納します.

何よりも先に処理しなければならないことがあれば、スタックに格納できます.

def factorial(n) :
    if n == 0 :
        return 1
    return n * factorial(n-1)
print(factorial(4))

この関数は再帰関数であり、それ自体を呼び出す関数である.

キューの使用例

スヶジューリング

オペレーティングシステム管理プロセス

を同時に実行する複数のプロセスにCPUなどのリソースを割り当てることで、パフォーマンスを向上させることができる.

タスクが並列に実行できる場合、

タスク間に依存関係がない場合は、それらをキューに保存して管理できます.

整理する

スタックは、他の操作の前に完了する必要があります.

キューは、複数のタスクの同時(パラレル)の影響を受けません.

スタックには依存関係があります.

キューは依存しません