Queue(큐), Priority Queue(우선순위 큐) 구현

Max Heap 구현 참고 : https://velog.io/@seanlion/pythonmaxheap

들어가며

배열을 활용해 원형 Queue를 구현해보았고,
Max Heap을 활용해 우선순위 큐를 파이썬 코드로 구현해보았습니다.

우선순위 큐의 경우 큐를 사용하는 프로그램까지 구현해보았으니 큐, 우선순위 큐 구현에 참고하시기 바랍니다.

원형 큐 구현

# queue 구현
from typing import Any
class FixedQueue: # 원형(고정) 큐로 구현
    class Empty(Exception):
        # 디큐 시 내보내는 예외 처리
        pass

    class Full(Exception):
        # 인큐 시 내보내는 예외 처리
        pass

    def __init__(self, capacity: int ) -> None: 
    # queue 시작할 때 호출되는 메소드
    
        self.data_cnt = 0 # 데이터 개수
        self.front = 0 # 프론트 커서
        self.rear = 0 # 리어 커서
        self.q_capa = capacity # 큐 크기
        self.que = [None] * capacity # 큐 선언

    def __len__(self) -> int: # 큐에 있는 데이터 개수 알려주는 메소드
        return self.data_cnt

    def is_empty(self) -> bool: # 큐에 데이터가 없는지 체크
        return self.data_cnt <= 0
        
    def is_full(self) -> bool: # 큐에 데이터가 가득 찼는지 체크
        return self.data_cnt >= self.q_capa


    def enque(self, num: Any)-> None: # 큐에 데이터 넣는 메소드
        if self.is_full():
            raise FixedQueue.Full # 큐가 가득 차 있으면 예외처리
        self.que[self.rear] = num
        self.rear +=1
        self.data_cnt +=1
        
        # rear가 배열의 마지막 부분이라서 
        # rear를 그 다음으로 놓으려하니 범위 초과 일때의 처리
        if self.rear == self.q_capa: 
            self.rear = 0

    def deque(self) -> Any: # 큐에서 데이터 빼는 메소드
        if self.is_empty():
            raise FixedQueue.Empty # 데이터 없으면 예외 처리

		num = self.que[self.front]
        self.front+=1
        self.data_cnt -=1
        
        # front가 배열의 마지막 부분일 때 front를 그 다음으로 놓으려하니 
        # 범위 초과할 때 인덱스를 0으로 초기화. 
        # 인덱스 끝에서 처음으로 돌아가는 효과
        if self.front == self.q_capa: 
            self.front = 0
        return num

    def peek(self) -> Any: # 큐에 맨 앞 데이터를 보는 메소드, front 값만 반환해줌.

		if self.is_empty(): # 큐에 데이터가 없으면 예외처리
            raise FixedQueue.Empty
        return self.que[self.front]

    def find(self, value: Any) -> Any: #큐에서 원하는 값을 찾으면 그 값의 인덱스를 반환 해주는 함수
        for i in range(self.data_cnt):
            index = (i+self.front) % self.q_capa 
            # 큐의 인덱스를 구하는 공식, 배열 인덱스랑은 다르게 구함.
            
            if self.que[index] == value:
                return index
        return -1

    def count(self, value: Any)-> Any: # 큐에 있는 특정 값의 개수 반환
        c = 0
        for i in range(self.data_cnt):
            index = (i + self.front) % self.q_capa  
            # 큐의 인덱스를 구하는 공식, 배열 인덱스랑은 다르게 구함.
            
            if self.que[index] == value:
                c+=1
        return c

    def __contains__(self, value: Any)-> bool: 
    #큐에 해당 값이 들어 있는지 없는지를 판단
    	if self.count(value) > 0:
            return 1
        else:
            return 0

    def clear(self) -> None:  # 큐의 값들을 삭제하는 함수. 
# 그러나 실제로 값을 비우는게 아니라 데이터 개수, front,rear 커서를 0으로 보내는 함수. 
# front에 값이 있으면 deque 같은거 할 수 있지않나? 라고 생각할 수 있으나, 
# 여기서 data cnt를 0으로 만들어주면 deque할 때는 
# 항상 is_empty 체크 할 때 True가 되니 deque시 예외처리.
        self.data_cnt = self.front = self.rear = 0
        

    def dump(self)-> None: 
    #모든 데이터를 맨 앞 부터 맨 끝까지 출력, 큐에 데이터 없으면 에러 메세지 출력
        if self.is_empty():
            print('큐가 비었습니다.')
        else:
            for i in range(self.data_cnt):
                print(self.que[(i + self.front) % self.q_capa], end=' ')
            print()

우선순위 큐 구현

# max heap으로 우선순위 큐 구현
# 구현 메소드 : enqueue, dequeue, len(큐 길이), show(큐 원소 보여주기)

from max_heap import MaxHeap, Element # max_heap.py에서 클래스 임포트

class PriorityQueue:
    def __init__(self): # 우선순위 큐 시작할 때 호출
        self.queue = MaxHeap()
        
    def is_empty(self) -> bool: # 큐가 비었는지 확인
        return self.queue.is_empty()
        
    def is_full(self) -> bool: # 큐가 가득 찼는지 확인
        return self.queue.is_full()

    def enqueue(self, data): # 우선순위 큐에 데이터 넣기
        self.queue.push(data)

    def dequeue(self): # 우선순위 큐에서 데이터 빼기
        try:
            return self.queue.pop()
        except IndexError:
            print()
            return

    def show(self):
        return self.queue.dump()

    def size(self):
        return self.queue.size()

우선순위 큐 사용 프로그램

from enum import Enum
from prior_que import PriorityQueue # prior_que.py에서 클래스 임포트

MenuList = Enum('Menu', ['인큐','디큐','길이','덤프','종료'])

def select_menu() -> MenuList: # 메뉴 선택하는 코드
    s = [f'({m.value}){m.name}' for m in MenuList]
    while True: # 무한루프
        print(*s, sep= '   ', end=' ')
        n= int(input(": "))
        if 1<= n <= len(MenuList):
            return MenuList(n)

q = PriorityQueue() # 우선순위 큐 인스턴스 

while True:
    menu = select_menu()

    if menu == MenuList.인큐:
        data = int(input('인큐할 데이터를 입력하세요 : '))
        
        try:
            q.enqueue(data)
        except q.is_full():
            print('큐가 가득 찼습니다.')
            
    elif menu == MenuList.디큐:
        try:
            dq = q.dequeue()
            print(f'디큐한 데이터는 {dq}입니다.')
        except q.is_empty():
            print('큐가 비어 있습니다.')
            
    elif menu == MenuList.길이:
        try:
            pk = q.size()
            print(f'큐의 길이는 {pk}입니다.')
        except q.is_empty():
            print('큐가 비었습니다.')
            
    elif menu == MenuList.덤프:
        q.show()
        
    else:
        break