Linear Queue (선형 큐)

큐 설명

• 큐(Queue)의 특성
  • 스택과 마찬가지로 삽입과 삭제의 위치가 제한적인 자료구조
    • 큐의 뒤에서는 삽입만 하고, 큐의 앞에서는 삭제만 이루어지는 구조
  • 선입선출구조(FIFO : First In First Out)
    • 큐에 삽입한 순서대로 원소가 저장되어, 가장 먼저 삽입(First in)된 원소는 가장 먼저 삭제(First Out)
• 큐의 선입선출 구조

• 큐의 사용을 위해 필요한 주요 연산

• 큐의 연산 과정

공백 큐 생성

원소 A 삽입

원소 B 삽입

원소 반환/삭제

원소 C 삽입

원소 반환/삭제

원소 반환/삭제

• 선형 큐
  • 1차원 배열을 이용한 큐
    • 큐의 크기 = 배열의 크기
    • front : 저장된 첫 번째 원소의 인덱스
    • rear : 저장된 마지막 원소의 인덱스
  • 상태 표현
    • 초기 상태 : front = rear = -1
    • 공백 상태 : front = rear
    • 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)
• 큐의 구현

# 선형 큐에서 front와 rear의 초기값은 -1
front, rear = -1, -1

# 삽입
def enQueue(item):
    global rear
    if isFull():
        print('Queue_Full')
    else:
        rear += 1
        Q[rear] = item

# 삭제
def deQueue():
    global front
    if isEmpty():
        print('Queue_Empty')
    else:
        front += 1
        return Q[front]

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

# 포화상태 검사
def isFull():
    return rear == len(Q) - 1

# 검색
def Qpeek():
    if isEmpty():
        print('Queue_Empty')
    else:
        return Q[front+1]

• 선형 큐 이용시의 문제점
  • 잘못된 포화상태 인식
    • 선형 큐를 이용하여 원소의 삽입과 삭제를 계속할 경우, 배열의 앞부분에 활용할 수 있는 공간이 있음에도 불구하고, rear = n - 1 인 상태 즉, 포화상태로 인식하여 더 이상의 삽입을 수행하지 않게 됨

• 해결방법 1

- 매 연산이 이루어질 때마다 저장된 원소들을 앞부분으로 모두 이동
- 원소 이동에 많은 시간이 소요되어 큐의 효율성이 급격히 떨어짐

• 해결방법 2

- 1차원 배열을 사용하되, 논리적으로는 배열의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정
- 원형 큐의 논리적 구조