[이것이코딩테스트다]5장_탐색 알고리즘 DFS/BFS(2)_DFS,BFS에 필요한 자료구조 - 스택, 큐

#스택

스택 : 박스 쌓기에 비유할 수 있음. 박스는 아래에서부터 위로 차곡차곡 쌓고 아래에 있는 박스를 치우기 위해서는 위에있는 박스를 먼저 내려야함. 이러한 구조를 선입후출(FILO) 구조 또는 후입선출(LIFO) 구조 라고 함

 

#파이썬의 스택 구현

리스트(stack=[])로 구현하며 push, pop은 아래와 같은 함수로 구현한다.

i를 push : stack.append(i) 

최상단 원소를 pop : stack.pop()

 

#스택 예제

stack=[]
stack.append(5) #5를 스택에 push
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop() #최상단 원소를 pop
stack.append(1)
stack.append(4)
stack.pop()

print(stack) #스택의 최하단 원소부터 출력
print(stack[::-1]) #스택의 최상단 원소부터 출력


'''
결과
[5, 2, 3, 1]
[1, 3, 2, 5]
'''

 ▲설명

▲ 그림을 보면 리스트의 맨 앞부분이 스택의 최하단 맨 끝부분이 스택의 최상단이다!

 

 

#큐

큐는 대기줄에 비유할 수 있다. 우리가 흔히 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 된다. 나중에 온 사람일수록 나중에 들어가기 때문에 흔히 '공정한' 자료구조라고 비유된다. 이러한 구조를 '선입선출' 구조라고 한다.

 

#파이썬에서 큐 구현

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque자료구조를 활용한다. deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue라이브러리를 이용하는 것보다 더 간단하다.

 

#큐 구현을 위해 알아두어야 할 것 

1. deque라이브러리 import : from collections import deque

2. 큐 구현을 위해 deque라이브러리 사용 : queue = deque() 

3. i를 push : queue.append(i)

4. 먼저 들어온 원소를 pop : queue.popleft()

5. deque객체를 리스트 자료형으로 변경하고자 한다면 list()메서드를 사용한다. 

 

#큐 예제 

from collections import deque

queue=deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) #먼저 들어온 순서대로 출력
queue.reverse() #다음 출려을 위해 역순으로 바꾸기
print(queue) #나중에 들어온 원소부터 출력
print(list(queue))#deque객체를 list자료형으로 바꾸기

'''
출력 결과 
deque([3, 7, 1, 4])
deque([4, 1, 7, 3])
[4, 1, 7, 3]
'''

▲설명

▲append로 원소를 삽입(push)하고 popleft로 원소를 삭제(pop) 한다.