java queue : 어떻게 사용하는지 간단히 알아봅시다.

 java에서 Queue는 어떻게 사용할까요? 저번 시간에 리스트를 잘 보셨다면, 대략적으로 감이 오실 거에요. 아. 이건 빼박 리스트구나. 사실 동적 배열을 이용해도 되는데요. 이것은 잘 생각해 보세요. 예제 프로그램을 봅시다.

 

 

 일단 저는 my_Object 객체를 Queue에 넣을 거에요. 이건 아마 딱 봐도, 미로 찾기나, 어느 지점에서부터 최단 거리를 구할 때 쓰는 것 같군요. 이제 main 함수를 볼까요?

 

 

 16번째 줄이 보이시나요? 저는 LinkedList를 쓸 거에요. LinkedList는 deque를, deque는 queue를 implements를 한 관계입니다. 이것은 Collections 시간에 다시 정리해 봅시다. 일단 오늘은, 아 이런 게 있구나. 정도만 보시면 되겠습니다. 사실 큐의 특성을 잘 생각해 보면, 3개의 연산만 지원이 되면 됩니다.

 

 뒤에서 push하고, 앞에서 pop 하고. 사실 이것은 링크드 리스트 시간에 배웠습니다. insertion과 delete 연산은, 내가 연산이 일어나는 위치만 빠르게 알 수 있다면, 빠르게 수행될 수 있다고 했는데, LinkedList가 딱 그렇습니다. 그러면, Java에서는 Queue를 쓸 때, Linked List 콜렉션을 이용하면 된다는 겁니다.

 

 

---

 먼저 Q.add(new my_object(...)); 가 어떻게 동작하는지 함수를 타고 들어가 봅시다.

 

 

 그러면 linkLast(e)가 들어오는데요. 뭔지 모르겠지만, 마지막에 추가한다고 합니다. 마지막이라는 위치를 알고 있다면, 당연하게도, O(1)에 추가할 수 있을 거에요. 메서드 안으로 계속 들어가 봅시다.

 

 

 그러면 현재 last의 위치를 l이라는 녀석이 가지고 있어요. 이 상태에서 Node<> 생성자를 타 봅시다.

 

 

 그러면 여러 가지 처리를 해 주는데요. this.next에 null 값이, this.prev의 값에 이전에 last였던, 파란색으로 칠한 노드를 가리키는 어떠한 값이 들어갑니다. 979번째 줄이 수행된 순간, 메모리의 상황을 간략하게 그려보면 아래와 같습니다.

 

 

 그러면 그 다음에 어떻게 해야 할까요? 일단 last가 새롭게 추가된 노드를 가리켜야 할 겁니다.

 

 

 다음에, 기존 item의 next 필드가 초록색 노드를 가리키면 될 거에요.

 

 

 이렇게 말입니다. 그런데, LinkedList가, 추가되기 전에 비어 있었다면 어떻게 해야 할까요?

 

 

 143번째 줄까지 끝나고 나서 상황입니다. 이 때 LinkedList의 first가 item을 가리키면 되지 않을까요? 반대로, peek()이나, poll()은 어떤가요? 이 둘의 차이점은 명확합니다. 가장 앞에 있는 노드를 가져오기만 하느냐, 아니면 가져오고 제거까지 하느냐.

 

 

---

 가장 앞에 있는 것을 제거하는 경우 또한 2가지로 나눌 수 있어요.

 

 

 모두 제거하면, List가 비는 경우. 이 때에는, 그냥 first하고 last가 nil을 가리키게 하면 됩니다. 그게 아니라면 어떻게 하면 좋을까요?

 

 

 일단 first가 초록색이 아닌, 파란색 노드를 가리키게 합니다.

 

 

 그리고 first의 prev가 nil을 가리키게 합니다. 그러면 초록색으로 가는 링크가 끊기기 때문에, 초록색으로 칠한 것은 가비지가 됩니다. peek()은 내부적으로 그리 구현이 되어 있습니다.

 

 

---

 이제 예제 프로그램을 차근 차근 봅시다.

 

 

 먼저 19번째 줄에 Q.add라고 되어 있어요. 이는 List의 last에만 추가하는 건데요. (0,0)부터 (4,4)까지의 데이터가 추가될 거에요. 그러면, LinkedList 객체의 last 필드가 계속 업데이트 될 거에요.

 

 

 다음에, 22번째 for문 블록에서, Q.peek()를 호출합니다. 이것은 맨 앞에, 즉, first가 가리키는 object를 리턴만 하는 건데요. i가 0이고 j가 0일 때, 즉 List에 데이터가 모두 들어가고 나서, 삭제 연산이 일어나지 않은 경우, 맨 앞에 있는 객체는 데이터 (0, 0)일 겁니다. 그것만 리턴이 되고, 실제 List에서 제거가 되지는 않아요.

 

 Q.poll()을 하면, 객체가 리턴이 되면서, List에서 제거까지 됩니다. 그 차이가 있어요. 그러면, 큐에서 중요한 건 무엇인가요? 비었는데 poll이나, peek이 호출되면 안 됩니다. 사실 null 값이 리턴되긴 합니다만, 왠만하면 코너 처리는 하고 들어가는 게 좋아요. 그렇기 때문에, 이런 연산들을 수행하기 전에, queue가 비었는지를 검사해야 하는데요. LinkedList에도 그러한 함수가 있습니다. isEmpty() 메서드는 List가 비었는지 검사합니다.

 

 

 프로그램을 실행한 예제는 다음과 같습니다. 되게 많은데요. queue에 쓸 4개 메서드인 add, peek, poll, isEmpty. 이 4개만 알면 무난하게 쓰실 수 있습니다.