원형 큐 (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)