[JAVA]링크드리스트로 큐 구현하기 (Queue)

큐는 먼저 들어온 것이 먼저 나가는 구조이다. 은행에 먼저 온 사람이 빠른 번호표를 부여받고, 먼저 나가는 원리를 생각하면 쉽다.

이 구조를 구현하기 위해서는 큐에서 나갈 차례를 기억하고 있어야하는데,  이를 위해서 몇가지 장치가 필요하다.

 

많이 사용하는 용어들이 있다. 

(1) Enqueue: 큐 맨 뒤에 어떤 요소를 추가한다. 마지막으로 온 손님에게 번호표를 발부해주는 것과 비슷하다.

(2) Dequeue: 큐 맨 앞쪽의 요소를 삭제한다. 손님의 업무가 끝나면 번호표를 삭제하는 것과 비슷하다. 

(3) front: 큐의 맨 앞 위치이다. 다음 서비스를 받을 손님 번호의 역할을 한다.

(4) Peek: front에 위치한 데이터를 읽는다. 다음 서비스를 받을 손님의 번호를 확인한다.

(5) rear: 큐의 맨 뒤 위치이다. 마지막에 온 손님 번호의 역할을 한다.

 

연결 리스트 기반으로 큐 구현하기

배열로 큐를 구현한다면, 크기를 미리 정해야한다는 단점이 있다. 반면 연결리스트로 구현하면 큐의 크기를 미리 정할 필요가 없다.