[Python 자료 구조] 우선순위 큐 (Priority Queues)

(Removing Highest Priority Element, programiz)

 

 

#우선순위 큐 (Priority Queues)

 - 큐가 FIFO(First-In-First-Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식

 

 

#우선순위 큐 구현 방식

 - (1) Enqueue할 때 우선순위 순서를 유지하도록 vs (2) Dequeue할 때 우선순위 높은 것을 선택

 - (1) 가 더 유리, (2)는 모든 원소를 다 살펴보아야 함

 

 

#우선순위 큐 연상 구현

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)

 

    # 데이터 삭제 연산
    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

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

 

 

 

#우선순위 큐 연상 구현 예제

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

 

 

(솔루션 출처)

velog.io/@inyong_pang/16%EA%B0%95-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90Priority-Queues