큐 : Queue (+ 우선순위 큐)

큐는 들어간 순서 그대로 출력되는 선입 선출의 형태를 가진 자료구조이다.
그대로 직역하면 대기줄이라는 번역이 되는데, 당연히 대기줄은 먼저 온 순서대로 진행이 된다.

데이터가 들어와서 자료구조에 입력되는 위치는 뒤인데, 이것은 Rear 또는 Back이라고 한다.
데이터가 나가는 위치는 앞으로, Front라고 한다.

우선순위 큐, 원형 큐 등의 다양한 파생 형태도 존재한다.

• 순차 큐
  • 1차원 배열을 이용한 큐이다.
    • 큐의 크기는 배열의 크기이다.
    • front는 저장된 첫 번째 원소 - 1의 인덱스를 저장한다.
    • rear는 저장된 마지막 원소의 인덱스를 저장한다.
      
      
  • 상태 표현은 이런 식이다 :
    • 초기 상태 : front = rear = -1
    • 공백 상태 : front = rear
    • 포화 상태 : rear = n - 1 (n : 배열의 크기, n - 1 : 배열의 마지막 인덱스)
    •  즉, 이런 식의 식을 알고 있다면 직접 구현하는데 직관적인 작성을 할 수 있다.
  • 순차 큐의 고질병
    • 순차 큐의 잘못된 포화상태 인식
      • 큐에서 삽입-삭제를 반복하는 경우 큐 안의 아이템은 점점 뒤쪽으로 밀린다. 하지만 앞에서 이야기한 포화 상태인 rear = n - 1에 도달하므로 더 이상의 삽입을 수행하지 못하게 된다.
        • 그럼 어쩌자고요??
          • 방법 1. 저장된 원소들을 배열의 앞부분으로 이동시킨다.
            • 순차자료에서의 이동 작업은 연산이 복잡하기 때문에 효율성이 떨어진다.
          • 방법 2. 1차원 배열을 사용 하되, 논리적으로 배열의 처음과 끝이 연결되어 있다고 추상화하고 사용해본다.
            • 이 방법은 원형 큐를 이야기하기도 한다.

 

•  원형 큐
  • 원형 큐의 초기 공백 상태는 front = rear = 0 이다.
  • front 와 rear의 위치가 배열의 마지막 인덱스인 n - 1에서, 논리적 다음 위치인 0번 이동을 위해 나머지 연산자를 사용해야 한다.
  • 3 % 4 = 3
•  

종류	삽입 위치	삭제 위치
순차 큐	rear = rear + 1	front = front + 1
원형 큐	rear = (rear + 1) mod n	front = (front + 1) mod n

• 공백 상태와 포화 상태 구분을 쉽게 하기 위해, front가 위치한 자리는 항상 빈자리로 두게 끔 한다.

 

연결 리스트 형태의 큐, 쌍방향 입력-출력이 가능한 deQue도 있다. 천천히 다루겠다.