데이터를 임시 저장하는 기본 자료구조인 큐에 대해서 알아보자

큐

큐란?

가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 방식이다.

enqueue : 큐에 데이터를 추가하는 작업
dequeue : 큐에서 데이터를 꺼내는 작업
front : 데이터를 꺼내는 쪽
rear : 데이터를 넣는 쪽

배열로 큐 구현하기

큐 또한 스택처럼 배열을 사용해서 구현할 수 있다.

배열의 맨 앞부터 순서대로 Q, U, E, U, E가 들어있다. 이 상태에서 X를 인큐하고 Q를 디큐하는 과정을 알아보자.

1) X를 인큐하기
맨 끝 데이터가 저장되어 있는 곳의 다음 위치에 X를 저장한다. 이때 처리의 복잡도는 O(1)이고 비교적 적은 비용으로 구현할 수 있다.

2) Q를 디큐하기
맨 앞에 저장되어 있는 Q를 꺼내면 2번째 이후의 모든 원소를 앞쪽으로 옮겨야 한다. 이때 처리의 복잡도는 O(n)이며 데이터를 꺼낼 때 마다 이런 처리 과정을 거쳐야 한다면 프로그램의 효율성이 많이 낮아진다.

링 버퍼로 큐 구현하기

디큐할 때 배열 안의 원소를 옮기지 않는 큐를 링 버퍼를 사용하여 구현해보자.

front : 맨 앞 원소의 인덱스
rear : 맨 끝 원소 바로 뒤의 인덱스(다음 인큐 시, 데이터가 저장되는 위치)

인큐와 디큐가 일어날 때 front와 rear의 값을 변화시키면 배열안의 원소를 옮기지 않을 수 있다. 링 버퍼에서 인큐와 디큐가 일어나는 과정을 자세히 알아보자.

1) 7개의 데이터 35, 56, 24, 68, 95, 73, 19가 que[7], que[8], ... , que[11], que[0], que[1]에 저장한다. 이때 front값은 7이고 rear값은 2이다.

2) 82를 인큐해보자. que[rear]에 82를 저장하고 rear의 값은 1 증가시킨다.

3) 35를 디큐해보자. 맨 앞 원소인 que[front]를 꺼내고 front의 값을 1 증가시킨다.

위와 같이 링 버퍼로 큐를 구현하면 원소를 옮길 필요가 없이 front와 rear의 값을 수정하는 것만으로 인큐와 디큐를 할 수 있다. 인큐와 디큐의 복잡도는 O(1)이다.

위의 내용을 참고하여 고정 길이 큐를 만들어보자.

예외처리 클래스 : Empty
비어 있는 큐에 deque(), peek() 함수를 호출할 때 내보내는 예외처리

예외처리 클래스 : Full
가득 찬 큐에 enque()함수를 호출할 때 내보내는 예외 처리

초기화하는 함수 : init()
큐의 배열을 생성하는 등의 준비 작업을 수행. 다음과 같은 5개의 변수에 값을 설정.

que : 큐의 배열로 list형 배열
capacity : 큐의 최대 크키를 나타내며 que의 원소 수와 일치하는 값
front : 맨 앞의 원소를 나타내는 인덱스, 가장 처음 넣은 원소의 인덱스
rear : 맨 끝의 원소를 나타내는 인덱스, 가장 마지막에 넣은 맨 끝 원소의 바로 다음 인덱스로 다음 인큐 때 데이터를 저장하는 인덱스
no : 큐에 쌓여 있는 데이터의 개수를 나타내는 int형 정수. 큐가 비어있거나 가득 차 있으면 변수 front와 rear의 값이 같은데 이때 no을 사용하여 구별한다. 큐가 비어있으면 no은 0이고 큐가 가득 차 있으면 capacity와 같은 값이 된다.

추가한 데이터 개수를 알아내는 함수 : len()
큐에 추가한 데이터 개수를 반환

큐가 비어있는지를 판단하는 함수 : is_empty()
큐가 비어있는지를 판단해 비어있으면 True, 그렇지 않으면 False를 반환

큐가 가득 차 있는지를 판단하는 함수 : is_full()
큐가 가득 차서 더 이상 데이터를 추가할 수 없는 상태인지 판단해 가득 차 있으면 True, 그렇지 않으면 False를 반환

데이터를 넣는 함수 : enque()
큐에 데이터를 인큐하거나 큐가 가득 차서 인큐할 수 없는 경우에는 예외처리인 FixedQueueFull을 내보냄
인큐하기 위해 que[rear]에 데이터를 저장하고 rear와 no의 값을 1 증가시킨다. 인큐하기 전 rear의 값이 배열의 맨 끝인 경우에는 rear의 값을 1 증가시키면 그 값이 capacity와 같아져 인덱스의 한계를 넘긴다. 이럴때는 인큐한 뒤 rear의 값을 배열의 맨 앞 인덱스인 0으로 되돌린다.

데이터를 꺼내는 함수 : deque()
큐의 맨 앞부터 데이터를 디큐하여 그 값을 반환하며 큐가 비어있어 디큐할 수 없는 경우에는 FixedQueueEmpty를 내보냄.
디큐하기 위해 que[front]에 저장된 값을 꺼내고 front를 1 증가, no을 1 감소 시킨다. 디큐하기 전 front의 값이 맨 끝인 경우에는 front의 값을 1 증가시키면 그 값이 capacity와 같아져 인덱스의 한계를 넘긴다. 이럴때는 디큐한 뒤 front의 값을 배열의 맨 앞 인덱스인 0으로 되돌린다.

데이터를 들여다보는 함수 : peek()
맨 앞 데이터를 들여다보는 함수. 들여다보기만 하고 데이터를 꺼내지는 않아 front, rear, no의 값은 변하지 않는다. 큐가 비어있는 경우에는 예외처리 FixedQueueEmpty를 내보낸다.

검색하는 함수 : find()
큐의 배열에서 value와 같은 데이터가 포함되어 있는 위치를 알아내는 함수. 검색에 성공하면 찾은 원소의 인덱스를 반환하고 실패하면 -1을 반환.

데이터 개수를 세는 함수 : count()
큐에 있는 데이터의 개수를 구하여 반환하는 함수.

데이터가 포함되어 있는지를 판단하는 함수 : contain()
큐에 데이터가 들어있는지를 판단하는 함수. 들어있으면 True, 들어있지 않으면 False를 반환.

큐의 전체 원소를 삭제하는 함수 : clear()
현재 큐에 들어있는 모든 데이터를 삭제하는 함수

큐의 전체 데이터를 출력하는 함수 : dump()
큐에 들어있는 모든 데이터를 맨 앞부터 맨 끝 쪽으로 순서대로 출력하는 함수. 큐가 비어있으면 예외처리 FixedQueueEmpty를 내보낸다.

고정 길이 큐 FixedQueue 클래스를 만들어보자.

from typing import Any

class FixedQueue:
    
    class Empty(Exception):
        # 비어있는 FixedQueue에서 디큐 또는 피크할 때 내보내는 예외 처리
        pass

    class Full(Exception):
        # 가득 차 있는 FixedQueue에서 인큐할 때 내보내는 예외 처리
        pass
    def __init__(self, capacity: int) -> None:
        # 큐 초기화
        self.no = 0 # 현재 데이터 개수
        self.front = 0 # 맨 앞 원소 커서
        self.rear = 0 # 맨 끝 원소 커서
        self.capacity = capacity # 큐의 크기
        self.que = [None] * capacity # 큐의 본체

    def __len___(self) -> int:
        # 큐에 있는 모든 데이터의 개수를 반환
        return self.no

    def is_empty(self) -> bool:
        # 큐가 비어있는지 판단
        return self.no <= 0

    def is_full(self) -> bool:
        # 큐가 가득 차 있는지 판단
        return self.no >= self.capacity

    def emque(self, x: Any) -> None:
        # 데이터 x를 인큐
        if self.is_full():
            raise FixedQueue.Full # 큐가 가득 차 있는 경우 예외 처리 발생
        self.que[self.rear] = 0
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity:
            self.rear = 0
        
    def deque(self) -> Any:
        # 데이터를 디큐
        if self.is_empty():
            raise FixedQueue.Empty # 큐가 비어 있는 경우 예외 처리 발생
        x = self.que[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        return x

    def peek(self) -> Any:
        # 큐에서 데이터를 피크(맨 앞 데이터를 들여다봄)
        if self.is_empty():
            raise FixedQueue.Empty
        return self.que[self.front]

    def find(self, value: Any) -> Any:
        # 큐에서 value를 찾아 인덱스를 반환(없으면 -1을 반환)
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.que[idx] == value: # 검색 성공
                return idx
        return -1 # 검색 실패

    def count(self, value: Any) -> bool:
        # 큐에 있는 value의 개수를 반환
        c = 0
        for i in range(self.no): # 큐의 데이터를 선형 검색
            idx = (i + self.front) % self.capacity
            if self.que[idx] == value: # 검색 성공
                c += 1 # 들어 있음
        return c

    def __contain__(self, value: Any) -> bool:
        # 큐에 value가 있는지 판단
        return self.count(value)

    def clear(self) -> None:
        # 큐의 모든 데이터를 비움
        return self.front = self.rear = 0

    def dump(self) -> None:
        # 모든 데이터를 맨 앞부터 맨 끝 순으로 출력
        if self.is_empty(): # 큐가 비어 있음
            print('큐가 비었습니다.')
        else:
            for i in range(self.no):
                print(self.que[(i + self.front) % self.capacity], end='')
            print()

덱(deque)이란?

맨 앞과 맨 끝 양쪽에서 데이터를 모두 삽입 및 삭제할 수 있는 자료 구조. 큐와 스택을 합친 형태라고 생각하자. 파이썬에서는 collections.deque 컨테이너로 제공됨.