우선순위 큐 (Priority Queue)
큐가 FIFO (First-In First-Out) 방식을 따르지 않고 원소들의 우선순위에 따라 큐에서 빠져나오는 방식
우선순위 큐의 활용
- 운영체제의 CPU 스케줄러
우선순위 큐의 구현
서로 다른 두 가지 방식이 가능할 듯:
(1) Enqueue 할 때 우선순위 순서를 유지하도록
(2) Dequeue 할 때 우선순위 높은 것을 선택
-> 어느 것이 더 유리할까? 1번
서로 다른 두 가지 재료를 이용할 수 있음:
(1) 선형 배열 이용
(2) 연결 리스트 이용
-> 어느 것이 더 유리할까?
- 시간면에선 (2)
- 메모리면에선 (1)
-> 시간적으로 유리한 걸 택하는 경우가 많음
실습 과제 - 우선순위 큐의 enqueue 연산 구현
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):
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 newNode.data < 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
* 프로그래머스의 '어서와! 자료구조와 알고리즘은 처음이지?' 강의를 듣고 정리하였습니다.
'알고리즘 강의' 카테고리의 다른 글
[알고리즘 강의] 파트18. 이진 트리(Binary Trees) (0) | 2021.07.21 |
---|---|
[알고리즘 강의] 파트17. 트리(Trees) (0) | 2021.07.21 |
[알고리즘 강의] 파트15. 환형 큐(Circular Queues) (0) | 2021.07.19 |
[알고리즘 강의] 파트14. 큐(Queues) (0) | 2021.07.17 |
[알고리즘 강의] 파트13. 스택의 응용: 후위 표기 수식 계산 (0) | 2021.07.17 |