Priority Queue

1. Priority Queue

• 일반적인 Queue의 FIFO의 방식을 따르지 않고 우선순위에 따라 원소가 큐에서 꺼내지는 방식
• enqueue(item)시 우선순위에 따라 정렬 상태를 유지시킴

2. 연결 리스트를 이용한 Priority Queue 구현

from doubly_linked_list import *

class PriorityQueue:

    def __init__(self):
        self.queue = DoublyLinkedList()
    
    def __repr__(self):
        return str(self.queue)

    def __len__(self):
        return len(self.queue)

    def isEmpty(self):
        return len(self) == 0

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

    def dequeue(self):
        if self.isEmpty():
            raise IndexError('queue is empty')
        return self.queue.popAt(0)

    def peek(self):
        if self.isEmpty():
            raise IndexError('queue is empty')
        return self.queue[0].data

3. 테스트

print('# 우선 순위 큐 생성')
pq = PriorityQueue()
print('Queue:', pq)

print('\n# 3, 2, 4, 1 차례대로 삽입')
for item in [3, 2, 4, 1]:
    pq.enqueue(item)
    print('Queue:',pq)
    
print('\n# 원소 두번 꺼내기')
print('첫 번째 꺼낸 원소:', pq.dequeue())
print('두 번째 꺼낸 원소:', pq.dequeue())
print('남은 Queue:', pq)

print('\n# Peek')
print('Peek한 원소:', pq.peek())

# 우선 순위 큐 생성
Queue: []

# 3, 2, 4, 1 차례대로 삽입
Queue: [3]
Queue: [2, 3]
Queue: [2, 3, 4]
Queue: [1, 2, 3, 4]

# 원소 두번 꺼내기
첫 번째 꺼낸 원소: 1
두 번째 꺼낸 원소: 2
남은 Queue: [3, 4]

# Peek
Peek한 원소: 3

소스코드 : priority_queue.py