Queue

특성
1) 삽입, 삭제의 위치가 제한적인 자료구조
2) 선입선출구조.

• 맨 앞: Front, 머리
• 맨 뒤: Rear, 꼬리
• 삽입: enqueue
• 삭제: dequeue

종류
1) 선형 큐

• 간단하고 기본적인 형태.
• 리스트 사용
  2) 원형 큐
• 선형에서 발전된 형태
• 리스트 사용
  3) 연결 큐
• 연결 리스트 형식을 이용
  4) 우선순위 큐
• 응용

선형 큐
1) 구현

• 초기: create queue
• enQueue(item)
• deQueue
• isEmpty(), isFull(): 공백 및 포화상태 검사
• Qpeek()
  2) 장점
• 삽입, 삭제의 처리속도 빠름
  3) 문제점
• 잘못된 포화상태 인식
• 리스트 크기 고정 -> 사용할 큐 크기만큼을 미리 확보 -> 메모리 낭비 발생

4) 보완책

• 원형 큐 사용으로 메모리 절약
• 리스트의 특성을 사용한 큐 사용으로 메모리 절약. 단, 단점으로 삽입, 삭제 등의 연산 수행에 많은 시간 소모.

원형 큐

• 1차원 리스트를 사용하되, 논리적으로 리스트의 처음과 끝이 연결되어 원형 형태의 큐를 이룬다고 가정하고 사용함
  1) 특징
• 초기 공백상태: front = rear = 0
• index의 순환: front와 rear의 위치가 리스트의 마지막 인덱스인 n-1을 가리킨 후, 논리적 순환을 이루어 리스트의 처음 인덱스인 0으로 이동해야 함.
• front 변수: 공백/포화 상태 구분을 쉽게 하기 위해 front 자리는 항상 비워둠.
• 삽입/삭제위치: 큐의 값보다 커지면 %n 연산 진행.
  2) 기본 연산과정

우선순위 큐
- FIFO 순서가 아니라 우선순위가 높은 순서대로 먼저 나가게 됨.
- 리스트 또는 우선순위 라이브러리 사용
1) 순서
- 리스트를 이용하여 자료 저장
- 원소를 삽입하는 과정에서 우선순위를 비교하여 적절한 위치에 삽입하는 구조
- 가장 앞에 최고 우선순위의 원소가 위치하게 됨
2) 문제
- 리스트를 사용하므로, 삽입이나 삭제 연산이 일어날 때 원소의 재배치가 발생
- 소요시간 길다.
3) 해결책
- PriorityQueue(maxsize) 클래스 사용
- 힙 자료구조 사용
4) 버퍼
- 데이터를 한 곳에서 다른 한 곳으로 전송하는 동안 일시적으로 그 데이터를 보관하는 메모리 영역
- 버퍼링: 버퍼를 활용하는 방식 또는 버퍼를 채우는 동작을 의미
- 일반적으로 입출력 및 네트워크와 관련된 기능에서 이용
- 순서대로 입력/출력/전달되어야 하므로 FIFO 방식의 자료구조인 큐가 활용됨.

BFS(Breath first search)

• 시작점의 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 시작점으로 하여 다시 인접한 장점들을 차례로 방문하는 방식
• 인접한 정점들을 탐색한 후, 차례로 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐 활용