큐 level 3 (우선순위 큐, Priority Queue)

1) 우선순위 큐

  - 큐(Queue)가 FIFO(선입선출) 방식을 따르지 않고 원소들의 갖고 있는 우선순위에 따라 나오는 자료구조

  - 대표적인 예로 '운영체제의 CPU 스케쥴러'가 있다

  - 우선순위 큐는 두가지 방식으로 구현 가능하다

• Enqueue 시 우선순위를 유지하도록 한다
• Dequeue 시 우선순위가 높은 것을 선택하도록 한다

      → 위 두가지 방식 중 'Enqueue 시 우선순위를 유지' 가 미세하게 유리하다. 왜냐하면 Dequeue 시 우선순위가 높은 것을 선택하도록 할 경우 모든 데이터에 대하여 다 살펴봐야하기 때문에 큐의 길이가 길어질 경우 시간적으로 불리하다. 

 

  - 우선순위 큐는 선형 배열(Array, list)과 연결 리스트(linked list)를 이용하여 구현 가능하다

      → 시간 소요 측면에서 삽입 및 삭제 연산을 유연하게 사용가능한 연결 리스트가 유리하나 메모리 사용 측면에서 선형 배열이 더 유리하다. 하지만, 설계시 보통 시간적으로 유리한 것이 우선시 된다

 

2) 연결 리스트(Doubly Linked List)를 이용한 Queue 자료구조 및 연산 구현

 

class PriorityQueue:
    def __init__(self):
        self.queue = DoublyLinkedList()  # 양방향 연결 리스트를 이용하여 빈 큐 초기화

    def size(self):
        return self.queue.getLength()

    def isEmpty(self):
        return self.size() == 0

    def enqueue(self, x):
        newNode = Node(x)  
        curr = self.queue.head  
        while curr.next != self.queue.tail and x < curr.next.data:
            curr = curr.next  
        self.queue.insertAfter(curr, newNode)  

    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())
      
    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data