알고리즘 with 파이썬 - (5) 스택과 큐 구현하기

데이터를 탐색할 때 쓰이는 대표적인 탐색 알고리즘 DFS와 BFS 를 이해하려면

기본 자료구조인 스택과 큐, 그리고 재귀함수에 대한 이해가 필요하다

아래는 스택과 큐를 간단히 구현하는 방법

 

1) 스택

# 스택에서의 삽입과 삭제
# 재귀함수는 내부적으로 스택 자료구조와 동일하다
stack =[]

stack.append(5) #최하단
stack.append(2)
stack.append(4)
stack.append(7)
stack.pop() # 자료 최상단에서 삭제
stack.append(1) # 최상단

print(stack)
print(stack[::-1]) #자료 최하단부터 거꾸로 출력하는 방법

 

결과

[5, 2, 4, 1]
[1, 4, 2, 5]

 

2) 큐 - deque 라이브러리가 필요하다는 점 유의

# 큐
# 삽입과 삭제가 각각 다른쪽 끝에서 일어남
from collections import deque
queue = deque() # 큐 구현을 위해 deque 라이브러리를 사용한다

queue.append(3)
queue.append(1)
queue.append(0)
queue.append(7)
queue.popleft() # 왼쪽끝 삭제
queue.append(4)
queue.append(5)
queue.popleft()

print(queue)
queue.reverse() # 역순으로 재배치
print(queue)

#queue 를 리스트 형으로 반환하는 방법
print(list(queue))

결과

deque([0, 7, 4, 5])
deque([5, 4, 7, 0])
[5, 4, 7, 0]