Queue(Circular Queue)

circular queue는 capacity만큼의 공간을 가지고 있어서 max size를 넘으면 overflow가 발생한다.

이 점이 queue와 다른점이다.

 

circular queue를 구현하기 위해 나머지 연산을 통해 idx를 구한다.

 

# Title : Circular Queue
# Chapter : Queue
# 문제 : Circular Queue를 구현하여라

class CircularQueue:
    def __init__(self, k:int) -> None:
        self._data = [None] * k
        self._rearIdx = -1
        self._frntIdx = 0
        self._size = 0

    def enQueue(self, value: int) -> None:
        self._fullCheck()
        cap = len(self._data)
        self._rearIdx = (self._rearIdx + 1) % cap
        self._data[self._rearIdx] = value
        self._size += 1

    def deQueue(self) -> None:
        self._emptyCheck()
        cap = len(self._data)
        self._frntIdx = (self._frntIdx + 1) % cap
        self._size -= 1

    def Front(self) -> int:
        self._emptyCheck()
        return self._data[self._frntIdx]

    def Rear(self) -> int:
        self._emptyCheck()
        return self._data[self._rearIdx]

    def _emptyCheck(self) -> None:
        if self._size == 0:
            raise RuntimeError('Queue is empty')

    def _fullCheck(self) -> None:
        cap = len(self._data)
        if cap == self._size:
            raise RuntimeError('Queue is full')

circularQ = CircularQueue(4)
circularQ.enQueue(1)
circularQ.enQueue(3)
circularQ.enQueue(5)
circularQ.deQueue()
print(circularQ.Front(),circularQ.Rear())

 

 

참조 : (3) 코딩테스트, 초급, 원형큐, circular Queue - YouTube