큐 (Queue)

[ 개념 및 구조 ]

입구와 출구가 따로 있어 한쪽에서는 입력만, 다른 한쪽에서는 출력만 하도록 만든 자료구조입니다. 따라서 먼저 들어간 것이 먼저 나오는 FIFO(First-In First-Out) 형식으로 작업이 이루어집니다.

일반적으로 맛있는 음식점에서 대기 줄을 설 때 먼저 온 사람이 먼저 가고 중간이 끼어드는 것이 없는 것처럼 큐는 먼저 들어온 데이터가 먼저 나가고 새로운 데이터가 들어오면 항상 맨 뒤에 배치하게 됩니다.

[ 기능 ]

• ENQUEUE(PUSH)
  큐에 데이터를 추가합니다.
• DEQUEUE(POP)
  큐에서 가장 앞에 있는 데이터를 꺼냅니다. (스택의 POP과 달리 들어온 순서대로 꺼냅니다.)
• FRONT
  큐에서 가장 앞에 있는 데이터를 반환합니다.
• SIZE
  큐에 들어있는 데이터의 수를 반환합니다.
• IS_EMPTY
  큐가 비어 있는지 확인합니다.

[ 구현 ]

• 연결리스트를 이용한 구현
  큐는 원형 연결리스트를 이용하여 구현할 수 있습니다.
  
  큐에서는 입출력을 위한 접근 수단으로 Head 대신 REAR(뒤쪽) 포인터를 이용합니다.
  '큐는 입구와 출구가 따로 있는데 접근수단이 하나면 한 쪽은 매번 끝까지 따라가야 하는 거 아니야?'라고 생각할 수 있겠지만, 원형 연결리스트에서는 맨 뒤에 있는 노드와 맨 앞에 있는 노드가 연결되어 있기 때문에 REAR 포인터만으로도 충분히 빠르게 맨 앞에 있는 노드에 접근할 수 있습니다.

• 배열을 이용한 구현

  큐는 데이터가 뒤로 들어오지만, 앞에서부터 빠져나가기 때문에 배열을 이용해 큐을 구현한다면 할당한 공간에서 사용하지 못하는 공간이 생깁니다. 하지만 데이터 하나가 나갈 때마다 나머지 모든 데이터를 앞으로 이동한다면 효율이 상당히 떨어지겠죠? 다른 방식을 고려해봅시다.

  큐가 원형 모양이라면 데이터가 빠져나간 공간까지 활용할 수 있을 것 같습니다. 직선 모양인 배열을 우리는 Modular 연산을 통해 원형처럼 사용할 수 있습니다. 이때, 맨 앞의 데이터(빠져나갈 데이터)를 가리키는 FRONT INDEX와 다음 데이터가 들어올 공간 가리키는 REAR INDEX를 두겠습니다.
  

  
  데이터 출력 시 FRONT INDEX를 증가시켜 삭제된 효과를 볼 수 있습니다. (다만, FRONT INDEX가 배열 끝에 도달하면 처음으로 돌아오도록 FRONT INDEX = (FRONT INDEX + 1) % MAX SIZE와 같이 증가시킵니다. 데이터 입력 시에도 마찬가지로 REAR INDEX에 데이터를 입력하고, REAR INDEX = (REAR INDEX + 1) % MAX SIZE로 증가시켜 REAR INDEX를 순환시키면 빠져나간 데이터 자리도 활용할 수 있습니다.
  
  여기서 주의할 점은 비어있는 큐에서 데이터를 출력하거나 가득 차 있는 상태에서 데이터를 입력하여 사용 중인 데이터가 덮어쓰이지 않도록 처리해야 합니다. COUNT 변수를 추가하여 데이터 입출력 시 현재 큐가 비어있는지 가득 차 있는지 확인할 수 있습니다.

[ 활용 ]

시간 순서대로 처리해야 할 여러 작업들이 즉시 수행되지 못한다면 작업이 들어올 때 큐에 넣어두고 순서대로 처리할 수 있습니다.