[Python] 큐(Queue) 구현

1. 개발 환경 : Python 3.8.10, WSL2, VSCODE

 

2. 큐(Queue)

2.1. 큐의 개념

• 줄을 서는 행위와 유사
• 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 (FIFO, First In First Out)
• 스택과 꺼내는 순서가 반대입니다. (스택은 LIFO)

• Enqueue : 큐에 데이터를 넣는 기능
• Dequeue : 큐에서 데이터를 꺼내는 기능
• Front : 데이터를 꺼내는 쪽
• Rear : 데이터를 넣는 쪽

2.2. 파이썬 큐(queue) 라이브러리

import queue 하여 사용할 수 있습니다.

 

• Queue() : 일반적인 큐 자료구조 >> queue.Queue()
• LifoQueue() : 나중에 입력된 데이터가 먼저 출력 (스택구조) >> queue.LifoQueue()
• PriorityQueue() : 데이터마다 우선순위를 넣어서 우선순위가 높은 순으로 출력 >> queue.PriorityQueue()

2.3. 큐의 활용

• 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현할 때 사용합니다.

 

3. Python으로 큐 클래스 구현하기

• enque() : 데이터 넣기
• deque() : 데이터 꺼내기
• peek() : 들여다보기
• find() : 검색
• count() : 특정 데이터 개수 세기
• __contain__() : 데이터가 포함되어 있는지 판단
• clear() : 큐의 원소 전체 삭제
• dump() : 큐의 데이터 전체 출력

 

3.1. 구현 코드

from typing import Any

class FixedQueue:
    class Empty(Exception):
        """
        비어있는 FixedQueue에 대해 deque 또는 peak을 호출 할때 내보내는 예외처리
        """
        pass
    class Full(Exception):
        """
        가득 찬 FixedQueue에 enque를 호출 할때 내보내는 예외처리
        """
        pass
        
    def __init__(self, capacity) -> None:
        """
        초기화 선언
        """
        self.no = 0 # 현재 데이터의 개수
        self.front = 0 # 맨 앞 원소의 커서 위치
        self.rear = 0   # 맨 뒤 원소의 커서 위치
        self.capactiy = capacity # 큐의 크기
        self.que = [None] * capacity # 큐의 본체
    
    def __len__(self):
        """
        큐에 있는 모든 데이터 개수를 반환
        """
        return self.no
    
    def is_empty(self) -> bool:
        return self.no <= 0
    
    def is_full(self) -> bool:
        return self.no >= self.capactiy

    def peek(self):
        """
        데이터를 피크합니다.
        """
        if self.is_empty():
            raise FixedQueue.Empty
        return self.que[self.front]
    
    def enque(self, data):
        if self.is_full():
            raise FixedQueue.Full
        self.que[self.rear] = data
        self.rear += 1
        self.no += 1
        if self.rear == self.capactiy:
            # 용량보다 커지면 rear가 맨 앞으로 돌아와 데이터 입력
            self.rear = 0
    
    def deque(self):
        if self.is_empty():
            raise FixedQueue.Empty
        x = self.que[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capactiy:
            self.front = 0
        return x
    
    def find(self, value):
        """
        큐에서 포함되어 있는 value를 찾아 인덱스를 반환하고 아니면 -1을 반환
        """
        for i in range(self.no):
            idx = (i + self.front) % self.capactiy  # capacity를 넘어가는 경우가 생기지 않게 해야함 (순환구조 코딩)
            if self.que[idx] == value:
                return idx
        return -1
    
    
    def count(self, value):
        """
        큐에 포함돼있는 value의 개수를 반환합니다.
        """
        cnt = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capactiy
            if self.que[idx] == value:
                cnt += 1
        return cnt
        
    def __contain__(self, value):
        return self.count(value)
    
    def clear(self):
        """
        모든 큐의 데이터를 비웁니다.
        """
        self.no = self.front = self.rear = 0
    
    def dump(self):
        """
        모든 데이터를 맨 앞에서 맨 끝 순서로 출력합니다.
        """
        if self.is_empty():
            raise FixedQueue.Empty
        else:
            for i in range(self.no):
                print(self.que[(i + self.front) % self.capactiy], end = ' ')
            print()

 

3.2. 실행 코드

64개의 데이터를 입력받아 저장할 수 있는 큐를 구현하였습니다.

 

from enum import Enum
from fixed_queue import FixedQueue

Menu = Enum('Menu', ['인큐', '디큐', '피크', '검색', '덤프', '종료'])

def select_menu():
    s = [f'({m.value}){m.name}' for m in Menu]
    while True:
        print(*s, sep=' ', end='')
        n = int(input(': '))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
    
q = FixedQueue(64)

while True:
    print(f'현재 데이터 개수: {len(q)} / {q.capactiy}')
    menu = select_menu()
    
    if menu == Menu.인큐:
        x = int(input('인큐할 데이터를 입력하세요: '))
        try:
            q.enque(x)
        except FixedQueue.Full:
            print('큐가 가득찼습니다.')
            
    elif menu == Menu.디큐:
        try:
            x = q.deque()
            print(f'디큐한 데이터는 {x}입니다.')
        except FixedQueue.Empty:
            print('큐가 비어있습니다.')
    
    elif menu == Menu.피크:
        try:
            x = q.peek()
            print(x)
        except FixedQueue.Empty:
            print('큐가 비어있습니다.')
    
    elif menu == Menu.검색:
        x = int(input('검색할 값을 입력하세요: '))
        if q.find(x) == -1:
            print('검색값을 찾을 수 없습니다.')
        else:
            print(f'{q.count(x)}개 포함되고, 맨 앞의 위치는 {q.find(x)}')
            
    elif menu == Menu.덤프:
        q.dump()
    
    else:
        break

 

실행 순서는 다음과 같습니다.

 

1. 1,2,3,3,2,1 을 인큐
2. 두 번 디큐
3. 피크
4. 1,2,3을 검색
5. 덤프
6. 종료

3.3. 실행 결과

1. 인큐

현재 데이터 개수: 0 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요: 1
현재 데이터 개수: 1 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요: 2
현재 데이터 개수: 2 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요: 3
현재 데이터 개수: 3 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요: 3
현재 데이터 개수: 4 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요: 2
현재 데이터 개수: 5 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 1
인큐할 데이터를 입력하세요: 1
현재 데이터 개수: 6 / 64

2. 디큐

(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 2
디큐한 데이터는 1입니다.
현재 데이터 개수: 5 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 2
디큐한 데이터는 2입니다.
현재 데이터 개수: 4 / 64

3.  피크

(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 3
3
현재 데이터 개수: 4 / 64

4. 1,2,3 검색

(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 4
검색할 값을 입력하세요: 1
1개 포함되고, 맨 앞의 위치는 5
현재 데이터 개수: 4 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 4
검색할 값을 입력하세요: 2
1개 포함되고, 맨 앞의 위치는 4
현재 데이터 개수: 4 / 64
(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 4
검색할 값을 입력하세요: 3
2개 포함되고, 맨 앞의 위치는 2
현재 데이터 개수: 4 / 64

5. 덤프

(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 5
3 3 2 1 
현재 데이터 개수: 4 / 64

6. 종료

(1)인큐 (2)디큐 (3)피크 (4)검색 (5)덤프 (6)종료: 6

 

 

[출처] : https://www.youtube.com/watch?v=n0wWDd64WwA&t=7936s