Queue : 큐

---

1. Queue란?

---

• queue의 사전적 의미는 줄, 대기 행렬
• 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In First Out, 선입선출)구조로 데이터를 저장
• 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용
• 예) 프린터의 출력 처리, 윈도 시스템의 메시지 처리기, 프로세스 관리 등

큐의 종류

• 직선 큐 (선형)

• 순환 큐 (원형)

직선 큐의 문제점과 순환 큐

직선 큐에서 큐는 용량이 커질수록 성능이 저하된다.
자바와 같은 언어에서는 배열의 크기가 정해져 있고, 원소는 스스로 움직이지 않음
때문에 뒤에 많은 원소가 남아있을수록(큐에 저장된 데이터가 많을수록) 원소를 당겨오는 연산을 많이 수행
이 때, front와 rear의 위치만 바꿔주면 이 문제를 해결할 수 있음
하지만 이 경우도 또 다른 문제가 발생
head가 계속해서 뒤로 움직이기 때문에 연산을 할수록 큐의 가용용량이 줄어듦
실제로 앞에 데이터가 들어갈 공간이 있지만 이 공간을 활용하지 못함
직선 큐가 가지는 불리한 점을 개선하기 위해 큐의 시작과 끝을 연결하는 순환 큐가 등장

2. Queue ADT

---

front - 큐의 맨 앞 위치
rear - 큐의 맨 뒤 위치
enqueue - 큐에 데이터 삽입
dequeue - 큐에서 데이터 삭제
size - 큐에 저장된 데이터의 수를 반환
reset - 큐 비우기

큐의 규칙을 위배하지 않으면 원하는 속성과 메소드를 취향껏 추가할 수 있음!
위의 속성과 메소드가 절대적인 것 X

3. Pseudo Code

---

자바스크립트(JavaScript) 배열로 구현하면 간단하게 구현이 가능
의사 코드는 객체로 구현하는 것으로 작성

• enqueue
  데이터를 저장하고 있는 객체의 키를 숫자로 써서 인덱스를 표현하고 값에 데이터를 저장
  큐가 비어있을 때는 front와 rear가 모두 0을 가리킴
  이 상태를 예외처리 하지 않으면 데이터를 1개 삽입했을 때 front는 0이고 rear는 1이 됨
  따라서 큐가 비어있을 때 처음 데이터를 삽입하는 상황은 조건문으로 처리
  큐에 데이터가 1개만 있을 때는 front와 rear가 모두 1을 가리키도록 구현할 것임
  데이터를 삽입할 때는 큐의 마지막에 추가하기 때문에
  저장소[rear++] = 삽입할 데이터 (rear값이 ++됨, 자동적으로 새로 추가된 데이터를 rear가 가리킴)
• dequeue
  데이터를 삭제할 때는 제일 앞의 데이터를 삭제
  delete 저장소[front]
  front++ 연산으로 front 위치를 바꿔 줌
• size
  저장소가 가진 키의 개수를 반환
• reset
  그냥 저장소 = {}; 초기화