#4 큐(Queue)

1. 큐(Queue)

 큐는 대기열이라는 이름 그대로 먼저 들어온 데이터가 먼저 추출되는 선입선출(FIFO)의 선형 자료구조이다.

스택이 top 에서만 삽입/삭제가 이루어졌던 것에 비해 큐의 경우 삭제만 이루어지는 front 와 삽입만 이루어지는

rear 로 이루어진다.  주요 연산은 다음과 같다.

• 데이터 삽입
  • enqueue(e) : 데이터 e를 큐의 맨 뒤인 rear 에 삽입한다.
• 데이터 삭제
  • dequeue() : 큐의 맨 앞인 front 의 데이터를 제거하고 제거된 데이터를 반환한다.

 

2.  큐의 활용

• 그래프의 너비 우선 탐색에 활용된다.
  
  
• OS의 스케줄링에서 프로세스들의 요청을 저장하거나 인터넷/전화 회선상에서 고객의 요청을 저장하는 등
  요청이 쌓이는 속도가 처리속도보다 빠른 경우라면 거의 대부분 유용하게 사용된다.

 

3. 파생 자료구조

• 데크(Dequeue)
  • 일반적인 큐와 달리 front 와 rear 양쪽에서 삽입/삭제가 모두 가능한 자료구조
    
    
  • 스택과 큐의 기능을 합쳐놓은 듯한 자료구조이다.
• 우선순위 큐
  • 들어간 순서가 나오는 순서가 되는 일반적인 큐와 달리 나중에 들어갔어도 지정된 우선순위가 보다
    높은 데이터가 먼저 추출되는 큐
  • 배열이나 리스트로 구현할 경우 우선순위에 맞는 위치에 삽입하기 위해 O(N)의 시간복잡도를 보이기 때문에
    O(logN)의 시간복잡도로 삽입 가능하며 항상 최솟값 혹은 최댓값이 먼저 추출되도록 할 수 있는 heap 을 
    사용하여 구현된다.  이에 대해서는 heap 을 설명할 때 자세히 다루기로 한다.
• 원형 큐
  • 큐의 front 와 rear가 맞닿아있는 형태의 큐
    
    
  • 원형 연결 리스트와 거의 동일하며 실제로 원형 연결 리스트를 그대로 원형 큐처럼 사용할 수 있다.