[Alg] Search Algorithms - Essential Data Structure


必要な資料構造の基礎

Search


エクスプローラ(Search):大量のデータから必要なデータを検索するプロセス
典型的なナビゲーションアルゴリズム:DFS、BFS

Stack


「先入後出」「最初のインバウンド出力」
後入先出
箱型構造
挿入するそうにゅうする:ボックスを下から上へ順番に積み上げるのと同じ
削除さくじょ:上部からボックスを削除するのと同じです
挿入順序が5-2-3-7の場合、最初に削除されたのは7です.
Pythonは基本リストにappend()とpop()メソッドを提供するため,スタック実装では基本リストを用いた.
append():リストの最後にデータを挿入する
pop():リストの末尾のデータを削除する
stack example
stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack)
print(stack[::-1])
結果
[5,2,3,1][1,3,2,5]

Queue


先入先出
キューなどの構造
先に来た人が先に入ります.
挿入、削除はすべて前の順序で行います.
5-2-3-7の順序で挿入すると、5-2-3-7の順序で削除されます.
Collectionsモジュールが提供するDequeデータ構造を使用してPythonキューを実現
dequeはスタックとキューの利点を同時に採用し、データのアクセス速度はリストデータ型よりも効率的で、queueライブラリを使用するよりも簡単です.
(ほとんどのエンコードテストでは、collectionsモジュールなどのデフォルトライブラリを使用できます)
append():dequeの最後にデータを挿入する
Popleft():dequeの前のデータを削除する
queue example
from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)
queue.reverse()
print(queue)
結果
deque([3,7,1,4])
deque([4,1,7,3])
Dequeオブジェクトをリストとして作成する場合はlist()メソッドを使用します.
list(queue)