큐(Queue) 자료구조 이해(+ Python)

본 포스팅에서는 큐(Queue) 자료구조에 대해 알아봅니다.

📚 목차

1. 큐(Queue) 자료구조란?
2. 큐 동작 예시
3. 큐 구현(Python)

1. 큐(Queue) 자료구조란?

큐 자료구조는 선입선출(先入先出, First In First Out, 줄여서 FIFO) 구조로 흔히 놀이공원 내 놀이기구 대기줄에 비유합니다(그림 1 참고).
즉, 놀이기구 대기줄에 먼저 선 사람(데이터 입력)이 먼저 놀이기구를 타는(데이터 출력/제거) 방식입니다(단, 새치기는 없다고 가정).

그림 1.  큐(queue) 자료구조 설명.

큐 자료구조는 아래 2가지 핵심적인 함수로 동작합니다.

• 데이터 삽입(append)
• 데이터 삭제(popleft)

큐 자료구조를 사용할 때는 오버플로우(Overflow)와 언더플로우(Underflow)가 발생하지 않도록 유의해야 합니다.

• 오버플로우(Overflow): 큐 자료구조에 저장할 수 있는 데이터의 크기를 초과한 상태에서 데이터 삽입을 수행할 때 발생
• 언더플로우(Underflow): 큐 자료구조에 데이터가 전혀 없는 상태에서 데이터 삭제를 수행할 때 발생

2. 큐 동작 예시

이제 큐 자료구조의 동작 방식을 살펴보겠습니다. 큐 자료구조는 그림 2 와 같이 입구와 출구가 모두 뚫려있는 터널 형태로 표현됩니다.

그림 2.  큐 자료구조 및 함수 시각화

그림 3 상단에 적힌 큐 자료구조 연산의 동작을 예시로 살펴보겠습니다.

3. 큐 구현(Python)

위에서 살펴본 큐 자료구조의 동작은 파이썬 내 collections 모듈에서 제공하는 deuque 자료구조를 활용해 표현할 수 있습니다.
deque는 데이터 입출력 속도가 리스트(list) 자료형 보다 효율적이며 queue 라이브러리를 이용하는 것보다 간단합니다.

from collections import deque
# 큐(Queue) 자료구조 구현을 위한 deque 라이브러리 사용
queue = deque()

이에, 먼저 큐 자료구조 구현을 위해 deque 라이브러리를 가져와 줍니다.

# 삽입(3) - 삽입(5) - 삽입(1) - 삽입(9) - 삽입(7) - 삭제() - 삭제() - 삽입(4) - 삽입(8) - 삭제()
queue.append(3) # 3 삽입
queue.append(5) # 5 삽입
queue.append(1) # 1 삽입
queue.append(9) # 9 삽입
queue.append(7) # 7 삽입
queue.popleft() # 3 삭제
queue.popleft() # 5 삭제
queue.append(4) # 4 삽입
queue.append(8) # 8 삽입
queue.popleft() # 1 삭제

print(queue) # 먼저 입력된 데이터부터 차례대로 출력
print(queue.reverse()) # 나중에 입력된 데이터부터 차례대로 출력

큐 자료구조에서 데이터를 입력할 때는 append 함수를 이용하며 데이터를 삭제할 때는 popleft 함수를 사용해 줍니다.

실행 결과

deque([9, 7, 4, 8])
deque([8, 4, 7, 9])

📚 참고할만한 포스팅

자료구조#1: 스택(Stack)에 대해 알아보자(+ Python)

---

포스팅 내용에 오류가 있을 경우 아래에 댓글 남겨주시면 감사드리겠습니다.
그럼 오늘도 즐겁고 건강한 하루 보내시길 바랍니다.
고맙습니다 :)