큐Queue

5. 큐Queue#

슬라이드

본문 내용을 요약한 슬라이드를 다운로드할 수 있다.

주요 내용

큐 추상 자료형
큐 자료구조
큐 활용

5.1. 큐의 정의#

항목 추가는 꼬리에서, 항목 삭제는 머리에서 이루어지는 선형 자료형을 큐queue라 부른다. 아래 그림에서 보여지는 것처럼 먼저 들어온 항목이 먼저 나간다는 선입선출first in first out(FIFO) 원리를 따른다. 즉 항목의 삭제는 추가된 순서대로 진행된다.

큐 자료형은 다음 예제들처럼 다양한 영역에서 이루어진다.

은행: 대기 순서에 따른 번호표 배분
프린터: 순서에 따른 서류 인쇄
키보드 입력: 키보드 입력값을 버퍼buffer에 잠시 저장한 다음에 처리 입력 순서대로 처리
컴퓨터 CPU: 사용자 명령을 순차적으로 처리

5.2. `Queue` 추상 자료형#

큐 추상 자료형을 구체적인 파이썬 자료구조(data structure)로 구현할 때 요구되는 기본 속성과 기능은 다음과 같다.

Queue(maxsize=0): 비어 있는 큐 생성. maxsize를 최대로 많이 담을 수 있는 항목의 수. 0인 경우엔 항목 수 제한 없음.
put(item): maxsize가 초과되지 않을 때 꼬리에 항목 추가
get(): 머리 항목을 삭제하면서 삭제하는 항목 반환.
empty(): 큐가 비었는지 여부 판단. 부울값 반환.
full(): 큐가 꽉 차 있는지 여부 판단. 부울값 반환.
qsize(): 큐에 포함된 항목 개수 반환.

Queue 추상 클래스

아래 코드에서 정의하는 추상 클래스 Queue는 생성자 또한 구현되어 있지 않다. 이유는 저장 방식을 자식 클래스에 위임하려 하기 때문이다.

class Queue:
    def __init__(self, maxsize=0):
        """
        - 새로운 큐 생성
        - maxsize: 최대 항목 수. 0은 무한대 의미.
        - 저장 방식은 자식 클래스가 지정해야 함.
        """
        raise NotImplementedError(
            """아래 두 변수 구현 필요
            self._maxsize=maxsize
            self._container=비어 있는 모음 객체. 항목 저장.
            """)
    
    def qsize(self):
        """항목 수 반환"""
        return len(self._container)
    
    def empty(self):
        """비었는지 여부 확인"""
        return not self._container

    def full(self):
        """_maxsize 충족 여부 확인"""

        if self._maxsize <= 0:
            return False
        elif self.qsize() < self._maxsize:
            return False
        else:
            return True            

    def put(self, item):
        """항목 추가"""
        raise NotImplementedError

    def get(self):
        """항목 삭제"""
        raise NotImplementedError

클래스의 생성자가 구현되어 있지 않기에 객체 선언도 허용되지 않는다. 다만 생성자 함수를 구현할 때 반드시 선언해야 하는 두 개의 변수를 지정하도록 유도한다.

self._maxsize=maxsize: 저장가능한 최대 항목 수
self._container: 비어 있는 모음 객체. 항목 저장 용도.

q = Queue()

---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
Cell In[26], line 1
----> 1 q = Queue()

Cell In[25], line 8, in Queue.__init__(self, maxsize)
      2 def __init__(self, maxsize=0):
      3     """
      4     - 새로운 큐 생성
      5     - maxsize: 최대 항목 수. 0은 무한대 의미.
      6     - 저장 방식은 자식 클래스가 지정해야 함.
      7     """
----> 8     raise NotImplementedError(
      9         """아래 두 변수 구현 필요
     10         self._maxsize=maxsize
     11         self._container=비어 있는 모음 객체. 항목 저장.
     12         """)

NotImplementedError: 아래 두 변수 구현 필요
            self._maxsize=maxsize
            self._container=비어 있는 모음 객체. 항목 저장.
            

5.3. 큐 자료구조 구현#

큐 자료구조를 선언할 때의 핵심은 항목의 저장방식과 머리와 꼬리를 어디로 설정하는가이다. 4장에서 myDeque 클래스를 선언할 때 사용한 리스트는 꼬리에서의 항목 추가와 삭제가 느린편이다. 따라서 여기서는 리스트 대신에 collections.queue 클래스를 이용한다.

from collections import deque

class myQueue(Queue):
    def __init__(self, maxsize=0):
        """
        - 새로운 큐 생성
        - _maxsize: 최대 항목 수. 0은 무한대 의미.
        - _container: 항목 저장 장치. collections 모듈의 queue 활용.
        """
        self._maxsize = maxsize
        self._container = deque([]) # 비어있는 덱
    
    def __repr__(self):
        """큐 표기법: queue([1, 2, 3]) 등등"""
        parent_repr = repr(self._container)
        # deque 문자열을 myQueue 문자열로 대체
        return parent_repr.replace("deque", 'myQueue')
    
    def put(self, item):
        """
        _maxsize를 못 채웠을 경우에만 항목 추가
        """
        if not self.full():
            self._container.appendleft(item)
        else:
            print("추가되지 않아요!")

    def get(self):
        """머리 항목 삭제 후 반환"""
        return self._container.pop()

아래 코드가 큐 객체를 생성하고 활용하는 간단한 작동법을 소개한다.

q = myQueue(maxsize=4)

q.put(4)
q.put("dog")
q.put(True)
print(q)
q.put(8.4)
print(q.full())
print(q)
q.put("하나 더?")
print(q)
print(q.get())
print(q.get())
print(q.qsize())
print(q)
print(q.empty())

myQueue([True, 'dog', 4])
True
myQueue([8.4, True, 'dog', 4])
추가되지 않아요!
myQueue([8.4, True, 'dog', 4])
4
dog
2
myQueue([8.4, True])
False

5.4. `queue.Queue` 클래스#

파이썬 queue 모듈이 큐 추상 자료형을 자료구조로 구현한 Queue 클래스를 지원한다. 앞서 collections.deque를 이용하여 정의한 myQueue와의 항목 추가와 삭제 실행 속도를 비교했을 때 myQueue가 4, 5배 정도 빠른 것으로 확인된다.

import queue

put() 메서드 속도 비교

%%time

n = 100_000
q1 = myQueue(maxsize=0)

for k in range(n):
    q1.put(k)

CPU times: user 11.2 ms, sys: 45 μs, total: 11.2 ms
Wall time: 11.1 ms

%%time

n = 100_000
q2 = queue.Queue(maxsize=0)

for k in range(n):
    q2.put(k)

CPU times: user 56.3 ms, sys: 0 ns, total: 56.3 ms
Wall time: 55.7 ms

get() 메서드 속도 비교

%%time

for k in range(n):
    q1.get()

CPU times: user 7.66 ms, sys: 0 ns, total: 7.66 ms
Wall time: 7.68 ms

%%time

for k in range(n):
    q2.get()

CPU times: user 53.5 ms, sys: 0 ns, total: 53.5 ms
Wall time: 53 ms

5.5. 큐 활용: 폭탄 돌리기 게임#

게임 소개

여러 명이 빙 둘러앉아 폭탄 돌리기 게임을 한다. 폭탄을 계속 돌리다가 멈추는 순간 폭탄을 들고 있는 사람은 탈락된다. 폭탄을 몇 번 돌리는가는 미리 지정하며 최종적으로 한 명이 남을 때까지 게임을 진행한다. 아래 그림은 6명이 폭탄 돌리기 게임에 참여해서 폭탄을 5번 돌린 후 폭탄을 갖고 있는 6번이 삭제 대상으로 지정되는 과정을 보여준다.

게임 구현

폭탄 돌리기 게임을 큐를 이용하여 구현한다. 게임 시작과 진행 과정에 필요한 사항들은 다음과 같다.

게임 시작: 참여자들의 수 player와 폭탄 돌리기 횟수 count
폭탄 시작 위치: 큐의 머리
폭탄 전달: 머리 항목 삭제 후 바로 꼬리에 추가
탈락: cout번의 폭탄 돌리기 이후 머리에 위치한 사람 탈락
게임 정지: 한 명이 남을 때까지 반복

위 알고리즘을 함수로 구현하면 다음과 같다.

def bombing(player, count):

    player_queue = myQueue()
    
    # 큐에 사람 목록 추가
    for p in range(1, player+1):
        player_queue.put(p)

    # 게임 진행
    while player_queue.qsize() > 1:
        # count번 폭탄 돌린 후 탈락자 지정
        for i in range(count):
            player_queue.put(player_queue.get())

        player_queue.get()

    return player_queue.get()    # 마지막 남은 사람

아래 코드는 폭탄을 5번 돌릴 때마다 탈락자를 정할 때 마지막에 4번이 남는다는 것을 확인해준다.

bombing(6, 5)

5.6. 연습 문제#

(실습) 큐