[Algorithm] 알고리즘을 위한 자료구조 스택과 큐 대해
이번 시간에는 코딩 테스트를 위한 알고리즘에 사용되는 자료구조로 스택과 큐에 대해서 간단히 알아보고자 합니다. 이후에 자료구조에 대해서 정리할 시간이 있다면 그 때 좀 더 구체적으로 다루도록 하겠습니다. 사실 스택은 알고리즘이라기 보다는 자료구조이지만 이런 자료구조들이 알고리즘 문제를 풀 때 자주 사용되므로 그냥 카테고리와 태그를 알고리즘으로 하였습니다.
스택
스택(stack)은 박스 쌓기에 비유할 수 있습니다. 흔히 박스는 아래에서부터 위로 차곡차곡 쌓고 아래에 있는 박스를 치우기 위해서는 위에 있는 나중에 쌓인 박스들부터 걷어내야 합니다. 이러한 구조를 선입후출(First In Last Out) 구조라고 합니다.
스택은 다음과 같은 기본 연산이 있습니다.
- push : 스택의 맨 위에 새로운 항목을 추가합니다.
- pop : 스택의 맨 위에 있는 항목을 제거하고 그 항목을 반환합니다.
- peek/top : 스택의 맨 위에 있는 항목을 반환하지만 제거하지는 않습니다.
- isEmpty : 스택이 비어 있는지 확인합니다.
파이썬 코드로 스택을 한 번 간단히 구현해 보도록 하겠습니다.
# 삽입(5)-삽입(2)-삽입(3)-삽입(7)-삭제()-삽입(1)-삽입(4)-삭제()
stack = []
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최 상단 원소부터 출력
콘솔 출력
[5, 2, 3, 1]
[1, 3, 2, 5]
큐
큐(queue) 는 대기 줄에 비유할 수 있습니다. 우리가 흔히 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 됩니다. 이러한 구조를 선입선출(First In First Out)라고 합니다.
큐는 다음과 같은 기본 연산이 있습니다.
- enqueue : 큐의 끝에 항목을 추가
- dequeue : 큐의 맨 앞의 항목을 제거
- peek : 큐의 맨 앞에 있는 항목을 확인
- isEmpty : 큐가 비었는지 확인
파이썬 코드로 큐를 간단히 구현해 보도록 하겠습니다.
from collections import deque
#큐 구현을 위한 deque 라이브러리 사용
queue = deque()
# 삽입(5)-삽입(2)-삽입(3)-삽입(7)-삭제()-삽입(1)-삽입(4)-삭제()
queue.append(5)
queue.append(5)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
콘솔 출력
deque([3, 7, 1, 4])
deque([4, 1, 7, 3])
파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용해야 합니다. deque 는 스택과 큐의 장점을 모두 채택한 자료구조인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며, queue 라이브러리를 이용하는 것보다 더 간단합니다. 더불에 대부분 코딩 테스트에서는 collections 모듈과 같은 기본 라이브러리 사용을 허용하므로 안심하고 사용해도 괜찮습니다.
Comments