[5.13] 링 버퍼로 큐 구현하기

링 버퍼로 큐 구현하기

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

-> FIFO에서 First Out을 하는 경우, 나머지 모든 원소의 인덱스를 변경해야 하는 문제(O(n)) 해결

 

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 <= 0
    
    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) -> bool:
        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:
        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()
    

양방향 대기열 덱의 구조 -> collections.deque 컨테이너(파이썬)

덱 deque - double-ended queue - 앞/끝 양쪽에서 데이터를 삽입/삭제할 수 있는 자료구조. 

 

링 버퍼로 큐 프로그램 만들기

- 스택과 기본적인 구조가 같다. 

from enum import Enum
from class_making 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) #capacity 64

while True:
    print(f'현재 데이터 개수 : {len(s)} / {s.capacity}')
    menu = select_menu()

    if menu == Menu.인큐:
        x = int(input('데이터를 입력하세요: '))
        try:
            q.enque()
        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

cf) 링 버퍼의 활용

- 오래된 데이터를 버리는 용도로 활용하기

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