Queue

본 문서는 2021년 12월 31일 에 작성되었습니다.

Dev 알고리즘 시리즈 중 자료구조 Doc 을 읽고 와주시면 감사하겠습니다.

---

Queue이란?

Queue 는 다음과 같은 특징을 가지고 있는 자료구조입니다.

1. FIFO (first in first out)
   1.1. 가로로 놓인 샌드위치를 만드는 개념이며, 가장 처음에 넣은 원소부터 꺼내야 한다.
2. DELETE 연산에서 삭제되는 원소가 정해져 있다.
3. INSERT 연산을 ENQUEUE 라고 한다.
4. DELETE 연산을 DEQUEUE 라고 부른다.

이러한 Queue 의 핵심 프로시저는 다음과 같습니다.
단 실제로 자료구조 라이브러리에 만들어져 있는 메서드의 수는 이보다 훨씬 많습니다.

1. ENQUEUE | 새 원소를 마지막 자리에 넣는다
2. DEQUEUE | 첫 번째 원소를 꺼낸다

아래의 프로시저에서 Q 는 Queue(큐형 배열)을 의미한다.

# ENQUEUE

Queue 가 포화되지 않았다는 것을 기본 전제로 한다.

Queue 의 꼬리에 x 값을 넣고

Queue 의 꼬리와 Queue 의 길이가
똑같다면, Q.tail 을 1로 바꾼다.
똑같지 않다면, Q.tail++ 을 한다.

ENQUEUE (Q, x)

   Q 의 포화를 검사하는 코드
   
   Q[Q.tail] = x
   if Q.tail == Q.length
      Q.tail = 1
   else
      Q.tail = Q.tail+1

# DEQUEUE

Queue 가 비어있지 않았다는 것을 기본 전제로 한다.

Queue 의 머리(FIFO)의 값을 잠시 저장해두고

Queue 의 머리와 길이가
똑같다면, 머리를 1로 바꾸고
똑같지 않다면, Q.head++ 를 한다.

그리고 x를 리턴한다.

DEQUEUE (Q)

   Q 가 비었는지 확인하는 코드

   x = Q[Q.head]
   if Q.head == Q.length
      Q.head=1
   else
      Q.head=Q.head+1
      
   return x

---

Java 에서 Queue 는?

Java(jdk 1.8이후) 에서는 Collection Framework 를 통해서,
Queue 를 구현해두었다.

이를 참고하여 사용하여도 괜찮지만,
Primitive Type 이 아닌 Wrapper Class 와 Generics 를 사용하기 때문에,
퍼포먼스가 신경쓰이고 Primitive 를 다룬다면 별도의 Stack 클래스를 만들어보는 것도 좋을 것 같다.

---

### 나아가서...

Queue 의 변형된 형태로는 Deque와 Priority Queue 등이 있다.

기본적으로 Queue 를 변형하였거나 본질이 아예 달라서 다음의 포스트에서 정리한 내용을 참고하면 좋을 것 같다.

Java : Collection Framework 중 Dequeue, Priority Queue
Heap Sort | Priority Queue Sort

---

백준 예제

10845번 큐
1158번 조세퍼스 문제

10866번 덱