큐란?

Preface

 

중간고사 이후 오랜만에 글을 업로드한다.

 

요즘엔 이런 저런 핑계를 대며 공부를 하지 않는 날이 많아진 것 같다.

 

저번 주만 해도 시험 공부를 한 뒤 한 두 시간 정도는 시간을 내 공부를 할 수 있었지만, 귀찮고 피곤하단 이유로 누워서 의미없는 시간을 보냈다.

 

매일 후회할 일을 하지 않고자 다짐해도 그게 말처럼 쉬운 일은 아닌 것 같다.

 

원하는 목표를 이루기 위해선 항상 초심을 잃지 말자.

 

이번 장에선 선입선출 자료구조인 큐에 대해 공부했는데, 코드 자체는 지난 번에 공부했던 스택과 크게 다른 부분이 없어 쉽게 이해하고 넘어갈 수 있었다.

 

또, 얼마 전까지만 해도 annotation과 enum의 사용이 헷갈리고 귀찮게 느껴졌지만, 여러 번 코드를 작성하다보니 나름 익숙해진 것 같다.

---

 

- 큐(queue) : 데이터를 임시 저장하는 자료구조

1) 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(FIFO)구조

2) 인큐(enqueue) : 큐에 데이터를 추가하는 작업

3) 디큐(dequeue) : 데이터를 꺼내는 작업

4) 프런트(front) : 데이터를 꺼내는 쪽

→ 맨 앞의 원소

5) 리어(rear) : 데이터를 넣는 쪽

→ 맨 끝의 원소

 

 

- 우선순위 큐(priority queue) : 인큐할 때 데이터에 우선순위를 부여하여 디큐할 때 우선순위가 가장 높은 데이터를 꺼내는 방식

→ heapq 모듈에서 제공 (6장에서 다룸)

 

 

- 링 퍼버(ring buffer) : 배열 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조

→ 원소를 옮길 필요 없이 front와 rear의 값을 업데이트하는 것만으로 인큐와 디큐 수행 가능

 

 

- 링 버퍼 코드

from typing import Any


class FixedQueue:
    class Empty(Exception):
        pass

    class Full(Exception):
        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 enque(self, x: Any) -> None:
        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

    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:
        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) -> Any:
        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) -> Any:
        return self.count(value)

    def clear(self) -> None:
        self.no = self.front = self.capacity = 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) : 맨 앞과 맨 끝 양쪽에서 데이터를 넣고 꺼낼 수 있는 양방향 대기열(지료구조)

→ collectionds.deque 컨테이너로 제공

 

 

- 링 버퍼 프로그램 코드

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)

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

 

 

- 링 버퍼 활용 프로그램 (가장 최근에 입력한 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'}:
        break

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

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