스택과 큐 간단 정리(DFS,BFS/이론)

 

DFS와  BFS를 이해하기 위해서는 스택과 큐에 대해서 먼저 이해해야한다. 

그를 위해 스택과 큐, 그리고 잘 쓰이는 코드에 대해(python) 아주 간단하게 정리해보고자 한다.

 

---

 스택

스택은 쌓다라는 뜻인만큼 상자쌓기에 비유할 수 있다. 

들어간 역순으로 데이터를 뺄 수 있다. 간단하게 선입후출의 형식이다.

 

스택은 아래 코드로 선언가능하고

stack = []

아래 코드로 삽입할 수 있다.

stack.append(5)

 

삭제는 아래 코드로 가능한데 스택의 구조상 가장 늦게 들어간것이 삭제된다. (선입후출)

stack.pop()

출력은 스택을 그대로 넣어 출력이 가능한데, 최하단 원소 즉, 가장 먼저 들어간 데이터부터 출력 가능하다. 

print(stack)

거꾸로 출력도 가능한, 아래 코드를 쓰면 된다.

print(stack[::-1])

---

큐

큐는 대기줄에 비유할 수 있는데, 기본적으로 먼저 들어간 데이터가 먼저 나오는 선입선출의 형식을 가진다. 

파이썬에서 스택은 따로 라이브러리를 사용하지않고 리스트 형태를 사용하지만 큐는 따로 deque라는 라이브러리를 호출한다. 

from collections import deque

선언은 아래와 같다.

queue = deque()

삽입코드

queue.append()

삭제코드

queue.popleft()

출력

print(queue)

역순으로 출력

queue.reverse()
print(queue)

deque객체를 리스트로 변형

list(queue)