큐(queue)

큐

스택과 같이 데이터를 임시 저장하는 자료구조이다. 하지만 스택과 반대로 가정 먼저 넣은 데이를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out) 구조를 가진다.예: 놀이공원에서 보통 줄 서는 구조

 

큐에 데이터를 넣을 떄는 인큐(enqueue), 큐에서 데이터를 꺼낼 때는 디큐(dequeue) 함수를 정의

데이터를 직접 꺼내는 것이 아니라 두개의 포인터(front, rear) 를 사용해서 위치를 나타낸다.

 

코드

# 고정 길이 큐 구현하기 with 링 버퍼.
# 기존의 리스트로 dequeue 구현 시 시간 복잡도가 O(n) 으로 상당히 비효율적이다.
# 이를 해결하기 위해 링 버퍼를 사용.
from typing import Any


class FixedQueue:
    class Empty(Exception):
        pass

    class Full(Exception):
        pass

    def __init__(self, capacity: int) -> None:
        # 큐의 크기, 머리 인덱스, 꼬리 인덱스, 데이터의 개수, 본체
        self.capacity = capacity
        self.front = 0
        self.rear = 0
        self.no = 0
        self.queue = [None] * capacity

    def is_empty(self) -> bool:
        return self.no <= 0

    def is_full(self):
        return self.no >= self.capacity

    # 데이터를 넣는
    def enqueue(self, value: Any) -> None:
        # 만약 가득차 있으면 못 넣는다.
        if self.is_full():
            raise FixedQueue.Full

        self.queue[self.rear] = value
        self.no += 1
        self.rear += 1
        # 끝 부분이 크기를 넘어가면 0으로 바꿔준다.
        if self.rear == self.capacity:
            self.rear = 0

    # 데이터를 꺼내는
    def dequeue(self) -> Any:
        # 만약 큐가 비어있으면 데이터를 꺼낼 수 없다.
        if self.is_empty():
            raise FixedQueue.Empty

        value = self.queue[self.front]
        self.front += 1
        self.no -= 1
        # 머리 부분이 큐의 크기를 넘어가면 0으로 바꿔준다.
        if self.front == self.capacity:
            self.front = 0
        return value

    # 데이터를 들여다보는 ( 꺼낼 데이터를 확인한다.)
    def peek(self) -> Any:
        if self.is_empty():
            raise FixedQueue.Empty

        return self.queue[self.front]

    # 검색하는
    def find(self, value: Any) -> int:
        # 들어있는 데이터의 개수만큼 포문
        for i in range(self.no):
            # 인덱스가 전체크기를 넘어설 경우를 대비하기 위해 크기로 나눈 나머지가 인덱스
            idx = (i + self.front) % self.capacity
            if self.queue[idx] == value:
                return idx
        return -1

    # 데이터 개수를 세는
    def count(self, value: Any) -> int:
        cnt = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.queue[idx] == value:
                cnt += 1
        return cnt

    # 데이터가 포함되어 있는지를 판단하는
    def __contains__(self, value: Any) -> bool:
        return self.find(value) >= 0

    # 큐의 전체 원소를 삭제하는
    def clear(self) -> None:
        self.no = self.front = self.rear = 0

    # 큐의 전체 데이터를 출력하는
    def dump(self) -> None:
        # 큐가 비어있으면
        if self.is_empty():
            print('큐가 비어있다.')
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            print(self.queue[idx], end=' ')


my_queue = FixedQueue(10)
# print('비어있을 때 디큐')
# my_queue.dequeue()
my_queue.enqueue("엔큐")
my_queue.enqueue("엔엔큐큐")
print('파인드: 없는 값', my_queue.find('엔큐ㅋ'))
print('파인드: 있는 값', my_queue.find('엔큐'))
print('피크: ', my_queue.peek())
print('카운트:', my_queue.count('엔엔큐큐'))
print('포함관계: ', my_queue.__contains__('엔큐23'))
print('포함관계: ', my_queue.__contains__('엔큐'))
print('전체 데이터: ', end=' ');
my_queue.dump()