자료구조 - [ Queue ]

큐는 먼저 넣은 데이터가 먼저 나오는 선입선출(FIFO) 구조로 저장되며, 일반적으론 작업 대기열로 많이 사용된다. 또한 Thread Pool에서 작업을 저장하는데 큐가 사용되며 순차적으로 먼저 들어온 작업을 처리하는 데 사용된다.. 또한 메시지와 관련한 서버 간의 통신을 위해 사용되는 메시지 큐, 그리고 시스템 버퍼에도 사용된다.

 

큐를 구현하는 방법으로는 크게 배열을 이용한 Circle Queue와 연결 리스트를 이용한 Queue가 있다.

 

---

1. Circle Queue (배열)

front는 데이터를 꺼낼 때 어떤 데이터를 꺼내야 하는지 배열의 index를 저장하는 값으로, 데이터를 꺼낸 후 1씩 증가한다. 

but 배열의 크기를 넘어서는 값을 가지지는 않는다.

 

* front의 변경 범위

0 <= front <= array.length -1

 

rear는 데이터를 넣을 때 어느 위치에 넣어야 하는지 배열의 index를 저장하는 값으로, 데이터 추가 후 rear는 1씩 증가한다.

but 배열의 크기를 넘어서는 값을 가지지는 않는다.

 

* rear의 변경 범위

0 <= rear <= array.length -1

 

 

---

1) Add

1. 큐가 꽉 찼는지 확인

2. rear의 값을 배열의 index로 접근하여 데이터 삽입

3. rear 값 1 증가

4. rear 값이 배열의 크기를 넘지 못하도록 mod 연산

 

 

---

2) Poll

1. 큐가 비어있는지 확인

2. front의 값을 배열의 index로 접근하여 데이터를 꺼낸 후 임시 저장

3. front의 값을 배열의 index로 접근하여 null 값을 삽입

4. front 값을 1 증가

5. front 값이 배열의 크기를 넘지 못하도록 mod 연산

 

---

Add와 Poll시 주의할 점

데이터를 꺼낼 때아 데이터를 넣을 때 front와 rear가 동일한 경우가 있다.

1. 큐가 꽉 차있을 때

2. 큐가 비어있을 때

이 두 가지 경우를 구분하기 위해서 front 또는 rear의 값을 배열의 index로 접근하여 저장된 값이 null인지 아닌지 구분해야한다.

 

 

---

일반 배열의 구현 시 한계점

런타임 환경에서 큐에 넣어야 할 데이터가 배열의 크기보다 클 경우 큐의 공간을 늘릴 수 없기 때문에 미리 많은 메모리 공간을 사용해야 하는데 사용하지 않을 경우 메모리 공간의 낭비가 발생한다. 이 문제를 해결하기 위해서는 가변 배열을 이용하거나, 연결 리스트를 이용해야 한다. (스택과 동일)

 

 

---

2. Queue (리스트)

front는 꺼내야 할 데이터의 노드를 가리킨다. null이면 큐가 비어있는 상황이다.

 

rear는 마지막 노드를 가리키며 새로운 노드를 추가시 마지막 노드의 다음 노드로 추가하기 위해 사용된다. null이면 큐가 비어있는 상황이다.

 

 

1) Add

1. 새로운 노드를 생성하고 데이터를 삽입

2. 큐가 비어있다면 front와 rear가 가리키는 노드를 새로운 노드로 한다.

3. 큐가 비어있지 않다면 rear가 가리키는 노드의 다음 노드로 새로운 노드를 연결

4. rear는 새로운 노드를 가리킨다.

 

 

---

2) Poll

1. front가 가리키는 노드의 데이터를 임시로 저장

2. front가 갈키는 노드를 삭제할 노드의 다음 노드로 가리킨다.

3. 만약에 큐의 노드가 1개이며 해당 노드를 삭제하는 경우는 rear의 값을 null로 변경

 

 

---

Add, Poll시 주의할 점

1) Add

큐가 비어있는 경우와 비어있지 않은 경우로 나누어, 큐가 비어있는 경우에 새로운 노드를 삽입시 맨 앞의 노드이면서 마지막 노드이므로 front와 rear는 새로운 노드를 가리켜야 함. 그러나 큐가 비어있지 않은 경우는 rear에만 신경쓰면 된다.

 

2) Poll

큐의 노드가 2개 이상인 경우에 노드를 삭제하는 경우 front에만 영향을 미치나, 큐의 데이터가 1개인 경우 노드를 삭제하면 해당 노드는 맨 앞의 노드이면서 마지막 노드이므로 front와 rear에 영향을 미치며 front와 rear는 null을 가리켜야 함

 

 

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼