[자료구조] 큐(Queue)

  큐(Queue)란 선입선출(FIrst In First Out; FIFO), 먼저 들어온 데이터가 먼저 나가는 구조입니다. 단방향에서의 삽입과 삭제가 가능한 스택과 달리, 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조입니다. 관공서, 은행, 우체국, 병원 등에서 번호표를 이용한 줄서기가 대표적인 큐의 예시입니다.

  큐는 선형 자료구조이므로 1차원 배열 또는 단순 연결 리스트로 구현합니다. 그러나 배열로 구현하는 경우 삽입과 삭제를 거듭하면 큐의 항목이 배열의 오른쪽 부분으로 편중되는 문제가 발생합니다. 새 항목은 뒤에 삽입되고 삭제는 앞에서 일어나기 때문입니다. 이를 해결하는 방법 중 하나는 큐의 항목을 배열의 앞부분으로 이동시켜 배열의 마지막 원소가 첫 원소와 맞닿아 있도록 구현하는 것입니다.

  연결 리스트를 사용하면 배열에 비해 쉽게 구현이 가능하고, 다양한 메소드를 지원합니다.

 

  큐 자료구조는 CPU의 태스크 스케줄링, 네트워크 프린터, 실시간 시스템의 인터럽트 처리 등에 사용됩니다. 이진 트리의 레벨 순회와 그래프에서 너비 우선 탐색에도 사용됩니다.

  배열로 구현한 큐의 add와 remove 연산은 각각 O(1) 시간이 소요됩니다. 하지만 배열 크기를 확대 또는 축소시키는 경우에 큐의 모든 항목을 새 배열로 복사해야 하므로 O(n) 시간이 소요됩니다.

  단순 연결 리스트로 구현한 큐의 add와 remove 연산은 각각 O(1) 시간이 소요됩니다. 삽입 또는 삭제 연산이 rear와 front로 인해 연결 리스트의 다른 노드들을 일일이 방문할 필요 없이 각 연산이 수행되기 때문입니다. 배열과 단순 연결 리스트로 구현된 스택의 장단점은 리스트를 배열과 단순 연결 리스트로 구현했을 때의 장단점과 동일합니다.

 

  큐에서의 용어

• front(또는 head): 큐의 앞쪽
• rear(또는 tail): 큐의 뒤쪽

 

  주요 메소드

• enqueue(): rear에 요소를 추가
• add(): rear에 요소를 추가, 용량 초과 시 예외 발생
• offer(): rear에 요소를 추가, 용량 초과 시 false 반환
• dequeue(): front에 있는 요소를 제거하고 반환
• remove(): front에 있는 요소를 제거하고 반환, 큐가 비어 있을 시 예외 발생
• poll(): front에 있는 요소를 제거하고 반환, 큐가 비어 있을 시 null 반환
• peek(): front 원소 반환, 제거는 하지 않음

 

front(head)	←	rear(tail)
dequeue remove poll		enqueue add offer

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.