[파이썬/python] 큐 (Queue)

큐(Queue)는 스택(Stack)과 유사하지만 반대의 성격을 지닌다.

스택은 LIFO(Last In First Out)의 형태로 마지막에 들어간 데이터가 첫 번째로 나오는 구조이고

큐는 FIFO(First In First Out)의 형태로 첫 번째 들어간 데이터가 첫 번째로 나오는 구조이다.

 

일차원의 선형 자료구조인 큐는 값을 저장하는 연산 enqueue와 값을 꺼내는 연산 dequeue가 있어야한다.

큐의 종류로는 선형 큐(Queue), 원형 큐(Circular Queue), 우선순위 큐(Priority Queue)가 있다.

 

선형 큐는 막대모양의 큐로 크기가 제한되어 있다.

그렇기 때문에 빈 공간을 사용하려면 모든 자료를 꺼내거나 자료를 한칸씩 앞으로 옮겨야한다는 단점이 있다.

 

선형 큐의 단점을 보완한 것이 원형 큐다.

head가 큐의 맨 끝에 닿으면 큐의 맨 앞으로 자료를 보내어 원형으로 연결하는 방식이다.

 

 

파이썬으로 구현하기

리스트로 구현하는 것도 가능하지만 리스트로 구현하면 선형 큐의 단점이 그대로 드러난다.

따라서 1. collection.deque / 2. Queue 모듈 중 하나를 이용하는게 가장 효율적이다.

 

1. collection.deque

deque는 double-ended queue의 줄임말로 앞 뒤 양방향에서 데이터를 처리할 수 있다.

from collections import deque


# 1. append(x)
deq = deque([1, 2, 3])
deq.append(4)
>>> deq = [1, 2, 3, 4]


# 2. appendleft(x)
deq = deque([1, 2, 3])
deq.appendleft(0)
>>> deq = [0, 1, 2, 3]


# append()와 extend()의 차이
deq.append('def')
>>> deq = ['a', 'b', 'c', 'def']
deq.extend('def')
>>> deq = ['a', 'b', 'c', 'd', 'e', 'f']


# 3. extend(i)
deq = deque(['a', 'b', 'c'])
deq.extend('de')
>>> deq = ['a', 'b', 'c', 'd', 'e']


# 4. extendleft(i)
deq = deque(['a', 'b', 'c'])
deq.extendleft('de')
>>> deq = ['e', 'd', 'a', 'b', 'c']


# 5. pop()
deq = deque([1, 2, 3])
deq.pop()
>>> deq.pop() -> 3
>>> deq = [1, 2]


# 6. popleft()
deq = deque([1, 2, 3])
deq.popleft()
>>> deq.popleft() -> 1
>>> deq = [2, 3]


# 7. rotate(n)
deq = deque([1, 2, 3, 4, 5])
deq.rotate(1)
>>> deq = [5, 1, 2, 3, 4]
deq = deque([1, 2, 3, 4, 5])
deq.rotate(-1)
>>> deq = [2, 3, 4, 5, 1]

• append(x) : 리스트에서의 사용과 마찬가지로 deque의 마지막(오른쪽)에 x를 추가한다.
• appendlieft(x) : 양방향 데이터 처리가 가능하므로 deque의 앞(왼쪽)에 x를 추가한다.
• extend(i) : 마지막(오른쪽)에 i를 추가한다. 각 요소를 하나씩 추가한다는 점에서 append와 차이가 있다.
• extendleft(i) : 앞(왼쪽)에 i를 추가한다.
• pop() : 리스트에서의 사용과 마찬가지로 deque의 마지막(오른쪽)에서부터 제거한다. 
• popleft() : deque의 앞(왼쪽)에서부터 제거한다.
• rotate(n) : 요소들을 n만큼 회전한다. 음수이면 왼쪽으로, 양수이면 오른쪽으로 회전한다.

2. Queue 모듈

Queue 모듈은 deque와 달리 방향성이 없기 때문에 간단하게 put과 get으로 구현할 수 있다.

주로 멀티스레딩 환경에서 유용하게 사용되며 여러 개의 스레드들이 동시에 수행해도 정상적으로 동작한다.

from queue import Queue
que = Queue([1, 2, 3])

que.put(4)
>>> que = [1, 2, 3, 4]

que.get()
>>>get() -> 1
>>>que = [2, 3, 4]

• put(x) : que에 x를 마지막(오른쪽)에 삽입한다.
• get() : que의 맨 앞(왼쪽)의 요소를 꺼낸다.