Queue

FIFO(First In First Out) 기반의 자료구조

데이터를 추가한 순서대로 제거할 수 있기 때문에

비동기 메세징(asynchronous messaging), 스트리밍(streaming), 너비 우선 탐색(breath first search) 등에서 널리 응용

 

1. list를 활용한 Queue -> 데이터 삽입, 삭제 시 O(1), 무작위 접근 시 O(n)

>>> queue = [4, 5, 6]
>>> queue.append(7)
>>> queue.append(8)
>>> queue
[4, 5, 6, 7, 8]
>>> queue.pop(0)
4
>>> queue.pop(0)
5
>>> queue
[6, 7, 8]


# 방향을 반대로 하려면
>>> queue = [4, 5, 6]
>>> queue.insert(0, 3)
>>> queue.insert(0, 2)
>>> queue
[2, 3, 4, 5, 6]
>>> queue.pop()
6
>>> queue.pop()
5
>>> queue
[2, 3, 4]

 

2.Deque (Double-Ended Queue) 양방향 큐 -> 데이터 삽입, 삭제 시 O(n), 무작위 접근 시 O(1)

>>> from collections import deque
>>>
>>> queue = deque([4, 5, 6])
>>> queue.append(7)
>>> queue.append(8)
>>> queue
deque([4, 5, 6, 7, 8])
>>> queue.popleft()
4
>>> queue.popleft()
5
>>> queue
deque([6, 7, 8])

>>> queue = deque([4, 5, 6])
>>> queue.appendleft(3)
>>> queue.appendleft(2)
>>> queue
deque([2, 3, 4, 5, 6])
>>> queue.pop()
6
>>> queue.pop()
5
>>> queue
deque([2, 3, 4])

 

 

3. 우선순위 큐(Priority Queue) *** 코딩 테스트에서는 힙큐(Heapq) 라이브러리를 사용해서 시간 단축

데이터를 추가한 순서대로 제거하는 선입선출(FIFO) 특성을 가진 일반적인 큐의 자료구조와 달리,

데이터 추가는 어떤 순서로 해도 상관이 없지만, 제거될 때는 가장 작은 값을 제거하는 독특한 특성을 지닌 자료구조

from queue import PriorityQueue

# 우선순위 큐의 디폴트 사이즈는 무한대
que = PriorityQueue()
# 특정 최대 크기를 가진 우선순위 큐가 필요하다면 maxsize 속성
que = PriorityQueue(maxsize=8)

# 원소 추가 = put 메소드
que.put(4)
que.put(1)
que.put(7)
que.put(3)

# 원소 제거 = get 메소드
print(que.get())  # 1
print(que.get())  # 3
print(que.get())  # 4
print(que.get())  # 7

# 다른 기준으로 정렬되기 원하는 경우
que.put((3, 'Apple'))
que.put((1, 'Banana'))
que.put((2, 'Cherry'))

print(que.get()[1])  # Banana
print(que.get()[1])  # Cherry
print(que.get()[1])  # Apple


## heapq를 활용하여 문제 풀기
import heapq

def solution(scoville, K):
    heapq.heapify(scoville)  # 리스트를 힙으로 변환
    answer = 0

    while len(scoville) > 1 and scoville[0] < K:
        first = heapq.heappop(scoville)  # 가장 맵지 않은 음식
        second = heapq.heappop(scoville)  # 두 번째로 맵지 않은 음식
        
        new_scoville = first + (second * 2)  # 새로운 스코빌 지수
        heapq.heappush(scoville, new_scoville)  # 힙에 새 스코빌 지수 삽입
        answer += 1

    # 모든 음식의 스코빌 지수가 K 이상인지 확인
    if scoville[0] < K:
        return -1
    return answer