[Python] 큐(Queue)

"5명 다 왔으니까 이제 롤 큐 돌리자." 의 큐는 이 큐이다.

1. 큐는 무엇인가?

큐는 스택과 같이 많이 쓰이는 자료구조 중 하나이다. 스택은 데이터의 입출력이 한 방향에서만 일어나서 가장 먼저 들어간 데이터가 가장 나중에 나온다면, 큐는 스택과 반대되는 성향을 가진다.

큐는 데이터의 입력 방향과 출력 방향이 따로 존재한다. 입력 방향으로 가장 먼저 들어간 데이터가 출력 방향으로 가장 일찍 나온다. 즉 가장 먼저 들어온 데이터를 가장 먼저 처리하는 구조이다. 그래서 큐는 선입선출 (FIFO, First In First Out) 자료구조라고 불린다.

2. 사용법

큐 자료구조에서 사용되는 대표적인 함수 3가지를 들 수 있다.

• enqueue
• dequeue
• peek

2-1. enqueue

enqueue는 큐에 데이터를 넣는 작업을 의미한다. 입력은 큐의 뒷부분에서만 실행된다.

2-2. dequeue

dequeue는 큐에서 가장 앞에 있는 데이터를 제거하면서 반환하는 작업을 담당한다. 출력은 큐의 맨 앞부분에서만 실행된다. return 값이 있는 함수이기 때문에 큐에서 꺼낸 값을 변수에 저장할 수 있다. 동시에 큐에서는 제거된다.

2-3. peek

peek은 큐에서 가장 앞에 있는 데이터가 어떤 것인지 확인하는 작업을 담당한다.

그럼 python에서는...? 🙄

스택은 python에서 list 자료형으로 구현이 가능했다. 큐도 list로 구현은 가능하지만, 효율성 측면에서 list를 사용하는 것은 권장하지 않는다.
(참고 : pop 함수에 관한 고찰)

그럼 다른 언어처럼 큐를 직접 구현해야 되냐! 그것도 아니다. python에서는 훌륭한 내부 라이브러로 큐를 제공하고 있는데, 바로 deque이다.

3. deque

deque은 Double-Ended Queue의 약자로, 덱이라고 읽는다. python에서는 deque이라는 라이브러리 형태로 큐 자료구조를 제공하고 있다. collections모듈의 deque를 import하면 큐와 내장함수들을 사용할 수 있다.

from collections import deque

3-1. append

append는 큐에 요소를 추가하는 함수이다. 큐의 오른쪽, 즉 맨 뒤에 추가한다.

3-2. popleft

popleft는 맨 왼쪽, 즉 가장 앞에 있는 요소를 제거하면서 반환하는 함수이다.

3-3. peek?

deque에도 peek 함수는 따로 존재하지 않는다. 대신 list를 인덱싱하는 것 처럼 특정 인덱스의 요소를 확인할 수 있다. 단, deque에서는 슬라이싱을 사용할 수 없다. 강제로 슬라이싱하면 에러가 발생한다.

from collections import deque

q = deque([1, 2, 3, 4, 5])
q.append(10)
print(q) 		# deque([1, 2, 3, 4, 5, 10])

value = q.popleft()
print(value) 	# 1
print(q)		# deque([2, 3, 4, 5, 10])

print(q[0])		# 2
print(q[-1])	# 10
print(q[1:3])	# TypeError: sequence index must be integer, not 'slice'

왜 요소를 제거하는 함수 이름이 pop이 아니고 popleft야? 그럼 popright도 있는거아닌ㄱ

python에서 제공해주는 deque은 Double-Ended Queue의 약자라고 했다. 그리고 큐의 가장 왼쪽에 있는 요소를 제거하는 함수는 popleft이다.

눈치챈 사람도 있겠지만, deque은 사실 한쪽에서만 입력이 일어나고 한쪽에서만 출력이 일어나는 구조가 아니다. 양쪽에서 입출력이 모두 가능한 자료구조이다. 양방향 입출력이 가능한 자료구조를 우리는 왼쪽에서만 입력을 하고(append), 오른쪽에서만 출력이 일어나게 함으로써(popleft) 큐처럼 사용을 하고 있는 것이다.

3-4. appendleft

관습적으로 사용하던 append의 대항마가 나타났다. appendleft는 큐의 맨 왼쪽에 요소를 추가하는 함수이다. 물론 deque에만 사용이 가능하고, list에는 사용할 수 없다.

3-5. pop

pop은 deque의 맨 오른쪽에 있는 요소를 제거하면서 반환하는 함수이다. 아쉽지만 popright가 아ㄴ

from collections import deque

q = deque([1, 2, 3, 4, 5])
q.appendleft(10)
print(q)			# deque([10, 1, 2, 3, 4, 5])

value = q.pop()
print(value)		# 5
print(q)			# deque([10, 1, 2, 3, 4])

💡 popleft와 appendleft 함수는 모두 맨 왼쪽, 즉 가장 앞에 있는 0번 인덱스에서 작업이 일어난다. list였으면 이런 작업들은 효율성이 좋지 않았겠지만, deque는 내부적인 인덱스 연산이 list와 다르게 일어나기 때문에 list보다 훨씬 좋은 효율을 낸다.

이외에 deque에서 유용하게 사용할 수 있는 함수들이 있다.

3-6. rotate

rotate는 deque를 n번 회전시키는 함수이다. 인자로 받은 n이 양수이면 오른쪽으로 회전하고, 음수이면 왼쪽으로 회전한다.

from collections import deque

q = deque([1, 2, 3, 4, 5])
q.rotate(3)
print(q)		# deque([3, 4, 5, 1, 2])

q.rotate(-3)
print(q)		# deque([1, 2, 3, 4, 5])

3-7. maxlen

deque를 초기화할 때 큐의 최대 길이를 지정할 수 있다. 최대 길이 만큼 요소가 저장되어 있는 상태에서 요소를 추가하면, 그 반대 방향에 있는 요소가 제거된다. maxlen의 길이를 초과했을 때, maxlen만큼의 길이를 보존하는 것이다.

from collections import deque

q = deque([1, 2, 3, 4, 5], maxlen=5)
q.append(6)
print(q) # deque([2, 3, 4, 5, 6], maxlen=5)

끗