Byeonguk Kim

안녕하세요. 29살의 조금은 늦은 나이로 새롭게 개발자로 시작하는 신입 개발자입니다. 포트폴리오 [https://deaguowl.github.io]

자료구조 07. 원형큐(circular queue)

02 Jul 2019 » 자료구조

2019.07.02 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

원형규

스크린샷 2019-07-03 오후 5 24 12

  1. circular queue(원형큐)
    1. 크기가 정해져 있는 배열!! or linked list로도 만들 수 있다.
    2. head, tail
    3. 배열, head, tail 만 있으면 구현할 수 있다.
  2. 구현 특징
    1. 핵심포인트 : 텅빈 큐를 어떻게 표현할 것이냐?/ tail이 인덱스를 벗어낫을 떄 어떻게 처리할 것인가?
    2. 텅빈 큐는 head == tail 이면 비었다고 표현한다.
    3. full은 한 칸을 버리지만 tail + 1을 했을 때 h면 full로 표현한다.
    4. tail은 마지막 데이터의 다음을 가르키게 구현을 한다.
  3. 큐사이즈는 정해주거나, 작은 숫자를 바탕으로 테스트하면 좋다.

class CQueue:
    #모든 인스턴스가 필요하면 클래스 멤버로 선언

    MAXSIZE = 10

    def __init__(self):
        #리스트 컨프렌션
        self.__container = [None for _ in range(CQueue.MAXSIZE)]
        #인포메이션 하이딩
        self.__head = 0
        self.__tail = 0

    def is_empty(self):
        if self.__head == self.__tail:
            return True
        return False

    def is_full(self):
        next = self.__step_forward(self.__tail)
        if next == self.__head:
            return True
        return False

    def enqueue(self, data):
        if self.is_full():
            raise Exception("The queue is full")

        self.__container[self.__tail] = data
        #tail은 마지막 데이터의 다음을 가르킨다.
        self.__tail = self.__step_forward(self.__tail)

    def dequeue(self):
        if self.is_empty():
            raise Exception("The queue is empty")

        result = self.__container[self.__head]
        self.__head=self.__step_forward(self.__head)
        return result

    def peek(self):
        if self.is_empty():
            raise Exception("The queue is empty")
        return self.__container[self.__head]

    # 편의함수
    def __step_forward(self, x):
        x+=1
        if x >= CQueue.MAXSIZE:
            x = 0
        return x

if __name__ == "__main__":
    cq = CQueue()

    for i in range(5):
        cq.enqueue(i)

    while not cq.is_empty():
        print(cq.dequeue(), end = "   ")

Related Posts