Queue

Queue는 선형자료구조로 First In First Out(FIFO) 구조를 따릅니다.
FIFO는 선입선출을 의미합니다.
한쪽 끝에서는 삽입만 일어나고 다른 한쪽 끝에서는 삭제만 일어납니다.

Queue의 유형

1. Simpe Queue
   가장 기본적은 Queue로 한쪽 끝에서만 삽입이 일어나고 다른 한쪽 끝에서는 삭제만 일어납니다.

2. Double-Ended Queue(Dequeue)
   양쪽 끝에서 삽입과 삭제가 둘 다 일어날 수 있습니다.
   약간의 변형도 존재합니다.

• Input Restricted Queue
  한쪽 끝에서만 삽입을 할 수있고 양쪽 끝에서 삭제가 가능합니다.
• Output Restricted Queue
  한쪽 끝에서만 삭제가 일어나고 양쪽 끝에서 삽입이 가능합니다.

3. Circular Queue
   특별한 형태의 Queue로 시작과 끝이 연결되어 원형 구조를 이루는 Queue를 말합니다.
   

4. Priority Queue
   특별한 형태의 Queue로 Queue의 요소들이 우선순위에 따라 접근이 됩니다.
   Priority Queue는 Heap과 Queue 두 개의 자료 구조를 이용해 구현하는 것이 일반적입니다.
   2가지 유형이 있습니다.

• Ascending Priority Queue
  우선순위에 따라 오름차순으로 정렬됩니다.
• Descending Priority Queue
  우선순위에 따라 내림차순으로 정렬됩니다.

Queue의 Operation

1. Enqueue
   큐의 끝에 값을 삽입합니다.

2. Dequeue
   큐의 끝에서 값을 가져오고 삭제합니다.

3. Peek or front
   큐의 맨 앞의 값을 삭제 없이 확인합니다.

4. rear
   큐의 맨 끝의 값을 삭제 없이 확인합니다.

5. isFull
   큐가 꽉 찼는지 확인합니다.

6. IsEmpty
   큐가 비었는지 확인합니다.

Queue의 이점

• 많은 양의 데이터를 쉽게 그리고 효율적으로 다룰 수 있게 만들어 준다.
• FIFO를 이용한 삽입과 삭제가 구현된다.
• 다수의 이용자들이 사용하는 특정 서비스에 유용하다.
• 데이터의 프로세스간 통신에서 빠른 속도를 보여준다.
• 다른 자료구조의 구현에 사용된다.

Queue의 단점

• 중간에 있는 데이터의 삽입과 삭제는 많은 시간을 요구한다.
• 검색은 평균적으로 O(N)의 시간을 요구한다.
• 배열을 이용한 Queue의 구현은 최대 크기를 정해야 한다.