우선순위 큐(Priority Queues)

---

• 큐가 FIFO(First-In-First-Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
• 대표적인 응용 예로는 운영체제에서 CPU 스케줄러를 구현할 때 현재 실행할 수 있는 작업들 중 가장 우선순위가 높은 것을 골라 실행하는 알고리즘을 들 수 있다

우선순위 큐를 구현할 때 서로 다른 두가지 방식이 가능하다.

1. 큐에 원소를 넣을 때 (enqueue할 때) 우선순위 순서대로 정렬해 두는 방법

2. 큐에서 원소를 꺼낼 때 (dequeue할 때) 우선순위가 가장 높은 것을 선택하는 방법

• 두가지 방법 중 1번이 더 유리
• 만약 큐에 데이터 원소들이 우선순위가 상관없이 늘어서 있다고 하면 우선순위가 가장 높은 것을 디큐하려면 모든 원소들을 다 살펴보아야한다.
• 큐의 길이에 비례하는 정도의 시간이 소요가 된다.

우선순위를 구현할 때 서로 다른 두가지 재료를 이용할 수 있다.

• 선형배열을 이용
• 연결 리스트를 이용
• 우선 시간적으로 봤을 때 연결리스트를 이용하는것이 유리
• 메모리를 차지하는 양을 보면 선형배열이 공간을 덜 차지

우선순위 큐 구현

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None

class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None

    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s

    def getLength(self):
        return self.nodeCount

    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result

    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result

    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr

    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True

    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)

    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data

    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)

    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail

        self.nodeCount += L.nodeCount

class PriorityQueue:
    # 양방향 연결리스트를 이용하여 빈 큐를 초기화
    def __init__(self, x):
        self.queue = DoublyLinkedList()
    
    # 크기를 반환
    def size(self):
        return self.queue.getLength()

    # 비어있는가?
    def isEmpty(self):
        return self.size() == 0
        
    # 데이터 삽입 연산
    def enqueue(self, x):
        newNode = Node(x)
        
        # 처음 시작하는 위치 head에서 시작
        curr = self.queue.head
        
        # 끝까지 가지 않을 조건 && 우선순위를 비교하는 조건
        while curr.next != self.queue.tail and x < curr.next.data :
            curr = curr.next
        
        # 양방향 연결리스트를 이용해 삽입! 
        self.queue.insertAfter(curr, newNode)
        
        # [주의] 양방향 연결리스트의 getAt()메서드를 이용하지 않는다.
        # why? 
    
    # 데이터 삭제 연산
    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    # 첫번째 데이터 반환
    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data

[실습] 우선순위 큐의 enqueue 연산 구현

문제

어서와! 자료구조와 알고리즘은 처음이지? 16강 실습: 우선순위 큐의 enqueue 연산 구현

문제 설명

앞선 강의에서 소개된 양방향 연결 리스트의 추상적 자료구조 구현인 클래스 DoublyLinkedList 를 이용하여 우선순위 큐의 추상적 자료구조인 클래스 PriorityQueue 의 구현을 완성하세요.

코드의 윗부분은 양방향 연결 리스트를 이용하기 위한 클래스 Node 와 DoublyLinikedList 의 구현입니다. 그대로 둔 채, 아래에 있는 class PriorityQueue 의 메서드들 중 enqueue() 메서드의 구현을 위한 빈 칸 채우기만 완성하면 됩니다.

[참고] 함수 solution() 은 이 클래스의 구현과는 관계 없는 것이지만, 문제가 올바르게 동작하는 데 필요해서 넣어 둔 것이니 무시해도 좋습니다. 또한, 실행 을 눌렀을 때 예시 테스트 케이스를 통과한다고 출력되는 것은 아무런 의미가 없습니다.

---

코드

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

def solution(x):
    return 0