큐(Queue)

1. 큐

■ 큐는 먼저 들어온 데이터가 먼저 나가는 선입선출(First-in First-out, FIFO)의 특성을 갖는 자료구조이다.

■ 큐의 구조는 뒤에서 새로운 데이터가 추가되고 앞에서 데이터가 하나씩 삭제되는 구조이다.

예를 들자면, 어떤 서비스를 받을 때 먼저 온 순서대로, 가장 먼저 온 사람이 가장 먼저 서비스를 받고, 마지막에 도착한 사람은 맨 뒤에서 기다려야 한다.

큐의 구조

■ 즉, 큐의 삽입과 삭제는 FIFO 순서를 따른다. 삽입과 삭제 연산이 같은 쪽이 아니라 다른 쪽에서 일어난다. 큐가 스택과 다른 점이 바로 이 점이다.

■ 큐에서 삽입 연산을 하는 곳을 후단(rear),삭제 연산을 하는 곳을 전단(front)이라고 한다.

■ 다음 그림과 같이 삽입(enqueue)은 큐의 맨 뒤에 추가하고, 삭제(dequeue)는 큐의 맨 앞에 있는 항목을 꺼낸다.

 

2. 큐의 구현

■ 큐는 선형 큐와 원형 큐로 구현할 수 있다.

2.1 선형 큐

Queue ADT

● Queue( ): 비어 있는 새로온 큐를 만든다.
● isEmpty( ): 큐가 비어있으면 True, 그렇지 않으면 False를 반환.
● enqueue(x): 항목 x를 큐의 맨 뒤에 추가한다.
● dequeue( ): 큐의 맨 앞에 있는 항목을 꺼내 반환하고 삭제한다.
● peek( ): 큐의 맨 앞에 있는 항목을 반환한다.
● size( ): 큐의 모든 항목의 개수를 반환한다.
● clear( ): 큐의 모둔 항목을 비운다. 즉, 공백 상태로 만든다.

■ 큐를 구현하는 간단한 방법은 배열 구조인 파이썬의 리스트를 이용하는 것이다.

■ 리스트를 이용하면 리스트의 맨 앞을 큐의 front, 리스트의 맨 뒤를 큐의 rear로 설정하면 front와 rear을 위한 변수를 따로 만들 필요가 없다.

- 리스트를 이용하면 front는 항상 리스트의 인덱스 0, rear는 항상 리스트의 인덱스 -1에 위치하기 때문이다.

■ 따라서 큐가 비었는지 확인하는 메소드는 리스트의 길이가 0이면 True, 그렇지 않으면 False를 반환하게 만들면 된다.

class LinearQueue:
    def __init__(self):
        self.data = []
        
    def QIsEmpty(self):
        return len(self.data) == 0

■ 삽입 연산은 리스트의 맨 뒤, rear에 새로운 항목을 추가하는 것이므로 리스트의 append( ) 메소드를 사용하면 된다. 따라서 대부분의 삽입 연산은 상수 시간, $O(1)$의 시간 복잡도를 갖는다.

def QEnqueue(self,new_item):
    self.data.append(new_item)

■ 삭제 연산은 리스트의 맨 앞, front에서 항목을 하나 꺼내 이를 반환하고 삭제하면 된다. 

- 이는 리스트의 pop(0)을 이용하면 된다.

- 만약, 큐가 공백 상태일 경우 pop( ) 메소드를 사용하면 오류가 발생하므로 먼저 큐가 공백 상태인지 확인하고, 공백 상태가 아닌 경우만 pop(0)을 수행해야 한다.

def QDequeue(self):
    if self.QIsEmpty():
        raise Exception('Queue is empty.')
    else:
        return self.data.pop(0)

cf) 혹은 큐가 비어있지 않다면 바로 pop(0)을 할 수 있도록 다음과 같이 구현할 수 있다.

def QDequeue(self):
    if not self.QIsEmpty():
        return self.data.pop(0)

■ 이렇게 리스트의 맨 앞의 항목을 삭제하기 때문에, 삭제된 항목 이후의 모든 항목들이 한 칸씩 앞으로 이동해야 하므로, 삭제 연산의 시간 복잡도는 $O(n)$이 된다. 이 점이 선형 큐의 단점이다.

- 스택은 스택 상단(top)을 전단이 아닌 후단으로 설정하여 삽입과 삭제 연산의 시간 복잡도를 $O(1)$로 만드는 것이 가능했지만, 

- 큐는 가장 먼저 들어온 항목이 가장 먼저 나가고 마지막에 온 항목은 맨 뒤에 위치하는 구조이므로, 스택처럼 후단에서 삽입과 삭제 연산을 하는 것은 어렵다.

■ front의 항목을 반환하는 메소드는 '리스트 인덱스 0'을 이용하면 되고, 큐의 크기를 반환하는 메소드는 리스트의 len( )을 이용, 큐를 초기화시키는 메소드는 빈 리스트를 만들게 하면 된다.

def QPeek(self):
    if self.QIsEmpty():
        return None
    else:
        return self.data[0]
        
def QSize(self):
    return len(self.data)
    
def QClear(self):
    self.data = []
        
def QShow(self):
    if self.QIsEmpty():
        return None
    else:
        return self.data

- 위와 같은 기능들을 종합하면 Linear Queue의 클래스는 다음과 같다.

class LinearQueue:
    def __init__(self):
        self.data = []
        
    def QIsEmpty(self):
        return len(self.data) == 0
    
    def QEnqueue(self,new_item):
        self.data.append(new_item)
    
    def QDequeue(self):
        if self.QIsEmpty():
            raise Exception('Queue is empty.')
        else:
            return self.data.pop(0)
            
    def QPeek(self):
        if self.QIsEmpty():
            return None
        else:
            return self.data[0]
        
    def QSize(self):
        return len(self.data)
    
    def QClear(self):
        self.data = []
        
    def QShow(self):
        if self.QIsEmpty():
            return None
        else:
            return self.data

linear_Q = LinearQueue()
print(linear_Q.QIsEmpty()); print(linear_Q.QPeek());print(linear_Q.QShow())
```#결과#```
True
None
None
````````````

linear_Q.QDequeue()
```#결과#```
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
Cell In[124], line 1
----> 1 linear_Q.QDequeue()

Cell In[120], line 13, in LinearQueue.QDequeue(self)
     11 def QDequeue(self):
     12     if self.QIsEmpty():
---> 13         raise Exception('Queue is empty.')
     14     else:
     15         return self.data.pop(0)

Exception: Queue is empty.

linear_Q.QEnqueue(13)
linear_Q.QEnqueue(3)
linear_Q.QEnqueue(5)
linear_Q.QEnqueue(9)
linear_Q.QEnqueue(7)

print(linear_Q.QIsEmpty()); print(linear_Q.QShow())
```#결과#```
False
[13, 3, 5, 9, 7]
````````````

print(linear_Q.QPeek()); print(linear_Q.QSize())
```#결과#```
13
5
````````````

print(linear_Q.QDequeue(), linear_Q.QShow())
print(linear_Q.QDequeue(), linear_Q.QShow())
print(linear_Q.QDequeue(), linear_Q.QShow())
print(linear_Q.QDequeue(), linear_Q.QShow())
print(linear_Q.QDequeue(), linear_Q.QShow())
```#결과#```
13 [3, 5, 9, 7]
3 [5, 9, 7]
5 [9, 7]
9 [7]
7 None
````````````

- 큐를 삽입하면 위와 같이 삽입한 순서대로 나열된 것을 볼 수 있으며,

- 삭제를 하면 삽입한 순서대로 삭제되는 것을 볼 수 있다.

linear_Q.QEnqueue(10)
linear_Q.QEnqueue(20)
linear_Q.QEnqueue(30)

print(linear_Q.QShow())
```#결과#```
[10, 20, 30]
````````````

linear_Q.QClear()
print(linear_Q.QIsEmpty()); print(linear_Q.QPeek());print(linear_Q.QShow())
```#결과#```
True
None
None
````````````

 

2.2 원형 큐

■ 배열을 선형이 아닌 원형 구조, 즉 리스트의 전단과 후단이 연결된 원형 구조로 생각하면 선형 큐의 삭제 연산 시간 복잡도 $O(n)$을 $O(1)$로 만들 수 있다.

■ 단, 원형 큐는 기본적으로 리스트의 크기가 고정되야 한다. 그리고 선형 큐와 달리 front와 rear을 위한 변수가 필요하다.

■ front는 가장 최근에 삭제된 항목의 위치, rear은 큐가 가장 최근에 삽입된 항목의 위치를 저장하게 만들어야 하기 때문이다.

- 이렇게 처음과 끝을 이어 인덱스가 원형으로 움직이게 한다. 

- 인덱스 0부터 계속 증가하다 인덱스가 MAX_QSIZE - 1(= rear가 큐의 길이의 끝에 도달한 경우)이 되면, 다음 인덱스는 MAX_QSIZE가 아니라 다시 인덱스 0이 되게 하는 것이다.

- 이를 위해 front와 rear를 원형으로 회전(시계방향)시키는 방법은 'front <- (front + 1) % MAX_QSIZE', 'rear <- (rear + 1) % MAX_QSIZE'이며, 데이터를 삽입할 때는 rear, 삭제할 때는 front를 업데이트한다.

■ 이렇게 front와 rear의 위치를 계속 표시해야 하기 때문에 front와 rear 변수를 만들어서 사용한다.

■ 예를 들어 큐의 MAX_QSIZE = 5이고 항목 A, B, C, D, E를 이 큐에 삽입, 삭제한다면

- 초기 상태에서는 front와 rear는 모두 index 0에서 시작한다고 했을 때,

- 삽입 연산으로 A를 삽입할 경우, 항목 A의 index는 초기 상태 'rear = 0'이었으므로 위와 같이 rear = (0 + 1) % 5 = 1 계산되어 index 1에 위치하게 된다.

- 즉, enqueue( )를 하면, rear를 한 칸 움직이고 rear에 항목을 삽입한다.

- 반대로 dequeue( )를 하면, front를 한 칸 움직이고, 그 위치에 있는 항목을 삭제하면서 반환해 준다.

- rear가 끝에 도달한 상황에서 새로운 데이터 'E'를 삽입할 경우, 원형 큐의 특성으로 rear는 위와 같이 다시 시작으로 돌아간다.

■ 이렇게 인덱스만 순환적으로 변경된다면, 삭제 연산을 할 때 선형 큐처럼 항목들을 앞으로 한 칸씩 당길 필요가 없어진다. 삽입도 마찬가지이다.

■ 따라서 삽입과 삭제 연산의 시간 복잡도는 모두 $O(1)$이다.

■ 큐의 공백 상태는 front == rear인 경우이다. 즉, 같은 곳을 가리키기만 하면 공백 상태이다. 위의 초기 상태처럼 반드시 인덱스 0일 필요는 없다.

■ 그리고 원형 큐는 선형 큐와 달리 MAX_QSIZE를 고정하여 리스트가 모두 차서 더 이상 항목을 추가할 수 없는 경우, 이를 '포화 상태'라 한다.

- 원형 큐의 포화 상태는 큐가 꽉 찬 상태가 아닌, 한 칸을 비워둔 상태를 포화 상태라고 한다. 

- 다음 두 번째 그림과 같이 큐가 꽉 찬 상태라면 front == rear이므로 공백 상태와 구분이 안 된다. 

- 따라서 첫 번재 그림처럼 front가 rear보다 한 칸 앞에 있고, 이 한 칸이 비어 있는 경우를 '포화 상태'라고 정의한다.

■ 따라서 포화 상태는 'front == (rear + 1) % MAX_QSIZE'인 상태로 볼 수 있다.

■ 파이썬에서도 원형 큐를 구현하려면, 포화 상태를 파악하기 위해 큐의 크기를 미리 결정해야 한다. 즉, 리스트의 크기가 미리 결정되어야 한다. 이 크기를 다음과 같이 클래스 변수 또는 전역 변수로 설정한다.

class CircularQueue:
    _CAPACITY = 10
    
    def __init__(self):
        self.front = 0 # 큐의 전단 위치(index)
        self.rear = 0 # 큐의 후단 위치(index)
        self.data = [None] * CircularQueue._CAPACITY # 리스트의 크기를 미리 결정한 큐의 크기만큼 만든다

■ 또한 원형 큐는 크기가 고정되므로, 포화 상태가 있다는 것을 고려하여 큐가 비어있는지 확인하는 메소드 외에 큐가 포화 상태인지 확인하는 메소드가 필요하다.

- 큐의 공백 상태는 front == rear인지 확인하면 되고, 포화 상태는 front = (rear + 1) % MAX_QSIZE인지 확인하면 된다.

- 그리고 초기화의 경우 front는 큐에서 데이터를 꺼낸 위치를, rear은 큐에서 삽입한 위치를 가리키므로 큐가 비어 있다면 front와 rear이 같은 위치를 가리켜야 한다.

- 따라서 다음과 같이 공백 상태, 포화 상태, 초기화 메소드를 구현할 수 있다.

def QIsEmpty(self):
    return self.front == self.rear

def QIsFull(self):
    return self.front == (self.rear + 1) % CircularQueue._CAPACITY 
# CAPACITY 크기가 10이면, 마지막 인덱스는 9가 된다. 여기서 rear이 한 번 더 움직이면 9 + 1 = 10이 되는데,
# 인덱스 10은 없으므로 앞으로 돌아가기 위해 ''(9 + 1) % 10(MAX_QSIZE) = 0'이 되어 다시 index 0으로 돌아간다.

def QClear(self):
    self.front = self.rear # 큐의 front와 rear을 동일한 위치에 있도록 만들어, 큐가 비어 있다는 상태를 나타낸다.

■ 삽입 연산은 먼저 큐가 포화 상태인지 확인하고, 포화 상태라면 큐가 포화 상태라는 메시지를, 포화 상태가 아니라면 rear을 한 칸 옮기고, 그 rear의 위치에 데이터를 삽입하면 된다.

def QEnqueue(self, new_item):
    if self.QIsFull(): # 큐가 포화 상태라면
        raise Exception('Queue is full')
    else: # 큐가 포화 상태가 아니라면, rear을 업데이트
        self.rear = (self.rear + 1) % CircularQueue._CAPACITY 
        self.data[self.rear] = new_item

■ 삭제 연산은 큐가 공백 상태인지 확인하고, 공백 상태가 아니라면 큐의 front를 업데이트 하고 그 위치에 있는 항목, 즉 삭제한 항목을 반환한다.

def QDequeue(self):
    if self.QIsEmpty(): # 큐가 공백 상태
        raise Exception('Queue is empty')
    else: # 공백 상태가 아니라면
        self.front = (self.front + 1) % CircularQueue._CAPACITY  # front 업데이트
        return self.data[self.front] # 삭제한 항목을 반환

■ 큐의 가장 앞에 있는 항목의 위치(index)를 확인하려면, 큐가 공백 상태가 아니라는 가정 하, front가 가리키는 다음 항목의 위치를 확인하면 된다.

- 원형 큐에서 front는 비어 있는 슬롯을 가리키고, 그 다음 항목이 실제로 첫 번째 데이터이기 때문이다.

def QPeek(self):
    if self.QIsEmpty():
        return None
    else:
        return self.data[(self.front + 1) % CircularQueue._CAPACITY]

■ 현재 큐에 저장되어 있는 항목의 개수를 반환하는 메소드는 다음과 같이 구현할 수 있다.

def QSize(self):
    return (self.rear - self.front + CircularQueue._CAPACITY) % CircularQueue._CAPACITY

■ size를 단순히 rear - front로 하지 않는 이유는, rear가 회전되어 front보다 작아질 수 있기 때문에 큐의 크기와 % 연산을 이용해야 한다.

- 예를 들어 [E, -, -, -, -, -, C, D] 배열의 크기가 8, front가 6, rear이 1이고 큐의 실제 크기는 3이라고 할 때, rear - front = -5가 되어 음수가 나온다. 

- 하지만 실제 큐에는 3개의 항목이 있다.

- 이를 올바르게 계산하려면 배열 크기(MAX_QSIZE)를 고려한 '모듈로'연산을 사용해서, 원형 큐의 인덱스의 순환적 특성을 반영해 현재 큐의 크기를 계산해야 한다.

- (1 - 5 + 8(MAX_QSIZE))를 하면 -5 + 8 = 3으로 양수로 변환되고 % 8(MAX_QSIZE)을 하면, 실제 원형 큐의 크기가 나온다.

- 이렇게 rear가 front보다 작은 경우에도 올바른 큐의 크기를 계산할 수 있다.

■ 큐의 내용을 출력하는 메소드도 인덱스를 고려해야 한다.

■ 선형 큐는 front가 항상 '인덱스 0'이므로 리스트를 출력하면 되지만, 원형 큐는 항목이 front 다음 항목부터 rear 항목까지 순서대로 출력해야 한다. 이는 리스트의 슬라이싱 기능을 이용하면 된다.

■ 다음과 같이 슬라이싱 기능을 이용하면 front와 rear이 뒤집혔을 때, front 이후부터 MAX_QSIZE 전까지와 인덱스 0부터 rear 항목까지의 항목들을 모아서 출력하면 된다.

def QShow(self):
    if self.front < self.rear:
        print(self.data[self.front+1:self.rear+1])
    else:
        print(self.data[self.front+1:CircularQueue._CAPACITY] + self.data[0:self.rear+1])

 

- 위와 같은 기능들을 종합하면 Circular Queue의 클래스는 다음과 같다.

class CircularQueue:
    _CAPACITY = 10
    
    def __init__(self):
        self.front = 0 
        self.rear = 0 
        self.data = [None] * CircularQueue._CAPACITY 
    
    def QIsEmpty(self):
        return self.front == self.rear

    def QIsFull(self):
        return self.front == (self.rear + 1) % CircularQueue._CAPACITY 

    def QClear(self):
        self.front = self.rear 
        
    def QEnqueue(self, new_item):
        if self.QIsFull(): 
            raise Exception('Queue is full')
        else: 
            self.rear = (self.rear + 1) % CircularQueue._CAPACITY 
            self.data[self.rear] = new_item
            
    def QDequeue(self):
        if self.QIsEmpty(): 
            raise Exception('Queue is empty')
        else: 
            self.front = (self.front + 1) % CircularQueue._CAPACITY  
            return self.data[self.front] 
        
    def QPeek(self):
        if self.QIsEmpty():
            return None
        else:
            return self.data[(self.front + 1) % CircularQueue._CAPACITY]
        
    def QSize(self):
        return (self.rear - self.front + CircularQueue._CAPACITY) % CircularQueue._CAPACITY
    
    def QShow(self):
        if self.front < self.rear:
            print(self.data[self.front+1:self.rear+1])
        else:
            print(self.data[self.front+1:CircularQueue._CAPACITY] + self.data[0:self.rear+1])

 

circle_Q = CircularQueue()
print(circle_Q.QIsEmpty()); print(circle_Q.QIsFull()); print(circle_Q.QSize())
```#결과#```
True
False
0
````````````

circle_Q.QShow()
```#결과#```
[None, None, None, None, None, None, None, None, None, None]
````````````

circle_Q.QDequeue()
```#결과#```
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
Cell In[124], line 1
----> 1 circle_Q.QDequeue()

Cell In[120], line 29, in CircularQueue.QDequeue(self)
     27 def QDequeue(self):
     28     if self.QIsEmpty():
---> 29         raise Exception('Queue is empty')
     30     else: 
     31         self.front = (self.front + 1) % CircularQueue._CAPACITY

Exception: Queue is empty
`````````````

for i in [13, 3, 5, 9, 7, 11, 4, 26, 2]:
    circle_Q.QEnqueue(i)
    
print(circle_Q.QIsFull()); print(circle_Q.QSize()); print(circle_Q.QPeek())
```#결과#```
True
9
13
`````````````

circle_Q.QShow()
```#결과#```
[13, 3, 5, 9, 7, 11, 4, 26, 2]
````````````

circle_Q.QEnqueue(100)
```#결과#```
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
Cell In[128], line 1
----> 1 circle_Q.QEnqueue(100)

Cell In[120], line 22, in CircularQueue.QEnqueue(self, new_item)
     20 def QEnqueue(self, new_item):
     21     if self.QIsFull(): 
---> 22         raise Exception('Queue is full')
     23     else: 
     24         self.rear = (self.rear + 1) % CircularQueue._CAPACITY 

Exception: Queue is full
``````````````

for i in range(5):
    circle_Q.QShow()
    print(f'peek item: {circle_Q.QPeek()}, dequeue item:{circle_Q.QDequeue()}\n')  
    
```#결과#````
[13, 3, 5, 9, 7, 11, 4, 26, 2]
peek item: 13, dequeue item:13

[3, 5, 9, 7, 11, 4, 26, 2]
peek item: 3, dequeue item:3

[5, 9, 7, 11, 4, 26, 2]
peek item: 5, dequeue item:5

[9, 7, 11, 4, 26, 2]
peek item: 9, dequeue item:9

[7, 11, 4, 26, 2]
peek item: 7, dequeue item:7
```````````````

circle_Q.QShow()
```#결과#```
[11, 4, 26, 2]
````````````

circle_Q.QClear()

# self.front = self.rear이라 큐가 비었다고 인식
print(circle_Q.QIsEmpty()); print(circle_Q.QIsFull()); print(circle_Q.QSize())
```#결과#```
True
False
0
````````````

circle_Q.QShow()
```#결과#```
[None, 13, 3, 5, 9, 7, 11, 4, 26, 2]
````````````

circle_Q.QEnqueue(100)
circle_Q.QShow()
```#결과#```
[100]
````````````

# clear 메소드 호출 시, self.data 리스트 자체는 초기화되지 않아서
# 그 전에 큐에 삽입된 값들이 그대로 남아 있으므로 clear 메소드를 다음과 같이 수정

def QClear2(self):
    self.front = self.rear  
    self.data = [None] * CircularQueue._CAPACITY  # 리스트의 모든 값을 None으로 초기화
    
circle_Q = CircularQueue()
for i in [13, 3, 5, 9, 7, 11, 4, 26, 2]:
    circle_Q.QEnqueue(i)
    
circle_Q.QShow()
```#결과#```
[13, 3, 5, 9, 7, 11, 4, 26, 2]
````````````

circle_Q.QClear2()
circle_Q.QShow()
```#결과#```
[None, None, None, None, None, None, None, None, None, None]
````````````

circle_Q.QEnqueue(101)
circle_Q.QShow()
```#결과#```
[101]
````````````

- 원형 큐는 이와 같이 크기가 제한되지만, 삽입, 삭제 연산에서 항목의 이동이 필요 없으므로 두 연산의 시간 복잡도가 모두 $O(1)$로 선형 큐에 비해 효율적이다.

- 원형 큐를 사용할 때, 문제에 따라 큐의 크기를 적절히 만들어 사용하는 것이 좋다.

 

■ 파이썬의 queue 모듈을 통해 큐, 스택, 우선순위 큐의 클래스를 제공받을 수 있다.

import queue

Q = queue.Queue(maxsize = 10) # 크기가 10인 큐 객체 생성
S = queue.LifoQueue() # 스택
PQ = queue.PriorityQueue # 우선순위 큐

■ queue.Queue에서 삽입 연산은 put( ), 삭제 연산은 get( )을 사용한다.

■ get( ) 연산 시, 큐가 공백 상태라면 언더플로(underflow)가 발생하고 put( )연산 시, 큐가 포화 상태라면 오버플로(overflow)가 발생한다. 이때, 언더플로나 오버플로가 발생했을 때 에러를 반환하지 않고 무한루프에 빠지므로 empty( )와 full( )을 통해 큐의 공백 상태와 포화 상태를 미리 확인하는 것이 좋다.

Q.qsize()
```#결과#```
0
````````````

for i in [13, 3, 5, 9, 7, 11, 4, 26, 2]:
    Q.put(i)
Q.qsize()
```#결과#````
9
`````````````

for i in range(Q.qsize()):
    print(f'get: {Q.get()}, size: {Q.qsize()}')
```#결과#```
get: 13, size: 8
get: 3, size: 7
get: 5, size: 6
get: 9, size: 5
get: 7, size: 4
get: 11, size: 3
get: 4, size: 2
get: 26, size: 1
get: 2, size: 0
`````````````

 

3. 우선순위 큐(Priority Queue)

■ 우선순위 큐는 우선순위의 개념을 큐에 도입한 자료구조이다. 모든 데이터에 우선순위를 부여해서 큐에 들어온 순서와 상관없이, 우선순위가 높은 데이터부터 먼저 출력하는 구조이다.

■ 우선순위 개념을 사용하기 대문에 우선순위를 어떻게 정하냐에 따라 우선순위 큐는 큐나 스택으로 얼마든지 사용할 수 있다.

■ 우선순위 큐의 연산은 큐와 동일하다. 단, 삭제 연산에서 어떤 항목이 먼저 삭제되는가에 따라 최대 우선순위 큐와 최소 우선순위 큐로 나뉘며, 디폴트는 가장 높은 우선순위의 항목을 먼저 삭제하는 최대 우선순위 큐이다.

■ 우선순위 큐는 가장 우선순위가 높은 항목만 알 수 있으면 되므로, 항목들을 순서대로 정렬하고 나열할 필요가 없다. 따라서 선형 자료구조로 보기는 어려우며, 가장 효율적인 우선순위 큐의 구현 방법은 힙(heap) 트리를 이용하는 것 이다.

■ 데이터 자체가 우선순위를 나타낸다는 가정 하, 리스트를 사용해서 구현하면 공백 상태, 초기화, 우선순위 큐 크기 확인 메소드는 다음과 같다.

class PriorityQueue:
    def __init__(self):
        self.data = []
        
    def PQIsEmpty(self):
        return len(self.data) == 0
    
    def PQClear(self):
        self.data = []
        
    def PQSize(self):
        return len(self.data)

 

■ 위의 가정 하에 삽입 항목도 리스트의 append( )를 이용하면 된다.

def PQEnqueue(self, new_item):
    self.data.append(new_item)

■ 우선수위 큐(최대 우선순위 큐)의 삭제 연산은 항상 우선순위가 가장 높은 항목부터 삭제해야 하므로, 해당되는 항목을 찾는 기능이 필요하다. 이는 모든 항목을 찾아서 가장 우선순위가 높은 항목의 인덱스를 반환하는 메소드를 정의하여 사용하면 된다.

def PQFindMaxIndex(self):
    if self.PQIsEmpty():
        raise Exception('Queue is empty')
    else:
        h = 0
        for i in range(1, self.PQSize()):
            if self.data[i] > self.data[h]:
                h = i
        return h

- 먼저 우선순위 큐가 비었는지 확인하고, 비어있지 않다면 최대값을 찾는다. (데이터 자체가 우선순위를 나타낸다는 가정 하)

- 인덱스 0과 인덱스 1에 있는 항목들의 값을 비교하면서 더 큰 값을 가지는 항목의 인덱스를 i에 저장하고 최종적으로 최대값이 있는 인덱스를 찾아 반환한다.

■ 가장 우선순위가 높은 항목의 인덱스를 알면, 삭제 연산은 해당 인덱스에 해당되는 항목을 삭제, peek( ) 연산은 해당 인덱스에 해당되는 항목을 반환할 수 있다.

def PQDequeue(self):
    highest_index = self.PQFindMaxIndex()
    if highest_index is None:
        return None
    else:
        return self.data.pop(highest_index)
    
def PQPeek(self):
    highest_index = self.PQFindMaxIndex()
    if highest_index is None:
        return None
    else:
        return self.data[highest_index]

 

- 위와 같은 기능들을 종합하면 Priority Queue의 클래스는 다음과 같다.

class PriorityQueue:
    def __init__(self):
        self.data = []
        
    def PQIsEmpty(self):
        return len(self.data) == 0
    
    def PQClear(self):
        self.data = []
        
    def PQSize(self):
        return len(self.data)
    
    def PQEnqueue(self, new_item):
        self.data.append(new_item)
        
    def PQFindMaxIndex(self):
        if self.PQIsEmpty():
            raise Exception('Queue is empty')
        else:
            h = 0
            for i in range(1, self.PQSize()):
                if self.data[i] > self.data[h]:
                    h = i
            return h
        
    def PQDequeue(self):
        highest_index = self.PQFindMaxIndex()
        if highest_index is None:
            return None
        else:
            return self.data.pop(highest_index)
    
    def PQPeek(self):
        highest_index = self.PQFindMaxIndex()
        if highest_index is None:
            return None
        else:
            return self.data[highest_index]

priority_Q = PriorityQueue()
print(priority_Q.PQIsEmpty()); print(priority_Q.PQSize()); print(priority_Q.PQPeek())
```#결과#```
True
0
---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
Cell In[17], line 1
----> 1 print(priority_Q.PQIsEmpty()); print(priority_Q.PQSize()); print(priority_Q.PQPeek())

Cell In[14], line 35, in PriorityQueue.PQPeek(self)
     34 def PQPeek(self):
---> 35     highest_index = self.PQFindMaxIndex()
     36     if highest_index is None:
     37         return None

Cell In[14], line 19, in PriorityQueue.PQFindMaxIndex(self)
     17 def PQFindMaxIndex(self):
     18     if self.PQIsEmpty():
---> 19         raise Exception('Queue is empty')
     20     else:
     21         h = 0

Exception: Queue is empty
`````````````

for i in [13, 3, 5, 9, 7, 11, 4, 26, 2]:
    priority_Q.PQEnqueue(i)
    
print(priority_Q.PQIsEmpty()); print(priority_Q.PQSize())
```#결과#```
False
9
````````````

priority_Q.data
```#결과#```
[13, 3, 5, 9, 7, 11, 4, 26, 2]
````````````

# index가 7인 항목 26이 최댓값 
# 데이터 자체가 우선순위를 나타낸다는 가정 하에 
# 항목 26이 가장 우선순위가 높은 항목
print(f'highest item: {priority_Q.PQPeek()}, index of highest item: {priority_Q.PQFindMaxIndex()}')
```#결과#```
highest item: 26, index of highest item: 7
````````````

while True:
    print(f'highest item: {priority_Q.PQPeek()}, data: {priority_Q.data}\n')
    priority_Q.PQDequeue()
    
```#결과#```
highest item: 26, data: [13, 3, 5, 9, 7, 11, 4, 26, 2]

highest item: 13, data: [13, 3, 5, 9, 7, 11, 4, 2]

highest item: 11, data: [3, 5, 9, 7, 11, 4, 2]

highest item: 9, data: [3, 5, 9, 7, 4, 2]

highest item: 7, data: [3, 5, 7, 4, 2]

highest item: 5, data: [3, 5, 4, 2]

highest item: 4, data: [3, 4, 2]

highest item: 3, data: [3, 2]

highest item: 2, data: [2]

---------------------------------------------------------------------------
Exception                                 Traceback (most recent call last)
Cell In[124], line 2
      1 while True:
----> 2     print(f'highest item: {priority_Q.PQPeek()}, data: {priority_Q.data}\n')
      3     priority_Q.PQDequeue()

Cell In[116], line 35, in PriorityQueue.PQPeek(self)
     34 def PQPeek(self):
---> 35     highest_index = self.PQFindMaxIndex()
     36     if highest_index is None:
     37         return None

Cell In[116], line 19, in PriorityQueue.PQFindMaxIndex(self)
     17 def PQFindMaxIndex(self):
     18     if self.PQIsEmpty():
---> 19         raise Exception('Queue is empty')
     20     else:
     21         h = 0

Exception: Queue is empty
````````````````

- 데이터 자체가 우선순위를 나타낸다는 가정 하, 값이 가장 큰 항목 순서대로 삭제 연산이 삭제 연산을 진행되는 것을 볼 수 있다.

■ 리스트의 가장 높은 값을 가지는 항목의 인덱스를 찾기 위해 사용한 PQFindMaxIndex( ) 메소드는 우선순위 큐의 모든 항목의 우선순위를 비교하기 때문에 시간 복잡도는 $O(n)$이 된다.

■ 따라서 이 PQFindMaxIndex( ) 메소드를 호출해서 사용하는 PQDequeue( ) 메소드와 PQPeek( ) 메소드의 시간 복잡도도 $O(n)$이 된다.

■ 또한, 예를 들어 위의 예시에서 항목 13을 삭제할 때, 모든 항목들이 한 칸씩 앞으로 이동하는 과정이 발생하며 이 연산도 $O(n)$이다. 따라서 삭제 연산의 시간 복잡도는 $O(n)$이다. 반면 삽입 연산은 append( )를 사용하여 대부분의 경우 시간 복잡도가 $O(1)$이라 할 수 있다.

■ 파이썬에서 제공하는 모듈을 통해 우선순위 큐를 사용할 수 있다.

from queue import PriorityQueue

# 우선순위 큐의 디폴트 사이즈는 무한대이지만, 다음과 같이 특정 사이즈로 설정할 수 있음
PQ = PriorityQueue(maxsize=10) 

for i in [13, 3, 5, 9, 7, 11, 4, 26, 2]:
    PQ.put(i)
PQ.qsize()
```#결과#```
9
````````````

for i in range(PQ.qsize()): 
    print(PQ.get()) # 크기 순서대로 항목이 삭제된다.
    
```#결과#```
2
3
4
5
7
9
11
13
26
`````````````

■ 만약, 오름차순이 아닌 다른 기준으로 항목을 정렬하려면 튜플 형태의 (우선순위, 값)로 데이터를 추가하고 삭제하면 된다.

items = [(3, 'py'), (1, 'th'), (2, 'on')]

for item in items:
    PQ.put(item)
PQ.qsize()
```#결과#```
3
````````````

while not PQ.empty():
    print(PQ.get())
    
```#결과#```
(1, 'th')
(2, 'on')
(3, 'py')
`````````````

- 삭제 연산 시, 우선순위가 높은 순서대로 항목들이 삭제되는 것을 볼 수 있다.