Python 63 - DFS/BFS (2) 꼭 필요한 자료구조 기초_[큐]

큐

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

 

큐에서 일련의 연산을 수행해보자. 큐는 다음 그림과 같이 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다. 초기 단계에서 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()를 차례대로 실행해보자.

 

 

이를 파이썬 코드로 표현하면 다음과 같다.

큐의 앞쪽 원소부터 출력하는 코드와 뒤쪽 원소부터 출력하는 내용을 모두 포함하였다.

 

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
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)    # 나중에 들어온 원소부터 출력


출력값
deque([3, 7, 1, 4])
deque([4, 1, 7, 3])

 

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

deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것 보다 더 간단하다. 더불어 대부분의 코딩 테스트에서는 collections 모듈과 같은 기본 라이브러리 사용을 허용하므로 안심하고 사용해도 괜찮다. 또한 deque객체를 리스트 자료형으로 변경하고 한다면 list()메서드를 이용하자 위 소스코드에서는 list(queue)를 하면 리스트 자료형이 반환된다.

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding