chapter 4-2. 큐

큐 = 데이터를 임시 저장하는 자료구조

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

 

인큐(enque) :큐에 데이터를 추가

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

프론트(front) : 데이터를 꺼내는 쪽 >> 맨 앞의 원소

리어 (rear) : 데이터를 넣는 쪽 >> 맨 끝의 원소

 

 

 

링 버퍼 = 배여 맨 끝의 원소 뒤에 맨 앞의 원소가 연결되는 자료구조

프론트(front) : 맨 앞 원소의 인덱스

리어(rear) : 맨 끝 원소 바로 다음의 인덱스(다음 인큐되는 데이터가 저장되는 위치)

링 버퍼로 큐를 구현하면 원소를 옮길 필요 없이 front와 rear 의 값을 업데이트하는 것만으로 인큐와 디큐를 수행할 수 있다. 모든 처리의 복잡도는 O(1)이다.

 

 

 

#고정길이 큐 클래스 FixedQueue 구현하기
 
from typing import Any
 
 
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_full(self) -> bool:
        """큐가 가득 차 있는지 판단"""
        return self.no >= self.capacity
    def is_empty(self) -> bool:
        """큐가 비어 있는지 판단"""
        return self.no <= 0
 
    def enque(self, s: Any) ->None:
        """데이터 x를 인큐"""
        if self.is_full():
            raise FixedQueue.Full  #큐가 가득 차 있는 경우 예외 처리 발생
        self.que[self.rear] = x
        self.que[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.capcacity
            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) ->Non4e:
        """큐의 모든 데이터를 비움"""
        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()