자료구조 - stack, queue, heap in Python

DataStructure

비전공자인 나는 정말 지식이 부족하다.
stack, queue, heap에 관한 기본적인 지식조차 부족했던 것 같다.
코딩테스트를 준비하는 겸 자료구조에 대해 간단히 알아보았다.
자료구조는 포인터, 메모리 할당 면에서 C로 공부하는 것이 괜찮다는 말을 들었지만 코딩테스트까지 시간이 얼마 없어 쉬운 Python으로 찾아보았다.

stack

스택이란 간단히 최근에 들어간 것이 먼저 나오는 구조이다.

s = []

# 's = [10, 20, 30]' 와 같음
s.append(10)
s.append(20)
s.append(30)

while s:
	print(s.pop())

결과는 30, 20, 10 이다.
먼저 추가해준 10이 가장 늦게 나온다.
파이썬의 list와 같다고 볼 수 있다.

queue

큐란 스택과 반대된다고 볼 수 있다.
즉 들어간 순서대로 나오는 구조이다.

# python에는 큐에 관한 적절한 자료구조가 없어서 deque를 import해서 사용한다.
from collections import deque

q = deque()

# 'q = deque([10, 20, 30])' 와 같음
q.append(10)
q.append(20)
q.append(30)

while q:
	print(q.popleft())

결과는 10, 20, 30.
먼저 추가해준 10이 가장 먼저 나오는 모습.

heap

Python heapq 라이브러리에서는 이진 트리를 기반으로 최소 힙(위로 갈수록 작은 값) 자료구조를 제공한다.

# heap을 사용하기 위해 heapq를 import.
import heapq

arr = []

heapq.heappush(arr, 10)
heapq.heappush(arr, 3)
heapq.heappush(arr, 7)
heapq.heappush(arr, 1)
heapq.heappush(arr, 2)
heapq.heappush(arr, 5)

print(arr)

다음은 힙 구조가 만들어지는 순서이다.

10

   10
  /
3

   3
  /
10

   3
  / \
10   7

     3
    / \
  10   7
 /
1  

    3
   / \
  1   7
 /
10  

    1
   / \
  3   7
 /
10  

위와 같은 과정으로 마지막 5까지 넣어주면 print(arr)의 결과(위, 왼쪽부터 읽음)로 [1, 2, 5, 10, 3, 7]이 출력된다.

       1
     /   \
   2       5  => 힙 구조
  / \     /
10   3   7

while arr:
	print(heapq.heappop(arr))

실행하면 작은 것(루트인 1)부터 작은 순서대로 1, 2, 3, 5, 7, 10이 출력된다
.
처음의 1이 제거되면 1이 빠져나가면서 맨 마지막 7이 1 자리로 올라온다.

       7
     /   \
   2       5
  / \     
10   3   

그 후 다시 정렬이 된다.

       2
     /   \
   7      5
  / \     
10   3   


       2
     /   \
   3       5
  / \     
10   7

그래서 한 번만 heappop을 진행하면 print(arr)은 [2, 3, 5, 10, 7]이다.

또한 기존 리스트를 힙구조로 변환할 수 있다.

import heapq

arr = [4, 1, 2, 7, 9]
heapq.heapify(arr)

print(arr)

결과는 [1, 4, 2, 7, 9]. 위의 과정을 보고 왜 이런 순서로 구조가 됐는지는 직접 생각해보는 것이 좋을 것이다.

import heapq

arr = [4, 1, 2, 7, 9]
heap = []

for value in arr:
	heapq.heappush(heap, -value)

for i in range(5):
	print(-heapq.heappop(heap))

최소 힙이 아닌 최대 힙 구조로 만들고 싶으면 위와 같은 방법을 사용하면 된다.
결과는 큰 순서대로 9, 7, 4, 2, 1이 출력된다.

마무리

나는 참 갈 길이 먼 것 같다...
공부를 하면 할수록 할게 많아지는 느낌이다.
재밌는, 편한 코딩만 하려 하지 말고 기초 cs 지식을 꾸준히 놓치지 말고 해야겠다!

---

이미지 출처
https://electricalvoice.com/stack-vs-queue-vs-heap/