큐

정의

First In First Out 이라는 개념을 가진 선형 자료구조

Linear Queue와 Circular Queue가 존재

---

특징

• Front: 큐의 맨 앞 요소
• Rear: 큐의 맨 뒤 요소
• EnQueue: 큐(의 가장 뒤)에 요소를 추가하는 것
• DeQueue: 큐(의 가장 앞)에서 요소를 제거하는 것
• 현실에서 비유하면 대기열이라고 할 수 있음

---

Linear Queue 를 Array 로 구현하는 경우

• Javascript Array 로 표현 가능하지만 배열의 길이가 고정되어 있지 않기 때문에 큐가 무한정으로 커질 수 있음
• DeQueue 를 한 뒤에 요소를 앞으로 당기게 되면 O(n) 의 시간이 소요됨

---

Linear Queue 를 Linked List 로 구현하는 경우

• Front 는 Head 가 되고 Rear 는 Tail 이 됨
• Array 와 다르게 인덱스에 대한 고민을 하지 않아도 됨

---

Javascript 에서 Linear Queue 구현 시 주의 사항

• Array.shift 메서드를 사용하게 되면 O(n) 의 시간이 소요되기 때문에 큐에서 기대되는 효과가 발생하지 않음
  따라서 Array 를 이용해 Queue 를 구현하는 경우 Array.shift 의 사용은 지양해야 함

---

Curcular Queue

• Front 와 Rear 가 이어져 있는 Queue
• 한정된 공간을 효율적으로 사용하기 위한 자료 구조
• Linked List 로도 구현 가능하지만 장점이 없음
• maxSize 를 통해 큐의 요소 개수를 제한