16강: 우선순위 큐(Priority Queues)

강의

"우선순위 큐"는 선입선출 방식이 아닌 우선순위에 따라 큐에서 빠져나오는 방식입니다.

 

예시로는 운영체제의 CPU 스케줄러가 있습니다.

 

구현

1. 방식 선택

• Enqueue 할 때 우선순위 순서를 유지 : 시간적으로 유리함
• Dequeue 할 때 우선순위 높은 것을 선택

2. 자료구조 선택

• 배열 : 공간적으로 유리함
• 연결 리스트 : 시간적으로 유리함

 

 

16강 실습: 

⭐ 효율성을 높이는 함수를 선택하는 문제!

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