Circular Queue (원형 큐)

설명

• 초기 공백 상태 : front = rear = 0
• Index의 순환
  • front와 rear의 위치가 배열의 마지막 인덱스인 n-1을 가리킨 후, 그 다음에는 논리적 순환을 이루어 배열의 처음 인덱스인 0으로 이동해야 함
  • 이를 위해 나머지 연산자를 사용
• front 변수
  • 공백 상태와 포화 상태 구분을 쉽게 하기 위해 front가 있는 자리는 사용하지 않고 항상 빈자리로 둠
• 삽입 위치 및 삭제 위치

• 원형 큐의 연산 과정

• 원형 큐의 구현

# 원형 큐에서 front와 rear의 초기값은 0
front, rear = 0, 0

# Index의 순환을 위해서 front와 rear은 n-1 다음에 0으로 이동해야함
# 이를 위해 나머지 연산자 mod()를 사용

# 삽입
def enQueue(item):
    global rear
    if isFull():
        print('Queue_Full')
    else:
        rear = (rear + 1) % len(cQ)
        cQ[rear] = item
    
# 삭제
def deQueue():
    global front
    if isEmpty():
        print('Queue_Empty')
    else:
        front = (front + 1) % len(cQ)
        return cQ[front]

def delete():
    global front
    if isEmpty():
        print('Queue_Empty')
    else:
        front = (front + 1) % len(cQ)

# 공백상태 검사
def isEmpty():
    return front == rear

# 포화상태 검사
def isFull():
    return (rear + 1) % len(cQ) == front

 

• 이 외에도 큐에는 '연결 큐', '우선순위 큐' 등이 있다. 해당 큐에 대한 설명은 추후에 보다 자세히 다루고자 한다.