스택과 큐

스택 & 큐

스택과 큐는 컴퓨터 공학에서 가장 기본이 되는 자료구조다. 예시를 들자면 스택은 ‘택배 상하차’ 를 생각하면 된다. 반면에 큐는 ‘은행 창구’를 생각하면 된다.

즉, 스택은 아래서부터 쌓고, 꺼낼 때는 위에서부터 꺼낼 수 있는 구조다. → 나중에 입력한 값을 먼저 꺼내는 구조

큐는 먼저 입력한 값이 먼저 꺼낼 수 있는 구조다.

결국에 스택 큐 라고 생각하면 된다.

큐

파이썬에서 큐를 구현하는 방법에는 크게 3가지가 있다.

list사용하기

q = []

q.append() # 큐에 입력
q.pop(0) # 가장 앞에 있는 값 빼기
Python
복사

collection.deque

deque는 파이썬 자료구조의 일종. list와 비슷하게 동작하지만, 연산 복잡도에 있어 dequeue가 더 빠르게 동작하도록 설계되어 있다고 한다.

from collections import deque

q = deque() 

q.append() # 큐에 입력
q.popleft() # 가장 앞에 있는 값 빼기
Python
복사

queue.Queue

queue는 멀티 스레드를 위해 만들어진 라이브러리다. 따라서 deque에 비해 많이 느리다.

•

queue : 파이썬 큐 내장 모듈

◦

Queue() : FIFO 구조

◦

LifoQueue() : LIFO 구조 (= 스택)

◦

PriorityQueue() : 사용자 지정

•

put() : 입력

•

get() : 가장 앞에 있는 값 빼기

•

empty() : 큐가 비어있으면 True, 아니면 False

•

qsize() : 큐의 길이 

import queue

# 큐 모듈의 큐 클래스 객체 선언
data = queue.Queue()
print(type(data)) # <class 'queue.Queue'>

# 선언된 큐 객체에 3개 데이터 입력하기 : 2,5,8
data.put(2)
data.put(5)
data.put(8)

# 큐 객체에서 입력된 객체 하나씩 꺼내기 
print(data.get()) # 2
print(data.get()) # 5
print(data.get()) # 8
Python
복사

우선순위 큐

우선순위가 가장 높은 데이터를 먼저 삭제하는 자료구조.

→ 데이터를 우선순위에 따라 처리하고 싶을 때 사용

자료구조	추출되는 데이터
스택(stack)	가장 나중에 삽입된 데이터
큐(queue)	가장 먼저 삽입된 데이터
우선순위 큐(priority queue)	가장 우선수위가 높은 데이터

•

구현하는 방법

1) 리스트 이용해서 구현

2) 힙(heap) 자료구조를 이용해서 구현

•

데이터 개수가 N개일 때, 구현 방식에 따라 시간 복잡도를 비교한 내용은 다음과 같다

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(heap)	O(logN)	O(logN)

→ 즉, 힙큐를 구현할 때는 힙 자료구조를 이용하는 것이 더 유리하다.

→ 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. (힙 정렬)

→ 이 경우 시간 복잡도는 O(NlogN)

완전 이진 트리

루트 노드부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 삽입되는 트리를 의미.

heapq

힙 은 특정한 규칙을 가지는 트리. (최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안)된 완전이진트리를 기본으로 한다.

•

항상 루트 노드를 제거한다. 

힙 property : A가 B의 부모노드면 A의 키값과 B의 키값 사이에는 대소 관계가 성립

•

최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작거나 같은 힙

◦

최소 힙 구성 함수 : min - heapify()

▪

상향식 : 부모 노드로 거슬러 올라가면서 부모노드가 자신보다 더 크면 위치를 교체해서 최소힙을 만족하게끔 한다. 

•

최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 크거나 같은 힙

이런 속성으로 인해 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.

이때 키값의 대소관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소 관계가 정해지지 않는다.

파이썬 힙 자료구조

파이썬 heapq 모듈은 heapq(priority queue) 알고리즘을 제공한다.

모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.

heapq는 내장 모듈로 별도의 설치 필요없다.

•

heapq.heappush(heap,item) : item을 heap에 추가

•

heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우는 Indexerror 호출. 

→ 자동으로 정렬

•

 heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함(O(N))

# 우선순위 큐 라이브러리를 활용한 힙 정렬 구현 예제
import sys
import heapq
input = sys.stdin.readline()

def heapsort(iterable): # 힙 정렬의 방식을 함수로 구현
	h = []
	result = []
	# 모든 원소를 차례대로 힙에 삽입
	for value in iterable: # 반복가능한 객체의 원소들에 대해서
		heapq.heappush(h, value) # h 리스트에 담는다. (자동으로 min-heap 정렬)
	# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
	for i in range(len(h)):
		result.append(heapq.heappop(h)) # result리스트에 h의 heappop한 값들을 차례로 집어넣는다.
	return result 

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

for i in range(n):
	arr.append(int(input())) # arr은 정해진 개수만큼의 정수를 담고 있는 리스트

res = heapsort(arr) 

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

힙 생성 & 원소 추가

힙 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘겨야 한다.

import heapq

heap = [] # 빈 리스트 생성
heapq.heappush(heap,50) # heap에 50 추가
heapq.heappush(heap,10) # heap에 10 추가
heapq.heappush(heap,20) # heap에 20 추가

print(heap) # [10,50,20] -> 최소힙 정렬
Python
복사

# 기존의 리스트를 힙 자료형으로 변환하기
heap2 = [50,10,20] # 그냥 리스트
heapq.heapify(heap2) # 우선순위 큐로 변경

print(heap2) # [10,50,20]
Python
복사

힙에서 원소 삭제

heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 결과값을 리턴하고, 제거한 뒤에 힙정렬도 자동으로 수행한다.

result = heapq.heappop(heap)

print(result)# 10
print(heap) # [20,50]

# 만약 원소를 삭제하지 않고 값을 가져오고 싶으면 indexing 을 이용한다.
result2 = heap[0]
print(result2) # 20
print(heap) # [20,50]
Python
복사

최대 힙 만들기

파이썬의 heapq 모듈은 최소 힙으로 구현되어 있기 때문에 최대 힙 구현을 위해서는 트릭이 필요하다.

→ IDEA : y = -x 변환을 하면 최솟값 정렬이 최댓값 정렬로 바뀐다.

힙에 원소를 추가할 때 (-item,item) 의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 된다. 이때 원소값의 부호를 바꿨기 때문에, 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용하게 되는 것이다.

아래의 예시는 리스트 heap_items 에 있는 원소들을 max_heap 이라는 최대 힙 자료구조로 만드는 코드다.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
	heapq.heappush(max_heap,(-item,item))

print(max_heap) # [(-9,9),(-7,7),(-3,3),(-1,1),(-5,5)]

# heappop() 을 사용하게 되면 힙에 있는 최댓값이 반환되는 것을 확인할 수 있다. 이때, 실제 원소값은 튜플의 두번째 자리에 저장되어 있으므로 [1]인덱싱을 통해 접근한다.
max_item = heapq.heappop(max_heap)[1]
print(max_item) # 9
Python
복사

heapq 이용한 풀이

Python
복사

스택

파이썬에 따로 내장 모듈은 없다. 대신 ‘리스트’ 처럼 사용하면 된다.

•

append() : 데이터 넣기

•

pop() : 데이터 꺼내기

# 빈 리스트 선언
stack = []

# 2,5,8 차례대로 리스트에 추가하기(-> append)
stack.append(2)
stack.append(5)
stack.append(8)

# 값이 모두 입력된 리스트 출력
print("stack : ", stack)

# 리스트 pop함수 이용해 데이터 꺼내기
print(stack.pop())
print(stack)
print(stack.pop())
print(stack)
print(stack.pop())
print(stack)
Python
복사