[Python] 자료구조 : 큐(Queue) 개념 및 사용

1. Queue란?

 

•  가장 먼저 입력 된 데이터가 가장 먼저 출력되는 구조이다.
• FIFO(First In, First Out)라고 부르기도 하며 반대로 LILO(Last In, Last Out)이라고 설명하기도 한다.
• 큐에서 알아두어야 할 용어가 있는데 Enqueue(인큐), Dequeue(디큐)이다.

-. Enqueue : 큐에서 데이터를 입력하는 기능

-. Dequeue : 큐에서 데이터를 꺼내는 기능

• 추가로 파이썬에서는 queue, deque라는 두가지 내장 모듈을 통해 큐를 구현할 수 있다. 

 

2. queue 내장 모듈을 통한 큐 구현 - 1 

 

•  파이썬에서는 queue라는 내장 모듈을 제공한다. 아래 예시로 든 그림을 통해 코드를 작성해보았다.
• put( )은 큐에 데이터를 넣을 때 사용하는 메서드, get( )은 큐에서 데이터를 꺼내는 메서드이다

 

 

<코드>

import queue

#큐 모듈의 큐 클래스 객체 선언
data = queue.Queue()
print(type(data))

#선언 된 큐 객체에 3개 데이터 입력하기 : 2,5,8
data.put(2)
data.put(5)
data.put(8)

#큐 객체에서 입력된 객체 하나씩 꺼내기 :FIFO
print(data.get())
print(data.get())
print(data.get())

 

<결과>

<class 'queue.Queue'>
2
5
8

 

숫자 2,5,8을 순서대로 넣고 get( )을 3번 하면 먼저 입력 된 순서대로 출력된다.

 

 queue 내장 모듈 내에는 기본적인 Queue( ) 클래스 외에도 LifoQueue( ), PriorityQueue( ) 클래스가 존재한다. 여기서 자세히 다루진 않겠지만 LifoQueue( )는 스택과 같은 LIFO 구조, PriorityQueue( ) 는 사용자가 우선순위를 지정한대로 데이터를 꺼낼 수 있는 구조라고 보면 될 것 같다.

 

 

2. deque 내장 모듈을 통한 큐 구현 - 2 

• 큐를 구현할려면 위의 예시처럼 queue 를 호출해도 되지만,
  일반적으로 deque를 사용하여 큐를 구현하는 것을 추천한다.
• append(): 큐의 끝에 요소를 추가
• popleft(): 큐의 맨 앞에서 요소를 제거하고 반환

from collections import deque

queue = deque()

# 큐에 요소 추가 (enqueue)
queue.append(1)
queue.append(2)
queue.append(3)

print(queue)  # deque([1, 2, 3])

# 큐에서 요소 제거 (dequeue)
front_element = queue.popleft()
print(front_element)  # 1
print(queue)  # deque([2, 3])

 

deque의 장점

• 양방향 작업의 효율성:
  • deque는 리스트와 달리 양쪽 끝에서 요소를 추가하거나 제거할 때 O(1)의 시간 복잡도를 가진다.
  • 리스트는 한쪽 끝에서만 O(1)의 시간 복잡도를 가지며, 다른 쪽 끝에서는 O(n)의 시간 복잡도를 가진다.
• 유연성:
  • deque는 스택과 큐의 모든 연산을 효율적으로 지원하므로, 상황에 따라 스택과 큐의 역할을 모두 수행할 수 있다.

 

deque의 주요 메서드

• 스택 연산
  • append(x): 스택의 맨 위에 요소 x를 추가
  • pop(): 스택의 맨 위에서 요소를 제거하고 반환
• 큐 연산
  • append(x): 큐의 끝에 요소 x를 추가
  • popleft(): 큐의 맨 앞에서 요소를 제거하고 반환
• 기타 메서드
  • appendleft(x): 큐의 맨 앞에 요소 x를 추가
  • popright(): 큐의 맨 끝에서 요소를 제거하고 반환

이와 같이 deque는 스택과 큐의 역할을 모두 효율적으로 수행할 수 있는 강력한 자료 구조이다.

 

deque와 queue 모듈의 비교

• 용도:
  • deque: 양방향에서 빠른 삽입 및 삭제가 필요한 경우에 사용된다. 큐와 스택의 연산을 모두 효율적으로 수행할 수 있다.
  • queue 모듈: 멀티스레딩 환경에서 안전하게 큐를 사용해야 하는 경우에 사용된다. 특히, 스레드 간의 작업을 조정할 때 유용하다.
• 성능:
  • deque: 대부분의 큐 및 스택 연산이 O(1)로 매우 효율적이다.
  • queue 모듈: 멀티스레딩을 지원하기 위해 추가적인 동기화가 필요하므로 약간의 성능 오버헤드가 있을 수 있다.
• 사용 편의성:
  • deque: 단순한 큐 및 스택 연산을 수행할 때 간단하고 직관적인 인터페이스를 제공한다.
  • queue 모듈: 멀티스레딩 환경에서 안전하게 사용할 수 있지만, 단일 스레드 환경에서는 다소 복잡할 수 있다.

결론

• 일반적인 큐 또는 스택 기능이 필요하고 단일 스레드 환경에서 사용한다면 collections.deque를 사용하는 것이 좋다.
• 멀티스레딩 환경에서 안전하게 큐를 사용해야 한다면 queue 모듈을 사용하는 것이 적합하다.