[자료 구조] 큐(Queue)

큐는 선입선출 즉, 먼저 들어간 데이터가 먼저 나오는 자료구조이다.
이를, FIFO(First in first out)이라고도 하고 선입선출이라고도 한다.

큐를 쉽게 이해하기 위해서 실생활에서 예를 하나 찾아보면, 공용 화장실을 생각해보면 쉽게 이해가 되실 거 같습니다. 누군가 먼저 화장실 안에 들어가서 볼일을 보고 있을 때, 뒤에 온 사람들은 먼저 온 순서대로 대기하고, 먼저 온 사람이 볼일을 끝내면 다음 사람이 들어가는 것이 자료구조 큐의 형태입니다.

주요 연산으로는 put과 get이 있는데, put은 큐에 새로운 데이터를 추가하는 연산이고, get은 큐에서 가장 오래된 데이터를 추출하는 연산이다.

데이터가 큐의 크기보다 많아진 경우를 오버플로우(overflow), 더 이상 추출할 데이터가 없는 경우를 언더플로우(underflow)라고 한다.

종류

• 선형 큐

  • 막대 모양의 큐, 데이터 입/출력 시 모든 자료를 한 칸씩 옮겨야한다는 단점이 있다.
  • 큐의 전단과 후단을 이용하여 입/출력 시의 문제를 해결 할 수 있지만, 입/출력을 하면 할 수록 가용 공간이 줄어드는 문제가 발생한다.
  • Github에서 코드 보기

• 순환 큐

  • 원형의 큐를 만듦으로써 전단, 후단이 배열의 마지막 인덱스에 위치하고 있으면 배열의 처음으로 인덱스를 옮겨 선현 큐에서 발생하는 가용 공간이 줄어드는 문제를 해결한 자료구조이다.
  • 큐의 포화 상태를 확인하기 위해서 큐의 크기를 지정한 가용 공간보다 1 높여 생성한다. 후단이 전단보다 1 작으면 포화 상태이고, 전단과 후단의 값이 같으면 큐가 빈 상태이다.
  • 큐의 크기가 정해져 있어 불편할 수도 있지만 예측 가능한 상황이거나, 성능이 중요할 경우에는 순환 큐를 사용한다.(링크드 큐는 입/출력 시에 오버헤드가 발생하기 때문)
  • Github에서 코드 보기

• 링크드 큐

  • 순환, 선형 큐를 모두 구현할 수 있으며, 오버플로우가 발생하지 않는 장점이 있다. 즉, 가변적인 크기의 큐를 생성할 수 있다.
  • 제거할 경우 제거된 노드를 메모리에서 해제시키는 로직이 추가된다.
  • 노드의 포인터로 인해 메모리가 상대적으로 더 많이 사용된다.
  • Github에서 코드 보기

Usage

• I/O Buffer
• 프린터의 출력 순서 관리