Skip to content

Circular Queue #
Find similar titles

원형 큐 (Circular Queue) #

기본 선형 큐의 한계점을 보완하기 위한 순환 구조를 가진 큐

  • 선형 큐를 크기가 정해져 있는 배열로 사용했을 경우, 삽입, 삭제를 반복하다 보면 전단이 배열의 마지막에 도착할 때 더 이상 큐를 사용할 수 없는 상황이 생긴다.
  • 메모리를 동적으로 사용할 수 없는 구조에서는 사용할 수 없기 때문에 전단의 위치를 유동적으로 변경해주는 방식
  • 전단의 다음 인덱스가 종단을 가리킬 경우 큐의 끝을 나타내는데. 이때 종단을 배열의 시작 위치로 변경하게 되면 순환 구조가 성립된다.

원형큐 클래스 구성 #

  • isEmpty : 큐가 비어있는지 여부 반환 True/False
  • isFull : 큐가 가득 차있는지 여부 반환 True/False
  • clear : 큐 초기화
  • len : 큐 요소 수 반환
  • enqueue : 큐 요소 삽입
  • dequeue : 큐 요소 반환(삭제)
  • peek : 큐의 맨 앞 요소 반환
  • print : 큐 요소 및 전단, 종단 출력

    MAX_SIZE = 10
    class CircularQueue :
        def __init__(self):
            self.front = 0
            self.rear = 0
            self.items = [None] * MAX_SIZE
    
        def isEmpty(self):
            return self.front == self.rear
    
        def isFull(self):
            return self.front == (self.rear+1)%MAX_SIZE
    
        def clear(self):
            self.front = self.rear
    
        def __len__(self):
            return (self.rear - self.front + MAX_SIZE) % MAX_SIZE
    
        def enqueue(self, item):
            if not self.isFull():
                self.rear = (self.rear + 1) % MAX_SIZE
                self.items[self.rear] = item
    
        def dequeue(self):
            if not self.isEmpty():
                self.front = (self.front+1) % MAX_SIZE
                return self.items[self.front]
    
        def peek(self):
            if not self.isEmpty():
                return self.items[(self.front+1)%MAX_SIZE]
    
        def print(self):
            out = []
            if self.front < self.rear:
                out = self.items[self.front+1:self.rear+1]
            else:
                out = self.items[self.front+1:MAX_SIZE] +
                self.items[0:self.rear+1]
    
            print(self.front, self.rear, out)
    
0.0.1_20210630_7_v33