우선순위 큐와 순환 큐 - 자료구조, 파이썬(python)

우선순위 큐의 각 원소들은 우선순위를 갖고 있다. 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다.

만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리된다.

즉, 우선순위가 다르다면 우선순위에 따라 원소들이 처리되지만 우선순위가 같은 경우 큐의 본래 특성인 선입 선출에 따라 큐가 처리된다.

#노드 클래스 생성
class Node:
    def __init__(self, data, pri):
        self.data = data
        self.next = None
        self.pri = pri
 
#우선순위 큐
class Priority_Queue:
    def __init__(self, data, pri):
        self.head = Node(data, pri)
 
    def Enqueue(self,data, pri):
        node = self.head
        while node.next:
            node = node.next
        if node.pri < pri:
            node.next = Node(data,pri)
        else: #node.pri >= pri
            node = self.head
            while node.next.pri < pri:
                node = node.next
            temp = node.next
            new = Node(data, pri)
            new.next = temp
            node.next = new
            del new
 
    def Dequeue(self):
        node = self.head
        while node.next:
            if node.next.next is None:
                node.next = None
                break
            else:
                node = node.next
 
    def display(self):
        node = self.head
        while node:
            print(node.data)
            node = node.next

직선 큐는 한가지 치명적인 단점을 가지고 있다. Dequeue 연산을 수행했다고 가정해볼 때, 가장 첫 번째 있는 요소를 빼내고 나면

그 뒤에 있는 원소들을 하나식 하나씩 옮겨줘야 하고 그만큼 옮겨주는 연산이 필요하게 된다.

큐의 원소들이 많아질수록 부담은 커지게 된다.

이러한 단점을 해결하기 위해 큐의 맨 앞에 전단(front)와 큐의 맨 뒤에 후단(rear)을 배치하는 방법이 있다. 큐를 제거할 때

전단을 후단에 가깝게 옮겨주면, 나머지 데이터가 움직일 필요 없이 맨 앞의 데이터가 전단 밖으로 벗어나 삭제된다.

다만, 이러한 방법도 단점이 있다. 제거 연산시 후단은 움직이지 않기 때문에 전단을 후단 쪽으로 옮기면 큐의 용량자체가 줄어들게 된다.

이러한 단점까지 보완한 게 순환 큐이다. 순환 큐란 배열의 처음과 끝을 이어놓은 구조이다. 물론 물리적으로는 일직선이지만, 논리적으로는 원형으로 보이는 것.

이런 구조는 어디가 배열의 시작이고 끝인지 알 수 없음. 전단과 후단이 저 원형내부를 계속 돌아가며 움직이는 것. 전단으로 젝

연산을 진행하더라도 더하는 연산으로 후단을 옮겨준다면 큐의 용량을 보존할 수 있다.

이 사진자료는 http://logonluv.blogspot.com/2015/02/datastructure-queue.html 를 참고했다.

#순환큐 구현
 
class circular_Queue:
    def __init__(self, max):
        self.max = max
        self.list = [None] * self.max
        self.size = self.rear = self.front = 0
 
    def next_idx(self, idx):
        return (idx + 1) % self.max
    
    def enqueue(self, item):
        if self.next_idx(self.rear) == self.front:
            print('큐가 꽉 찼습니다')
        else:
            self.rear = self.next_idx(self.rear)
            self.list[self.rear] = item
            self.size += 1
 
    def dequeue(self):
        if self.size == 0:
            print('큐가 비었습니다')
        else:
            self.front = self.next_idx(self.front)
            self.list[self.front] = None
            self.size -= 1
 
    def peek(self):
        self.front = self.next_idx(self.front)
        print(self.list[self.front])
 
    def display(self):
        current = self.front
        while current != self.rear:
            current = self.next_idx(current)
            print(self.list[current])