큐

• 개념

  --> 입구와 출구가 따로 있는 원통 형태의 자료구조
  --> 스택과 달리, 먼저 들어간 것이 먼저 나오는 구조이다.
  --> 들어갈 때는 데이터를 지정해서 들어갈 수 있지만, 나올 때는 특정 데이터를 선택할 수 없다!!

• 원리

  --> 한쪽에서는 삽입만, 다른 쪽에서는 추출만 진행
  enQueue: 큐에 데이터 삽입
  deQueue: 큐에서 데이터 추출
  front: 추출하는 데이터의 위치 (데이터 중 첫 번째 데이터)
  rear: 삽입되는 데이터의 위치 바로 뒤 (데이터 중 마지막 데이터)

  enQueue: 데이터 삽입

  1) 큐에 데이터가 비어있는 상태 --> front = rear = -1
  2) rear를 한 칸 오른쪽으로 이동 --> rear += 1
  3) rear 위치에 화사를 입력

  deQueue: 데이터 추출 --> 맨 왼쪽의 데이터를 꺼내는 과정

  1) front를 한 칸 오른쪽으로 이동 --> front += 1
  2) front 위치의 데이터를 삭제

• 간단 구현

  1. 큐 생성 --> 배열 형태로 구현

  * front와 rear가 둘 다 -1인 상태이면 큐가 비었다는 의미이다.

  queue = [None, None, None, None, None]
  front = rear = -1

  2. 데이터 삽입: enQueue

  rear를 1 증가 -> rear 위치에 데이터 삽입

  rear += 1
  queue[rear] = '화사'
  rear += 1
  queue[rear] = '솔라'
  rear += 1
  queue[rear] = '문별'

  3. 데이터 추출: deQueue

  front 1 증가 -> front 위치의 데이터 밖으로 추출 -> front 위치의 데이터 None으로 변경

  # 초기 front값은 -1
  front += 1
  data = queue[front]
  queue[front] = None
  print('dequeue --> ', data)

• 일반 구현

  1. 큐 초기화

  SIZE = 5
  queue = [None for _ in range(SIZE)]
  front = rear = -1

  오른쪽이 입구, 왼쪽이 출구라고 가정하고 진행

  2. 데이터 삽입 과정

  1) 큐가 꽉 찼는지 확인하는 함수: rear의 값이 큐의 크기 -1이면 꽉 찬 상태

  def isQueueFull():
      global SIZE, queue, front, rear
      if (rear == SIZE - 1):
          return True
      else:
          return False

  2) 큐에 데이터를 삽입하는 함수

  def enQueue(data):
      global SIZE, queue, front, rear
      if (isQueueFull()):
          print('큐가 꽉 찼습니다.')
          return
      rear += 1
      queue[rear] = data

  3. 데이터 추출 과정

  1) 큐가 비었는지 확인하는 함수: front값과 rear값이 동일하면 큐가 비어있는 상태

  def isQueueEmpty():
      global SIZE, queue, front, rear
      if (front == rear):
          return True
      else:
          return False

  2) 큐에서 데이터를 추출하는 함수

  def deQueue():
      global SIZE, queue, front, rear
      if (isQueueEmpty()):
          print('큐가 비어있습니다.')
      return None
      front += 1
      data = queue[front]
      queue[front] = None
      return data

  4. 데이터 확인

  --> 다음에 추출될 데이터를 큐에 그대로 두고 확인만 하는 것 (peek)

  def peek():
      global SIZE, queue, front, rear
      if (isQueueEmpry()):
          print('큐가 비어있습니다.')
          return None
      return queue[front + 1]

• 기능 통합 버전 개선

  문제점: deQueue를 하면 큐의 앞쪽은 계속 비워지지만 다시 사용하지 않는다.

  여유 공간 확인 방법

  기존 방식

  if (rear값 == 큐크기 -1):
      큐가 꽉 찼음

  개선 방식

  def isQueueFull():
      global SIZE, queue, front, rear
      # 큐가 꽉 차지 않은 경우
      if (rear != SIZE - 1):
          return False
      # 큐가 꽉 찬 경우
      elif (rear == SIZE - 1) and (front == -1):
          return True
      # 큐의 앞 공간이 비어있는 경우
      else:
          for i in range(front + 1, SIZE):
              queue [i-1] = queue[i] # 왼쪽으로 한 칸씩 이동
              queue[i] = None
          front -= 1
          rear -= 1
          return False

• 큐의 응용: 원형 큐

  선형 큐의 한계점
  --> 큐의 앞쪽이 비어있고, 뒤쪽이 꽉 찬 상태에서 데이터를 삽입하려면 수많은 데이터를 왼쪽으로 한 칸씩 이동시켜야하는 오버헤드가 발생
  해결책
  --> 큐의 맨 앞과 맨 뒤를 이어 원형 큐로 만들면 오버헤드가 발생하지 않음

  1. 원형 큐 초기화

  --> 선형과 다르게 front, rear 값을 0으로 초기화한다.

  2. 원형 큐가 비어있는 경우

  --> front와 rear의 값이 같은 경우

  3. 원형 큐가 꽉 차있는 경우

  --> rear + 1과 front의 값이 같은 경우
  * 원형 큐는 선형 큐와 다르게 전체 크기에서 한 칸을 사용하지 못한다.
  --> 모든 칸이 다 차있으면, front값과 rear의 값이 같아서 큐가 비어있는 것으로 인식한다.

  4. 데이터 삽입, 추출

  --> 선형 큐와 같다. 하지만, 마지막 칸 다음은 다시 0이므로, 해당 값 처리만 바꾸면 된다.

• 원형 큐 일반 구현

## 함수 선언 부분 ##
def isQueueFull():
    global SIZE, queue, front, rear
    if ((rear + 1) % SIZE == front):
        return True
    else:
        return False
def isQueueEmpty():
    global SIZE, queue, front, rear
    if (front == rear):
        return True
    else:
        return False
def enqueue(data):
    global SIZE, queue, front, rear
    if (isQueueFull()):
        print('큐가 꽉 찼습니다.')
        return
    rear = (rear + 1) % SIZE # 0을 처리하기 위해서
    queue[rear] = data
def deQueue(data):
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print('큐가 비었습니다.')
        return None
    front = (front + 1) % SIZE
    data = queue[front]
    queue[front] = None
    return data
def peek():
    global SIZE, queue, front, rear
    if (isQueueEmpty()):
        print('큐가 비었습니다.')
        return None
    return queue[(front + 1) % SIZE]
## 전역 변수 선언 부분 ##
SIZE = int(input('큐 크기를 입력하세요. --> '))
queue = [None for _ in range(SIZE)]
front = rear = 0