[자료구조][파이썬/Python] 큐(Queue)

큐(Queue)

• 큐(Queue)는 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다.
• 기본적으로 값을 저장하는 연산 enqueue와 저장된 값을 꺼내는 연산 dequeue가 제공되어야 한다.
• 부가적으로 큐의 길이를 반환하는 연산이나 큐가 비어있는지 확인하는 연산, 큐의 가장 아래에 있는 값이 무엇인지 확인하는 연산을 추가할 수도 있다.
• 가장 먼저 들어간 값이 가장 먼저 나오게 되는 원칙(First In First Out, FIFO)을 따른다.

 

클래스로 구현하기 & 리스트 메서드 활용하기

스택과 큐는 매우 유사한 형태이고 따르고 있는 원칙만 약간 달라 설명도, 특징도, 구현하는 방식도 유사한 점이 많다. 그래서 큐도 마찬가지로 클래스로 구현하는 일반적인 방법은 (1) 양방향 연결리스트(Doubly Linked List)를 통해 구현하는 방법, (2) Python 내 리스트 메서드를 활용하는 방법이 존재한다. 다만, 큐 또한 실제로 코딩테스트 문제를 풀 때 어떻게 빠르게 사용할 수 있을지에 초점을 둘 것이기 때문에 클래스로 구현하는 것은 생략하도록 하겠다. 

 

스택과 달리 큐에서 유의할 점은, 리스트 자료구조로 큐를 대체할 경우 dequeue를 실행할 때 O(n) 만큼의 시간이 발생한다는 것이다. 스택에서는 리스트의 맨 끝 원소를 pop하기만 하면 됐는데, 큐에서는 리스트의 맨 앞 원소를 pop한 후 그 뒤에 있는 원소들을 모두 한 칸씩 앞으로 당겨와야 한다. 그래서 리스트에 들어있는 원소의 개수 n 만큼의 시간이 소요된다. 반면 양방향 연결리스트로 큐를 구현할 경우 dequeue를 할 때 O(1) 만큼의 시간이 발생한다는 이점이 존재한다. 하지만 큐 중간에 있는 요소를 수정하거나 삭제, 혹은 요소를 삽입하고자 할 때에는 리스트로 구현한 큐가 더 좋은 효율을 보인다. 그러니 목적에 알맞는 방식으로 큐를 구현하면 효율이 더 좋아질 것이다.

 

Python의 모듈을 이용하기

python 내장 모듈에서는 큐를 지원하는 Queue라는 것이 있다. Stack에 대한 포스팅을 할 때 말했다시피, 이건 스레드 환경을 위해 만들어진 모듈이기 때문에 일반적인 상황에서 쓰는 것은 권장하지 않는다. 그래도 혹시 한 번 보고 싶다면 여기서 확인해보자.

 

대신 다른 모듈들이 존재하는데, collections의 deque와 pythonds의 queue이다. pythonds는 Stack을 설명할 때도 언급했었지만, 이걸 설치해서 쓰나 직접 리스트를 만들어서 쓰나 별 차이가 없다. 오히려 더 헷갈릴 수도 있다고 생각된다. 그래서 queue를 설명할 때에는 pythonds에 대한 설명은 생략하고자 한다.

 

collections.deque는 내부적으로 구현하기 귀찮은 양방향 연결리스트(Doubly Linked List)로 구성되어 있어서, 양방향 연결리스트로 구현된 큐가 필요하다고 생각되면 유용하게 활용할 수 있다. 특히 큐 안에 있는 값을 반복적으로 찾거나, 큐 중간에 값을 삽입, 제거, 변경하는 일이 아니고 단순히 enqueue와 dequeue만을 반복하기 위한 큐라면 리스트로 큐를 구현하기 보다는 collections.deque를 쓰는 것이 더 효율적이다. 

 

코드를 통해 deque의 파워를 확인해보자.

from collections import deque

d = deque()
print(type(d)) # <class 'collections.deque'>


# enqueue의 기능을 하는 연산 : append
for i in range(10):
    d.append(i)
print(d) # deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])


# enqueue를 리스트 왼쪽에서부터 할 수도 있다 : appendleft
d.appendleft(10)
print(d) # deque([10, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9])


# 큐 중간에 요소를 삽입을 하는 연산 : insert
d.insert(5, 11)
print(d) # deque([10, 0, 1, 2, 3, 11, 4, 5, 6, 7, 8, 9])


# 큐 왼쪽/오른쪽에 iterable한 객체를 통째로 append 하여 연장시키는 연산 : extendleft / extend
d.extend([0, 0, 0])
print(d) # deque([10, 0, 1, 2, 3, 11, 4, 5, 6, 7, 8, 9, 0, 0, 0])
d.extendleft([0, 0, 0])
print(d) # deque([0, 0, 0, 10, 0, 1, 2, 3, 11, 4, 5, 6, 7, 8, 9, 0, 0, 0])


# 스택의 pop처럼 리스트 오른쪽에서부터 요소를 제거하며 return하는 연산 : pop
for i in range(10):
    d.pop()
print(d) # deque([0, 0, 0, 10, 0, 1, 2, 3])


# 큐의 dequeue처럼 리스트 왼쪽에서부터 요소를 제거하며 return하는 연산 : popleft
for i in range(3):
    d.popleft()
print(d) # deque([10, 0, 1, 2, 3])


# 작업을 완료한 후에는 일반적인 리스트처럼 이용할 수도 있다
print(list(d)) # [10, 0, 1, 2, 3]

위 코드에는 쓰지 않았지만 clear, copy, count, reverse, rotate, maxlen과 같은 연산들이 더 존재한다. 상당히 유용한 기능들을 수행하는데 큐인듯 리스트인듯 애매한 녀석이다. 그리고 예시를 적으려고 쓰다 보니 이 collections.deque를 이용하면 pop 연산도 존재하니 스택처럼 써도 괜찮다는 생각이 든다.