큐(Queue) 파이썬으로 구현하기

큐(Queue)는 데이터를 넣고빼는 자료구조 중 하나로, 먼저 삽입된 데이터가 먼저 추출되는 FIFO(First In First Out) 구조를 가지고 있다. 큐는 Front, Rear라는 두개의 포인터를 사용하여 데이터를 관리한다.

 

Front : 다음 추출될 데이터를 가리킨다.

Rear : 다음 데이터가 저장될 공간을 가리킨다.

 

데이터를 삽입하는 행위를 enque, 추출하는 행위를 deque라고 부른다. enque 및 deque 실행 시 포인터 관리에 유의해야 한다.

(구현 방법에 따라 포인터의 증감 순서는 조금씩 다를 수 있다.)

 

 

1. 변수

  1) Capacity : 크기

  2) Front : 큐의 맨 앞

  3) Rear : 큐의 맨 뒤

  4) No : 큐에 들어있는 데이터의 갯수

 

2. 함수

  1) enque() : 큐에 데이터를 넣는 함수

  2) deque() : 큐에서 데이터를 빼는 함수

  3) __len__() : 큐에 넣어있는 데이터의 갯수를 반환하는 함수

  4) dump() : 큐 안에 있는 데이터를 순차적으로 모두 읽는 함수

  5) peek() : 맨 앞 데이터를 들여다보는 함수

  6) find() : 큐에서 특정 값을 찾아 인덱스를 반환하는 함수

  7) count() : 큐 안에서 특정 값의 갯수를 찾아 반환하는 함수

  8) contains() : 큐 안에 특정 값의 존재 여부를 찾아 반환하는 함수

  9) clear() : 큐를 초기화하는 함수

  10) is_full() : 큐가 가득 찼는지 확인하는 함수

  11) is_empty() : 큐가 비었는지 확인하는 함수

 

3. Exception

  1) Empty : 큐가 빈 경우 발생하는 Exception

  2) Full : 큐가 가득 찬 경우 발생하는 Exception

 

* 구현 내용

class FixedQueue:
    
    class Full(Exception):
        pass

    class Empty(Exception):
        pass

    def __init__(self, c : int):
        self.capacity = c
        self.front = 0
        self.rear = 0
        self.no = 0
        self.queue = [None] * self.capacity

    def is_full(self) -> bool:
        if self.no >= self.capacity:
            return True
        else:
            return False

    def is_empty(self) -> bool:
        if self.no <= 0:
            return True
        else:
            return False

    def enque(self, data):
        if self.is_full():
            raise FixedQueue.Full
        self.queue[self.rear] = data
        self.rear += 1
        self.no += 1
        if self.rear == self.capacity:
            self.rear = 0

    def deque(self):
        if self.is_empty():
            raise FixedQueue.Empty
        r_data = self.queue[self.front]
        self.front += 1
        self.no -= 1
        if self.front == self.capacity:
            self.front = 0
        return r_data
        
    def __len__(self):
        return self.no

    def dump(self):
        if self.is_empty():
            print('큐가 비었습니다.')
        else:
            for i in range(self.no):
                print(self.queue[(i + self.front)%self.capacity])

    def peek(self):
        if self.is_empty():
            raise FixedQueue.Empty
        return self.queue[self.front]

    def find(self, value):
        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):
        c = 0
        for i in range(self.no):
            idx = (i + self.front) % self.capacity
            if self.queue[idx] == value:
                c += 1
        return c

    def contains(self, value):
        return self.count(value)

    def clear(self):
        self.no = 0
        self.front = 0
        self.rear = 0