[Python][이코테] 스택 & 큐

스택

흔히 게임을 하는 사람이라면 익숙한 단어다. '스택'이라고

 

스택 뒤에 주로 따라오는 단어 중 하나가 바로 '쌓는다'이다.

 

즉 스택은 쌓는 것이다. 탑처럼

 

탑을 쌓을 땐 제일 처음 들어온 게 제일 아래로 가장 마지막에 쌓은 게 제일 위에 있다.

 

이 탑을 하나씩 제거할 땐 가장 최근에 쌓은 것부터 제거가 된다.

 

즉 후입선출 - 나중에 들어온 것이 먼저 나가는 구조이다.

 

이러한 구조다.

 

# 5-1 DFS,BFS 스택

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7) #5 2 3 7
stack.pop()     #5 2 3
stack.append(1)
stack.append(4) #5 2 3 1 4
stack.pop()     #5 2 3 1

print(stack)

 

append로 추가하고

pop으로 빼낸다.

 

---

큐

큐는 스택과 반대로 선입선출 - 먼저 들어온 게 먼저 나간다.

 

즉 우리가 평상시에 어딘가 줄을 서는 것을 큐라고 한다.

 

아마 영국식 영어를 하던 사람은 줄을 설 때 line이라 하지 않고 queue라고 주로 말을 하게 될 텐데

 

이때 queue가 줄, 즉 선입선출 - 먼저 온 사람이 먼저 입장하는 것이다.

 

# 5-2 DFS,BFS 큐

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7) # 5 2 3 7
queue.popleft() # 2 3 7

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

print(queue)

큐에서 중요한 점은

 

from collections import deque

파이썬에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하면 좋다.

 

대부분 코딩 테스트에서 collections 모듈과 같은 기본 라이브러리를 허용하기 때문에 안심하고 사용해도 좋다.

 

입력은 동일하게 append로 추가하며

 

삭제할 때는 popleft()를 이용해서 맨 앞에 추가된 데이터를 지운다.