# 큐

• 처음에 저장한 데이터를 가장 먼저 꺼내는 선입선출 (FIFO : First In First Out) 구조로 되어 있다.
• 입출력이 양방향에서 이루어지는 데이터 구조이다.
• 삽입 연산을 Enqueue 삭제 연산을 Dequeue 라고 한다.

# 단점

• 데이터 삽입 후 계속 항목 삭제를 하면 REAR 와 FRONT 가 만나게 되어 공백 Queue 가 됨에도 불구하고 오버 플로우 현상이 생겨 메모리낭비 현상이 생기게 된다.

# 용도

• OS 의 작업 스케쥴링
• 대기행렬 처리

# 유의사항

Queue 에서 데이터를 추출할 때는 첫번째 저장된 데이터를 삭제하므로 배열리스트와 같은 배열 기반 Collection Class 를 사용하면 데이터를 꺼낼때마다 빈공간을 채우기 위해 데이터의 복사가 발생한다.

이는 성능저하를 야기 시키기 때문에 연결 리스트 (Linked List) 로 구현 하는것이 적합하다.

# Priority Queue (우선순위 큐)

우선순위가 높은 데이터가 먼저 작업 된다.

# 구현 방법

• 배열을 기반으로 구현
• 연결리스트를 기반으로 구현
• 힙 (Heap) 이용하여 구현

데이터가 적을때는 문제가 없지만 _데이터가 많을 경우에는 노드 수에 비례해서 비교를 하기 때문에 성능저하의 이슈_가 있다.
따라서 주로 힙 (Heap) 을 이용하여 구현 하는 것이 일반적이다.

# 데큐 / 디큐 / 덱 (Deque : Double-End Queue)

• Queue 와 Stack 을 합쳐놓은 형태이다.
• 두개의 포인터를 사용하여 양쪽에서 삽입과 삭제를 발생시킬수 있다.

# 특징

• 크기가 가변적이다.
  • 리스트와 같이 데이터를 담을 수 있는 크기가 가변적이다.
• 앞과 뒤에서 삽입과 삭제가 가능하다.
• 구현이 쉽지 않다.
• 랜덤 접근이 가능하다.
• 중간에 데이터의 삽입 및 삭제가 용이하지 않다.
  • 되도록이면 중간에 데이터를 삽입하거나 삭제하는 것은 피해야 하며, 삽입과 삭제를 중간에 한다면 삽입과 삭제한 위치의 데이터를 모두 이동해야 한다.

# 중간에 데이터 삽입 시

# 중간에 데이터 삭제 시

# Deque 를 사용하는 경우

다음과 같은 경우 Deque 를 사용하면 효과적이다.

• 앞과 뒤에서 삽입 혹은 삭제를 한다.
  • STL Container 라이브러리 중에서 Deque 사용할때 성능이 가장 좋다.
• 저장할 데이터의 개수가 가변적이다.
  • Deque 는 동적으로 크기가 변하므로 유연하게 사용 가능하다.
• 검색을 거의 하지 않는다.
  • 많은 데이터를 저장하며 검색이 필요한 경우라면 Map, Set, HashMap 중 하나를 선택해서 사용하는편이 효과적이다.
• 데이터 접근을 랜덤하게 하고 싶다.
  • Vector 와 같이 랜덤 접근이 가능하다. (사용방법도 같음)