자료구조 : 스택(Stack) / 큐(Queue) / 우선순위 큐(Priority Queue) for 파이썬(Python)

머기조 2023. 3. 10. 14:41

ADT : 스택 (Stack)

스택은 '쌓다'라는 사전적 정의와 같이 밑에서 부터 쌓아 올리는 구조를 한다. 삽입과 삭제 등을 위한 접근은 목록의 끝(보통 'top'이라 칭한다. 가장 최근의 데이터라고 할 수 있다.)에서만 가능하다. 후입선출(Last-In First-Out, LIFO)의 구조를 하고 있다.

스택의 응용

: 웹에서 방문한 웹 페이지들의 기록 / 재귀의 구현 등

Data Structure : 파이썬(Python)에서의 스택 구현

list

파이썬에 이미 list를 이용하여 스택 구조를 구현할 수 있는 기능 및 내장함수가 존재한다. ~~(파이썬 맛있다!)~~

append() : 리스트 마지막에 괄호 안 원소를 추가(삽입)
pop() : 리스트 마지막 원소 삭제 / 괄호 안에 원소를 지정하여 삭제도 가능하지만 '스택' 구조와는 관련없음
_list[-1] : 스택의 마지막 데이터인 top을 바로 가져올 수 있음 (리스트의 -1 인덱스 == 리스트의 마지막 원소)

_list = [1, 2, 3]
_list.append(5)

# => [1, 2, 3, 5]

_list = ['a', 'b', 'c']
_list.append('x')

# => ['a', 'b', 'c', 'x']

_list = [1, 2, 3]
_list.pop()

# => [1, 2]

_list = [1, 3, 5]
top = _list[-1]

print(top)
# => 5

ADT : 큐 (Queue)

큐는 '(무엇을 기다리는 사람 등의) 줄'이라는 사전적 정의를 통해 그 구조를 쉽게 연상할 수 있다. 큐의 삽입 기능은 목록의 가장 앞(front)에서 수행되고, 삭제 기능은 목록의 가장 뒤(rear)에서 수행된다. 따라서, 큐는 선입선출(First-In First-Out, FIFO)의 구조를 가진다.

큐의 응용

: 대기열 / 관료적 체제 / 공유 자원에 대한 접근(프린터 등) 등

Data Structure : 파이썬(Python)에서의 큐 구현

list

큐도 스택과 마찬가지로, 파이썬에 이미 내장되어 있는 list 등을 이용하면 자료구조로서 이용할 수 있다. 하지만, 특히 파이썬에서의 list를 이용한 큐 구현은 성능면에서 좋지 않다. 파이썬 list 자료구조는 타 언어의 배열과 같이 무작위적인(index를 이용한) 접근에 최적화되어 있기에 큐를 구현하는 데에 있어서는 추천되지 않는다. ~~(파이썬 맛없다!)~~

_list.append() :
_list.pop(0) : 스택과 마찬가지로 pop() 함수를 이용하지만, index에 0을 줌으로써 첫 데이터를 삭제할 수 있음

queue = [1, 3, 5]

queue.append(7)
# => [1, 3, 5, 7]

queue.pop(0)
# => [3, 5, 7]

collections 모듈 deque

deque, double-ended queue의 약자로 선입선출의 구조를 가지고 있는 큐를 양방향에서 데이터를 삽입, 삭제할 수 있는 구조로 변화시킨 것이다. 즉, 스택과 큐의 장점을 동시에 가지고 있다.

from collections import deque

dq = deque('code')
print(dq)
# deque(['c', 'o', 'd', 'e'])

dq2 = deque([1, 2, 3, 4])
print(dq2)
# deque([1, 2, 3, 4])

append(), pop() : list의 메소드 활용과 동일
appendleft(), pop(), append(), popleft() : 순서대로 left 삽입, right 삭제 / right 삽입, left 삭제 구현
extend(), extendleft() : 각각 오른쪽, 왼쪽으로 문자열, 리스트 등을 확장시킬 수(이어 붙일 수) 있음 / extendleft()는 매개변수에 있는 deque가 그대로 들어가는 것이 아닌 역순으로 붙는다는 점 주의

from collections import deque

dq = deque('code')
print(dq)
# deque(['c', 'o', 'd', 'e'])

dq2 = deque('python')

dq.extend(dq2)
print(dq)
# deque(['c', 'o', 'd', 'e', 'p', 'y', 't', 'h', 'o', 'n'])

dq.extendleft(dq2)
print(dq)
# deque(['n', 'o', 'h', 't', 'y', 'p', 'c', 'o', 'd', 'e', 'p', 'y', 't', 'h', 'o', 'n'])

인덱스를 활용하여, deque 내의 특정 원소 수정가능

from collections import deque

dq = deque('code')
print(dq)
# deque(['c', 'o', 'd', 'e'])

dq[2] = 'X'
print(dq)
# deque(['c', 'o', 'X', 'e'])

remove() : 리스트와 마찬가지로 특정 원소 지정(값으로)하여 삭제함 / 가장 먼저 나오는 원소를 삭제
clear() : deque 전체 삭제
reverse(), rotate() : 각각 deque를 역순으로 바꾸고, 가장 오른쪽 원소를 가장 앞으로 가져오며 나머지 원소들을 한 칸씩 뒤로 밀어내는 메소드 / rotate()의 매개변수로 양수를 쓰면 오른쪽으로 회전, 음수를 쓰면 왼쪽으로 회전

import sys
input = sys.stdin.readline
from collections import deque

dq = deque()
for i in range(1, 6):
    dq.append(i)
# dq = deque([1, 2, 3, 4, 5])

dq.rotate(-1)

print(dq)
# dq = deque([2, 3, 4, 5, 1])

deque의 주요 메소드 시간복잡도 / https://wellsw.tistory.com

ADT : 우선순위 큐 (Priority Queue)

우선순위 큐는 FIFO 구조의 큐와 다르게, 우선순위를 정하여 그 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조 이다.

Data Structure : 파이썬(Python)에서의 우선순위 큐 구현

queue 모듈 PriorityQueue

put(), get() 메소드 모드 O(logN)의 시간 복잡도를 가진다. 파이썬에서 PriorityQueue를 통해 구현한 우선순위 큐는 iterable하지 않아, 인덱스로 접근 불가이며, for문을 통해 원소에 접근할 수도 없다. get() 메소드를 통해 기준을 정하여 빼고, 반환하여 이용하거나 출력하는 등의 동작이 가능하다.

q = PriorityQueue() : 우선순위 큐 생성 및 초기화
q = PriorityQueue(maxsize=10) : maxsize를 입력하지 않을 시, 디폴트 사이즈는 무한대로 설정됨
put() : 매개변수로 데이터를 넣어 우선순위 큐에 원소 삽입 / 디폴트 기준으로 오름차순 정렬됨
get() : 삭제 메소드로, 우선순위 기준이 정해지지 않으면, 크기가 작은 순서대로(오름차순으로) 삭제
put((우선순위, 값)) : 우선순위를 기준으로 값(데이터)을 저장할 수 있음
get()[우선순위] : 우선순위를 입력하여 원하는 데이터를 삭제할 수 있음

from queue import PriorityQueue

q = PriorityQueue()

q.put(10)
q.put(2)
q.put(12)
q.put(55)
q.put(15)
q.put(28)

print(q.get())
print(q.get())

# 2
# 10

사용이 조금 복잡한 것 같다.

qsize() : 우선순위 큐 사이즈 반환
empty() : 우선순위 큐가 비어있으면 True, 아니면 False 반환
full() : 큐가 maxsize와 같은 값 즉, 가득차있으면 True, 아니면 False를 반환