카테고리 없음

기본 자료구조 - 큐

sungw00 2024. 8. 13. 23:40
728x90

큐 알아보기

큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조이다.

큐에 데이터를 추가하는 작업을 인큐(enqueue), 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다. 

또 데이터를 꺼내는 쪽을 프런트(front), 데이터를 넣는 쪽을 리어(rear)라고 한다.

 

배열로 큐 구현하기

스택과 마찬가지로 큐 또한 배열을 사용하여 구현할 수 있다.

아래 그림은 배열의 맨 앞부터 순서대로 4개의 데이터 19, 22, 37, 53이 들어있다.

배열 이름을 que라고 할 때 que[0] ~ que[3]까지 int형 데이터가 저장된다.(인덱스 0인 원소가 큐의 첫 번째 원소이다.)

이 상태에서 데이터 24를 인큐하고 19를 디큐하는 과정을 알아보자.

24를 인큐하기

맨 끝 데이터가 저장되어 있는 que[3]의 다음 원소인 que[4]에 24를 저장한다. 이때 처리의 복잡도는 O(1)이고 비교적 적은 비용으로 구현할 수 있다.

 

19를 디큐하기

que[0]에 저장되어 있는 19를 꺼내면서 2번째 이후의 모든 원소를 앞쪽으로 옮겨야 한다.

이 때 처리의 복잡도는 O(n)이다. 데이터를 꺼낼 때마다 이런 처리를 수행해야 한다면 프로그램의 효율성을 기대할 수 없다.

 

링 버퍼로 큐 구현하기

디큐할 때 배열 안의 원소를 옮기지 않는 큐를 구현하게 되는 경우 사용하는 자료구조는 링 버퍼이다. 

링 버퍼는 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조이다.

어떤 원소가 맨 앞 원소이고, 어떤 원소가 맨 끝 원소인지 식별하는 변수가 각각 front와 rear이다.

여기에서 프런트와 리어는 논리적인 데이터 순서일 뿐 배열의 물리적 원소의 순서는 아니다.

 

인큐와 디큐를 수행하면 front와 rear의 값은 변한다.

아래 과정을 통해 두 값이 변하는 과정을 알아보자.

4개의 데이터 68, 95, 21, 73이 늘어선 순서대로 que[5], que[6], que[7], que[0]에 저장된다.

front 값은 5이고 rear 값은 1이다.

 

아래는 82를 인큐한 다음의 상태이다.

맨 끝의 다음에 위치한 que[rear], 즉 que[1]에 82를 저장하고 rear값을 1 증가시켜 2로 만든다.

아래는 68을 디큐한 다음의 상태이다.

맨 앞 원소인 que[front], 즉 que[5]의 값인 68을 꺼내고 front 값을 1 증가시켜 6으로 만든다.

 

링 버퍼로 큐를 구현하면 원소를 옮길 필요 없이 front와 rear의 값을 업데이트하는 것만으로 인큐와 디큐를 수행할 수 있다.

이로써 모든 처리의 복잡도는 O(1)이다.

 

링 버퍼를 사용한 큐를 구현하는 프로그램

# 고정 길이 큐 클래스 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

 

예외 처리 클래스 Empty와 Full

비어 있는 큐에 deque( ), peek( ) 함수를 호출할 때 내보내는 예외 처리는 Empty 클래스이고, 가득 차 있는 큐에 enque( ) 함수를 호출할 때 내보내는 예외 처리는 Full 클래스이다.

 

초기화하는 __init__( ) 함수

__init__( ) 함수는 큐 배열을 생성하는 등의 준비 작업을 하며 다음과 같이 5개의 변수에 값을 설정한다.

  • que: 큐의 배열로서 밀어 넣는 데이터를 저장하는 list형 배열이다.
  • capacity: 큐의 최대 크기를 나타내는 int형 정수이다. 이 값은 배열 que의 원소 수와 일치한다.
  • front, rear: 맨 앞의 원소, 맨 끝의 원소를 나타내는 인덱스이다. 큐에 넣은 데이터 중에 가장 처음에 넣은 맨 앞 원소의 인덱스가 front이고, 가장 마지막에 넣은 맨 끝 원소의 바로 다음 인덱스가 rear이다. rear는 다음에 인큐할 때 데이터를 저장하는 원소의 인덱스이다.
  • no: 큐에 쌓여 있는 데이터 개수를 나타내는 int형 정수이다. 변수 front와 rear의 값이 같을 경우 큐가 비어 있는지 또는 가득 차 있는지 구별하기 위해 필요하다. 큐가 비어 있는 경우에는 no가 0이 되고, 가득 차 있는 경우에는 capacity와 같은 값이 된다.

 

추가한 데이터 개수를 알아내는 __len__( ) 함수

__len__( ) 함수는 큐에 추가한 데이터 개수를 반환한다. no의 값을 그대로 반환한다.

 

큐가 비어 있는지를 판단하는 is_empty( ) 함수

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

 

큐가 가득 차 있는지를 판단하는 is_full( ) 함수

is_full( ) 함수는 큐가 가득 차 있어서 더 이상 데이터를 추가할 수 없는 상태인지 검사한다. 가득 차 있으면 True를, 그렇지 않으면 False를 반환한다.

 

데이터를 넣는 enque( ) 함수

enque( ) 함수는 큐에 데이터를 인큐한다. 하지만 큐가 가득 차서 인큐할 수 없는 경우 예외 처리인 FixedQueue.Full을 내보낸다.

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

 

위 그림 중 좌측 그림은 맨 앞부터 순서대로 95, 21, 73, 82를 넣은 큐에 47을 인큐하는 모습이다.

que[rear]인 que[2]에 인큐하는 데이터를 저장하고 rear와 no의 값을 1 증가시키면 인큐가 완료된다.

 

그런데 우측 그림과 같이 인큐를 하기 전의 rear 값이 배열의 맨 끝에서는 rear값을 1 증가시키면 capacity의 값과 똑같이 되어 배열 인덱스의 한계를 넘어간다. 이런 경우 인큐의 모습을 보여준다.

rear에 1을 증가시킨 뒤 rear값이 큐의 크기인 capacity와 같을 경우 rear를 배열의 맨 앞 인덱스 0으로 되돌린다.

이렇게 하면 다음에 인큐하는 데이터가 que[0] 위치에 제대로 저장된다.

 

데이터를 꺼내는 deque( ) 함수

deque( ) 함수는 큐의 맨 앞부터 데이터를 디큐하여 그 값을 반환한다. 그러나 큐가 비어 있어 디큐할 수 없는 경우 예외 처리인 FixedQueue.Empty를 내보낸다.

def enque(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

 

디큐를 수행하는 과정은 아래와 같다.

위 그림 중 좌측 그림은 맨 앞부터 순서대로 68, 95, 21, 73, 82를 넣은 큐에서 68을 디큐하는 모습이다.

큐의 맨 앞인 que[front], 즉 que[5]에 저장된 값 68을 꺼내고 front를 1 증가, no를 1 감소시킨다.

 

그런데 우측 그림과 같이 디큐하기 전에 front가 배열의 맨 끝인 경우 front를 1 증가시키면 그 값이 capacity와 같아져서 배열 인덱스의 한계를 넘어간다. 그럴 땐 front의 값이 큐의 크기인 capacity와 같을 경우 front를 1 증가시켜 배열의 맨 앞 인덱스인 0으로 되돌린다. 

이렇게 하면 다음 디큐를 수행할 때 데이터를 que[0] 위치에서 제대로 꺼낼 수 있다.

 

데이터를 들여다보는 peek( ) 함수

peek( ) 함수는 맨 앞 데이터, 즉 다음 디큐에서 꺼낼 데이터를 들여다본다.

que[front]의 값을 반환할 뿐 데이터를 꺼내지는 않으므로 front, rear, no의 값은 변하지 않는다. 

큐가 비어 있을 때는 예외 처리 FixedQueue.Empty를 내보낸다.

 

검색하는 find( ) 함수

find( ) 함수는 큐의 배열에서 value와 같은 데이터가 포함되어 있는 위치를 알아낸다.

맨 앞에서 맨 끝쪽으로 선형 검색을 수행한다.

물론 스캔은 아래 그림처럼 배열의 맨 앞 원소가 아니라 큐의 맨 앞 원소(front)부터 시작한다.

따라서 스캔할 때 주목하는 인덱스 idx를 구하는 식은 (i + front) % capacity이다.

다음과 같이 i와 idx의 값이 변한다.

i 0 →  1 → 2 → 3 → 4 → 5 → 6 7
idx 5 6 7 0 1 2 3 4

 

검색에 성공하면 찾은 원소의 인덱스를 반환하고 실패하면 -1을 반환한다.

 

데이터 개수를 세는 count( ) 함수

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

 

데이터가 포함되어 있는지를 판단하는 __contains__( ) 함수

__contains__( ) 함수는 큐에 데이터(value)가 들어 있는지를 판단한다. 들어 있으면 True를, 그렇지 않으면 False를 반환한다.

내부의 count( ) 함수를 호출하여 구현한다.

 

큐의 전체 원소를 삭제하는 clear( ) 함수

clear( ) 함수는 현재 큐에 들어 있는 모든 데이터를 삭제한다.

인큐와 디큐는 no, front, rear의 값을 바탕으로 수행된다. 그러므로 값을 0으로만 하면 된다.(실제 큐 배열 que의 원솟값을 변경할 필요가 없다.)

 

큐의 전체 데이터를 출력하는 dump( ) 함수

dump( ) 함수는 큐에 들어 있는 모든 데이터를 맨 앞부터 맨 끝 쪽으로 순서대로 출력한다.

하지만 큐가 비어 있으면 '큐가 비어 있습니다.'를 출력한다.

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 __contains__(self, value: Any) -> bool:
    """큐에 value가 있는지 판단"""
    return self.count(value)

def clear(self) -> None:
    """큐의 모든 데이터를 비움"""
    self.no = 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()

 

큐 FixedQueue 클래스를 실제 사용하는 프로그램(fixed_queue.test.py)

# 고정 길이 큐 클래스(FixedQueue)를 사용하기

from enum import Enum
from fixed_queue import FixedQueue

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

def select_menu() -> 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)  # 최대 64개를 인큐할 수 있는 큐

while True:
    print(f'현재 데이터 개수: {len(q)} / {q.capacity}')
    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(f'피크한 데이터는 {x}입니다.')
        except FixedQueue.Empty:
            print('큐가 비었습니다.')

    elif menu == Menu.검색:   # 검색
        x = int(input('검색할 값을 입력하세요.: '))
        if x in q:
            print(f'{q.count(x)}개 포함되고, 맨 앞의 위치는 {q.find(x)}입니다.')
        else:
            print('검색값을 찾을 수 없습니다.')

    elif menu == Menu.덤프:   # 덤프
        q.dump()
    else:
        break

 

실행 결과

현재 데이터 개수: 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
인큐할 데이터를 입력하세요.: 1
현재 데이터 개수: 4 / 64
(1)인큐  (2)디큐  (3)피크  (4)검색  (5)덤프  (6)종료: 1
인큐할 데이터를 입력하세요.: 5
현재 데이터 개수: 5 / 64
(1)인큐  (2)디큐  (3)피크  (4)검색  (5)덤프  (6)종료: 5
1 2 3 1 5 
현재 데이터 개수: 5 / 64
(1)인큐  (2)디큐  (3)피크  (4)검색  (5)덤프  (6)종료: 4
검색할 값을 입력하세요.: 1
2개 포함되고, 맨 앞의 위치는 0입니다.
현재 데이터 개수: 5 / 64
(1)인큐  (2)디큐  (3)피크  (4)검색  (5)덤프  (6)종료: 3
피크한 데이터는 1입니다.
현재 데이터 개수: 5 / 64
(1)인큐  (2)디큐  (3)피크  (4)검색  (5)덤프  (6)종료: 2
디큐한 데이터는 1입니다.
현재 데이터 개수: 4 / 64
(1)인큐  (2)디큐  (3)피크  (4)검색  (5)덤프  (6)종료: 2
디큐한 데이터는 2입니다.
현재 데이터 개수: 3 / 64
(1)인큐  (2)디큐  (3)피크  (4)검색  (5)덤프  (6)종료: 2
디큐한 데이터는 3입니다.
현재 데이터 개수: 2 / 64
(1)인큐  (2)디큐  (3)피크  (4)검색  (5)덤프  (6)종료: 5
1 5 
현재 데이터 개수: 2 / 64
(1)인큐  (2)디큐  (3)피크  (4)검색  (5)덤프  (6)종료: 6

Process finished with exit code 0

 

링 버퍼의 활용

링 버퍼는 오래된 데이터를 버리는 용도로 활용할 수 있다. 

예를 들면 원소 수가 n인 배열에 데이터를 계속해서 입력할 때 가장 최근에 들어온 데이터 n개만 저장하고 나머지 오래된 데이터는 버리는 경우이다.

아래 코드는 리스트형 배열 a의 원소 수는 총 n개인데, 정수를 계속해서 입력(인큐)할 수는 있지만 배열에 저장되는 데이터는 가장 최근에 입력한 n개만 링 버퍼에 남아있도록 작성한 코드이다.

# 원하는 개수(n)만큼 값을 입력받아 마지막 n개를 저장

n = int(input('정수를 몇 개 저장할까요?: '))
a = [None] * n  # 입력받은 값을 저장하는 배열

cnt = 0 # 정수를 입력받은 개수
while True:
    a[cnt % n] = int(input((f'{cnt + 1}번째 정수를 입력하세요.: ')))
    cnt += 1

    retry = input(f'계속 할까요?(Y ... Yes / N ... No): ')
    if retry in {'N', 'n'}: # N이나 n을 입력하면 더 이상 값을 받지 않음
        break

i = cnt - n
if i < 0: i = 0

while i < cnt:
    print(f'{i + 1}번째 = {a[i % n]}')
    i += 1

 

실행 결과(n이 10일 때 12개의 정수를 입력받으면 마지막에 입력받은 정수 10개만 남게된다.)

정수를 몇 개 저장할까요?: 10
1번째 정수를 입력하세요.: 15
계속 할까요?(Y ... Yes / N ... No): y
2번째 정수를 입력하세요.: 17
계속 할까요?(Y ... Yes / N ... No): y
3번째 정수를 입력하세요.: 64
계속 할까요?(Y ... Yes / N ... No): y
4번째 정수를 입력하세요.: 57
계속 할까요?(Y ... Yes / N ... No): y
5번째 정수를 입력하세요.: 99
계속 할까요?(Y ... Yes / N ... No): y
6번째 정수를 입력하세요.: 21
계속 할까요?(Y ... Yes / N ... No): y
7번째 정수를 입력하세요.: 0
계속 할까요?(Y ... Yes / N ... No): y
8번째 정수를 입력하세요.: 23
계속 할까요?(Y ... Yes / N ... No): y
9번째 정수를 입력하세요.: 44
계속 할까요?(Y ... Yes / N ... No): y
10번째 정수를 입력하세요.: 55
계속 할까요?(Y ... Yes / N ... No): y
11번째 정수를 입력하세요.: 97
계속 할까요?(Y ... Yes / N ... No): y
12번째 정수를 입력하세요.: 85
계속 할까요?(Y ... Yes / N ... No): n
3번째 = 64
4번째 = 57
5번째 = 99
6번째 = 21
7번째 = 0
8번째 = 23
9번째 = 44
10번째 = 55
11번째 = 97
12번째 = 85

Process finished with exit code 0

 

위에서 입력받은 값을 배열 원소에 저장하는 과정은 아래와 같다.

1번째 값 입력받기

cnt 값은 0이고, 이것을 10으로 나눈 나머지는 0이다. 입력받은 값을 a[0]에 저장한다.

 

2번째 값 입력받기

cnt 값은 0이고, 이것을 10으로 나눈 나머지는 0이다. 입력받은 값을 a[1]에 저장한다.

 

(...생략...)

 

10번째 값 입력받기

cnt 값은 9이고, 이것을 10으로 나눈 나머지는 9이다. 입력받은 값을 a[9]에 저장한다.

 

11번째 값 입력받기

cnt 값은 10이고, 이것을 10으로 나눈 나머지는 0이다. 입력받은 값을 a[0]에 저장한다.

a[0]에 이미 1번째 값이 있지만 11번째 값이 덮어쓴다.

 

12번째 값 입력받기

cnt 값은 11이고, 이것을 10으로 나눈 나머지는 1이다. 입력받은 값을 a[1]에 저장한다.

a[1]에 이미 2번째 값이 있지만 12번째 값이 덮어쓴다.

 

입력받은 값을 저장하는 곳의 인덱스를 cnt % n으로 구하고, 그 뒤 cnt 값을 1 증가시켜 링 버퍼(배열)의 모든 원소를 순환하면서 저장하게 된다.

728x90