[자료구조/알고리즘] python 스택, 큐, 우선순위 큐 개념 및 예제

<개념>

스택 (stack)

• 선입 후출 형식으로, 나중에 들어오는 데이터를 제일 먼저 반환하는 방식
• 파이썬에서는 리스트에 append 후 pop 함수를 통해 구현 가능
• append 를 통해 리스트에 순서대로 데이터를 적재
• pop 함수를 통해 가장 마지막에 들어온 데이터를 추출

스택 append

스택 pop 추출

예제)

# stack
def sol(s):
    check = []

    for i in s:
        if i == '(':
            check.append(i)
        else:
            try:
                check.pop()
            except:
                return False
    else:
        if len(check) != 0:
            return False
        else:
            return True

# s = "()()"
# s = "(())()"
s = ")()("
# s = "(())("

sol(s)

큐 (Queue)

• 선입 선출 형식으로, 먼저 들어온 데이터를 제일 먼저 반환하는 방식
• 파이썬에서는 리스트에 append 후 dequeue 또는 pop(0) 을 통해 구현 가능
• append 를 통해 리스트에 순서대로 데이터를 적재
• dequeue 또는 pop(0) 함수를 통해 가장 먼저 들어온 데이터를 추출

예제)

from collections import deque

def sol(j):
    queue = deque(j)
    while queue:
        c_j = queue.popleft()
        print(c_j)

sol(['1','2','3'])

정리

우선 순위 큐 (Priority Queue)

• 데이터에 중요도(우선순위)를 주면, 높은 중요도 순으로 나오는 방식

예제)

import heapq
def sol(p):
    heapq.heapify(p)
    while p:
        a,b = heapq.heappop(p)
        print(a,b)

# 집합 {} 자료 형은 순서가 없기 때문에 불가, 리스트, 튜플 형식만 가능
sol([[2, "patient2"], [1, "patient1"], [3, "patient3"]])