Circular Queue

1. Circular Queue

• Queue와 같은 FIFO 구조이지만 순환하는 방식으로 dequeue로 생긴 빈 공간을 재활용 할 수 있음

• Queue와 동일하게 enqueue(x), dequeue(), peek(), isEmpty()가 있고, 가질 수 있는 최대 원소의 갯수가 정해져 있으므로 isFull() 메소드를 추가함

2. List를 이용한 구현

class CircularQueue:

    def __init__(self, n):
        self.maxCount = n
        self.data = [None] * n
        self.count = 0
        self.front = 0
        self.rear = 0
    
    def __repr__(self):
        if self.front + self.count < self.maxCount:
            return str(self.data[self.front:self.rear])
        else:
            return str(self.data[self.front:]+self.data[:self.rear])

    def size(self):
        return self.count

    def isEmpty(self):
        return self.count == 0

    def isFull(self):
        return self.count == self.maxCount

    def enqueue(self, x):
        if self.isFull():
            raise IndexError('Queue full')
        self.data[self.rear] = x
        self.rear = (self.rear+1)%self.maxCount
        self.count += 1

    def dequeue(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        x = self.data[self.front]
        self.front = (self.front+1)%self.maxCount
        self.count -= 1
        return x

    def peek(self):
        if self.isEmpty():
            raise IndexError('Queue empty')
        return self.data[self.front]

3. 테스트

print('# 최대크기 4의 환영 큐 생성')
cq = CircularQueue(4)
print('Queue:', cq)

print('\n# 1, 2, 3, 4 차례대로 삽입')
for item in [1, 2, 3, 4]:
    cq.enqueue(item)
    print('Queue:',cq)
    
print('\n# 원소 두번 꺼내기')
print('꺼낸 원소:', cq.dequeue())
print('꺼낸 원소:', cq.dequeue())
print('남은 Queue:', cq)

print('\n# Peek')
print('Peek한 원소:', cq.peek())

# 최대크기 4의 환영 큐 생성
Queue: []

# 1, 2, 3, 4 차례대로 삽입
Queue: [1]
Queue: [1, 2]
Queue: [1, 2, 3]
Queue: [1, 2, 3, 4]

# 원소 두번 꺼내기
꺼낸 원소: 1
꺼낸 원소: 2
남은 Queue: [3, 4]

# Peek
Peek한 원소: 3

소스코드 : circular_queue.py