프로그래머스 강의_16

우선순위 큐(Priority Queues)

• 큐가 FIFO 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

• 예) Enqueue 작은 수가 우선순위가 높다고 가정
  6 7 3 2 => 큐의 길이는 4
  예) Dequeue
  2 3 6 7 => 우선순위대로 빠져나온다.

  우선순위 큐의 활용

• 운영체제의 CPU 스케줄러

• 서로 다른 두 가지 방식이 가능하다.
  (1) Enqueue 할 때 우선순위 순서를 유지하도록
  (2) Dequeue 할 때 우선순위 높은 것을 선택
  ===> (1) 번이 좀 더 유리하다.

우선순위 큐의 구현

• 서로 다른 두 가지 재료를 이용할 수 있다.
  (1) 선형 배열
  (2) 연결 리스트

우선순위 큐의 초기화

from doublylinkedlist import Node,DoublyLinkedList

## 양방향 연결 리스트를 이용하여 빈 큐를 초기화
class PriorityQueue:
   def __init__(self,x):
       self.queue = DoublyLinkedList()
   # (주의) 양방향 연결리스트의 getAt()메서드를 이용하지 않음!
    def enqueue(self, x):
       newNode = Node(x)
       curr = self.queue.head
       while curr.next.data != None and x < curr.next.data:
           curr = curr.next
       self.queue.insertAfter(curr, newNode)

==> 우선순위 큐는 enqueue만 바꿔주면 나머지 함수는 이전 강의에 있는 함수를 사용하면 된다.