[자료구조] 큐queue 정의 및 데크deque와 힙큐heapq 사용법

큐는 시퀀스의 한쪽 끝에는 엔티티를 추가하고, 다른 반대쪽 끝에는 제거할 수 있는 엔티티 컬렉션이다.

 

큐는 FIFO(First-In-First-Out) 선입선출의 구조를 가진다. 간단히 말하면 선착순이다. 맛집에서 줄을 서는 것과 같다. 

 

큐는 스택과 마찬가지로 리스트로 큐의 모든 연산을 구현할 수 있다. 하지만 동적 배열인 리스트는 큐연산에 적합하지 않아서 데크(deque)라는 별도의 자료형을 써야 좋은 성능을 낼 수 있다. 

 

 

데크 : 더블엔디드큐(Double Ended Queue)의 줄임말로, 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상자료형이다. 

 

<데크의 구현>

데크는 pop( )과 popleft( ) 모두 시간복잡도 O(1)을 가지므로 매우 성능이 좋은 자료형이다.

 

import collections

q = collections.deque()

## add element
q.append(1)
q.append(2)
q.append(3)


## pop() and popleft()
print(q)
print(q.pop())
print(q.popleft())

[1,2,3]
3
1


## insert
q = collections.deque([1,2,3])
q.insert(1,5) ## idx, value
print(q)
[1,5,2,3]

 

 

우선순위 큐 : 큐/스택과 같은 추상자료형과 유사하나 각 요소의 우선순위와 연관되어 있다.

 

- 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형

- 정렬 알고리즘을 사용하면 우선순위 큐를 만들 수 있다.

- 최단 경로를 탐색하는 다익스트라 알고리즘 등 우선순위 큐는 다양한 분야에 활용되며 힙 자료구조와도 관련이 깊다.

 

우선순위 큐에는 항상 heapq 모듈을 사용한다.

최소 힙을 지원하며 pop( )을 할 경우 가장 작은 원소부터 추출된다.

>>import heapq

>>heap = []

>>## add element , time complexity : O(logN)
>>heapq.heappush(heap, 3)
>>heapq.heappush(heap, 2)
>>heapq.heappush(heap, 4)
>>heapq.heappush(heap, 1)


## pop element, time complexity : O(logN)
>> for _ in range(4):
>>    print(heapq.heappop(heap)
1
2
3
4


## list to heap
>>heap = [5,2,4,3]
>>heapq.heapify(heap)
>> for _ in range(4):
>>    print(heapq.heappop(heap)
2
3
4
5

 

* 최대 힙 구현하기

>>nums = [5,8,7,6,9]
>>heap = []
>>for num in nums:
>>    heapq.heappush(heap, (-num,num))  
>>
>>while heap:
>>    print(heapq.heappop(heap)[1])  
9
8
7
6
5