[TIL]アルゴリズム&データ構造:スタックとキュー、優先キュー

1.スタックとキュー

1-1. スタックデータ構造

先入後出フォーマット

入口と出口の形状は同じで、箱を積み重ねて可視化できます

DFSなどの複数のアルゴリズムに使用されるデータ構造

時間的複雑度は常にO(1)である.

Pythonはリスト形式を受け入れる

📌 実装例

stack = []

# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack[::-1])	# 최상단 원소부터 출력
print(stack)	# 최하단 원소부터 출력

1-2. キューデータ構造(a.k.a.フェアデータ構造)

先進的なデータの先出しフォーマット(先入先出)

入口と出口に穴が開いているトンネルのように、ココはキューとして扱われています

dequeライブラリを使用すると、Pythonでキューを実装する場合、リストフォーマットの時間的複雑さがより高いため

データ挿入はappend()を用い,データ削除はpopleft()を用いるため,この方法の時間的複雑度はO(n)であるが,通常は

📌 実装例

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) > 삽입(2) > 삽입(3) > 삽입(7) > 삭제() > 삽입(1) > 삽입(4) > 삭제()
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)	# 나중에 들어온 원소부터 출력

2.優先キュー

データ構造

は、最も優先度の高いデータ

を最初に削除する.

データ優先処理用

資料構造比較表

データ構造抽出データスタック(Stack)最新挿入データキュー(Queue)最初に挿入されたデータ優先度キュー(Priority Queue)が最も高いデータ

実施方法

リスト実装

スタックを用いて

を実現

時間の複雑さ
優先キュー実装挿入時間削除時間リストO(1)O(N)Hip(Heap)O(log N)O(log N)
お尻にN個のデータを入れ、すべて取り出す=お尻揃え
時間複雑度:O(N log N)
👉 そのため、お尻の時間の複雑さはリストよりも低い!

お尻の特徴

完全バイナリツリーデータ構造
ルートノードe左側サブノードe右側サブノード順にデータを挿入するツリー

ルートノードを常に削除(ルートノード)

複数の最短パスアルゴリズムを含み、複数のアルゴリズムに使用できます.

最小ヒープ(minheap)

ノードの最小値.

の値が最も小さいデータは優先的に削除されます.

さいだいヒープ

ノードの最大値.

の値が大きいデータを優先的に削除します.

最小臀部構成関数:Min-Hapify()

上から下へ:親ノードにドリルダウンし、値が親ノードより小さい場合は、親ノードと自分の位置

を置き換えます.

の新しい元素を挿入すると,O(logN)の時間的複雑さをhip特性に保つことができる.

hipから元素を除去するとO(logN)の時間的複雑さもhip特性を維持できる.

の最後のノードをルートノードの位置に到達させる.

ノードからHeapify(),合計

を下へ行う.
📌 実装例

import sys
import heapq	# 파이썬의 힙 라이브러리
input = sys.stdin.readLine

def heapsort(iterable):
    h = []
    result = []
    # 모든 원소를 차례대로 힙에 삽입 (-1을 인자에 넣으면 max heap 가능)
    for value in iterable:
        heapq.heappush(h, value)
    # 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기 (-1을 인자에 넣으면 max heap 가능)
    for i in range(len(h)):
        result.append(heapq.heappop(h))
    return result

n = int(input())
arr = []

for i in range(n):
    arr.append(int(input()))

res = heapsort(arr)

for i in range(n):
    print(res[i])