[자료구조] 큐 (Queue)

1) 추상 큐(Abstract Queue)

• 선입 선출(FIFO : First-In-First-Out) 자료구조
• 선형 정렬을 이용
• 삽입과 삭제가 개별적으로 실행
• 삽입(Push Into)에 어떤 객체든 제한이 없으며, 그 객체는 큐의 Back
• 큐의 처음 객체는 Front
• 삭제(Pop From)는 큐의 현재 Front에서 실행
• 모든 큐의 연산은 O(1)시간 복잡도를 가져야 함

배열 큐(Array Queue)

• 단출입구 배열로는 모든 연산이 O(1) 시간 복잡도를 만족하지 못함

• 양출입구 배열로 O(1) 시간 복잡도를 만족함

template <typename Type>
class Queue
{
    private:
        int queue_size; // 현재 큐 사이즈
        int ifront; // front index
        int iback;  // back index
        int array_capacity; // 최대 수용량
        Type *array;    // Queue Array
    public:
        Queue( int = 10 );
        ~Queue();
        bool empty() const;
        Type front() const;
        void push( Type const & );
        Type pop();
};

순환 큐(Circular Queue)

• 필요성
  • 배열 크기가 16, 16 Push와 5 Pop을 시행했을 때 큐 크기는 11로 줄어듦
  • 이러한 경우 더 이상의 객체를 배열 큐에 삽입할 수 없음.

• 순환 배열 구조로 문제를 해결

연결 리스트 큐(Linked List Queue)

• 단일 연결 리스트를 사용하는 큐 클래스로서 하나의 Private 멤버 변수 List를 가짐

template <typename Type>
class Queue
{
    private:
        Single list<Type> list;
    public:
        bool empty() const;
        Type front() const;
        void push(Type const &);
        Type pop();
};

너비 우선 트리 탐색

• 가로 방향 즉 너비를 우선하여 트리 구조를 탐색
• 루트 노드를 큐에 저장
• 큐에 객체가 존재하는 동안 아래 연산을 반복
  1. Front에서 삭제(Pop)
  2. 모든 아래 노드를 큐에 삽입(Push)

STL(Standard Template Library)

#include <iostream>
#include <queue>
using namespace std;
int main() 
{
    queue <int> iqueue;
    iqueue.push( 13 );
    iqueue.push( 42 );
    cout << "Head: " << iqueue.front() << endl;
    iqueue.pop(); // no return value
    cout << "Head: " << iqueue.front() << endl;
    cout << "Size: " << iqueue.size() << endl;
    return 0;
}

2) 우선 순위 큐

• 시간의 우선 순위
  • 삽입된 순서에 따라 저장
  • 스택 : 후입 선출
  • 큐 : 선입 선출
• 일반화 된 우선 순위
  • 우선 순위에 따라 저장
  • 우선 순위 큐 : 도착 시간에 상관없이 할당된 우선 순위를 따름
• 키의 필요 여부
  • 우선 순위 큐에서는 키(= 우선 순위 값) 필드가 필요
  • 스택, 큐에서는 시간에 따라 자료구조를 조직화하게 되므로 키 필드가 불필요

추상 자료형 우선 순위 큐

• create : 새로운 우선순위 큐를 만들기
• Destroy : 사용되던 우선순위 큐를 파기하기
• Add : 현재 우선순위 큐에 새로운 레코드를 삽입하기
• Remove : 가장 우선순위가 높은 레코드를 삭제하기
  • 어떤 레코드가 우선 순위가 가장 높은지를 큐 자체가 알고 있음
  • 호출 함수 쪽에서는 아무런 인자도 넘길 필요가 없다.
• IsEmpty : 현재 우선 순위 큐가 비어있는지 확인하기

정렬된 배열을 이용한 구현

• 우선 순위를 기준으로 오름차순으로 정렬
• 가장 우선 순위가 큰 레코드는 항상 배열의 마지막에 위치
• 삭제 함수는 마지막 레코드를 리턴, 배열 레코드의 개수를 하나 줄임
• 이 작업의 시간적 효율은 O(1)
• 삽입 함수는 일단 키 값을 기준으로 이진 탐색 하는데 O(lgN)
• 데이터 이동에 O(N)

정렬 안 된 배열을 이용한 구현

• 새로운 레코드를 무조건 배열 끝에 붙임
• 삽입의 효율은 O(1)
• 삭제의 효율은 O(N). 처음부터 끝까지 찾아야 함
• 정렬된 배열과 정렬 안 된 배열을 사용할 때의 삽입, 삭제 효율은 서로 뒤바뀐 모습
• 삭제가 빨라야 한다면 정렬된 배열, 삽입이 빨라야 한다면 정렬 안 된 배열
• 삽입, 삭제 전체를 감안하면 두 방법 모두 O(N)의 효율

내림차순 정렬 연결 리스트를 이용한 구현

• 우선 순위가 가장 높은 레코드를 헤드 포인터가 직접 가리킴
• 삭제 시간은 O(1)
• 삽입 함수는 키 값을 기준으로 삽입 위치를 찾아야 함
• 최악의 경우 마지막 위치. O(N)
• 배열처럼 이동은 불필요
• 삭제와 삽입 모두를 감안한 효율은 O(1) + O(N) = O(N)

정렬 안 된 연결 리스트를 이용한 구현

• 삽입될 레코드를 가장 첫 노드로 만들면 삽입은 O(1)
• 삭제를 위해 가장 큰 레코드를 찾는데 O(N)
• 삭제와 삽입 모두를 감안한 효율은 O(N) + O(1) = O(N)

이진 탐색 트리를 이용한 구현

• 루트로부터 출발해서 RChild를 계속 따라 감
• 더 이상 RChild가 없으므로 자식이 하나이거나 없는 노드
• 상대적으로 쉬운 삭제
• 삭제 함수의 효율은 O(lgN). 루트로부터 리프까지 내려감
• 삽입 위치를 찾아 리프 노드까지 내려가는데 O(lgN)
• 효율은 O(lgN) + O(lgN) = O(lgN) (단, 균형 트리에 한함)

구현 방법별 효율 비교

3) 히프를 이용한 우선 순위 큐

• 히프(Heap) : “쌓아 놓은 더미”
• 최대 히프(Max Heap)
  • 키 값이 큰 레코드가 우선 순위가 높은 것으로 간주
  • 루트 노드의 키가 가장 큼
• 최소 히프(Min Heap)
  • 최대 히프와는 정반대
  • 키 값이 작을수록 우선 순위가 높음
• 정렬
  • 이진 탐색 트리는 값의 크기를 기준으로 삽입되기 때문에 왼쪽 노드보다 오른쪽 노드가 더 큰 값을 가짐
  • 히프는 키를 기준으로 값을 정렬하기 때문에 값들끼리의 상관관계는 없음

히프의 구성

1. “히프 = 완전 이진 트리”
   • 배열로 표시하는 것이 가장 효율적
   • 루트부터 시작해서 위에서 아래로, 왼쪽에서 오른쪽으로 진행
   • 노드 필기하는 순서로 트리를 순회하면서 인덱스를 부여
   • 루트 노드는 배열 인덱스 0
2. 히프는 배열로 표시
   • 히프의 부모 자식 관계는 다음과 같은 배열의 인덱스 연산으로 바뀜
   • 인덱스 K에 있는 노드의 왼쪽 자식은 (2K + 1)에, 오른쪽 자식은 (2K + 2)에 위치함
   • 인덱스 K에 있는 노드의 부모 노드는 (K - 1) / 2에 위치함

삽입 연산

• 배열 마지막 요소에 새로운 노드 삽입
• 부모와 비교하여 자식이 우선 순위가 높을때 위치를 교환
• 부모가 자식보다 우선 순위가 높을때까지 반복
• 업 히프(Up Heap)

삭제 연산

• 우선 순위가 가장 큰 루트 노드를 삭제
  • 루트를 직접 삭제하면 이후 히프를 재구성하는 것이 복잡
  • 배열 마지막 요소를 루트 노드 위치에 덧씌움
• 다운 히프(Down Heap)

히프의 정렬

• 히프에서 Remove를 가하면 키가 제일 큰 레코드가 빠져 나옴
• 빈 트리가 될 때까지 계속적으로 삭제를 가함
• 빠져 나온 레코드를 순차적으로 적어나가면 그것이 바로 정렬된 결과
• 내림차순: Max Heap
• 올림차순: Min Heap

연산 효율

• O(lgN)
  • 배열의 마지막 레코드를 처음으로 복사하는데 O(1)
  • 최악의 경우 루트로부터 리프까지 굴러 떨어짐
  • 비교의 횟수는 총 2lgN이 됨
  • 스와핑은 Temp = A, A = B, B = Temp라는 3번의 복사
  • 최악의 경우 스와핑에 의한 복사의 횟수는 3lgN
• “히프가 이진 탐색 트리보다 유리”
  • 트리의 높이
  • 이진 탐색 트리는 최악의 경우 연결 리스트와 유사. O(N)의 효율
  • 히프는 완전 이진 트리로서 균형 트리
  • 균형 트리의 높이는 항상 lg(N)에 가까움
  • 배열로 표시되어야 하므로 최대 레코드 개수를 미리 예상해야 함

하향식 히프 구성

• 빈 히프에서 출발하여 삽입에 의해서 히프를 구성
  • 노드가 삽입될 때마다 대략 lgN의 경로를 거쳐 위로 올라감
  • N개가 삽입된다면 NlgN의 효율
  • 삭제 역시 하나씩 빠져 나가면서 루트로 간 레코드가 lgN 경로를 타고 내려와야 하므로 NlgN에 해당
  • 정렬의 효율은 O(NlgN) + O(NlgN) = O(NlgN)

상향식 히프 구성

• 일단 트리를 구성
  • H, S, O, R, T 순으로 노트 필기하듯이 일단 트리를 구성
• 히프 구조가 되도록 재조정
  • 가장 아래쪽부터 검사하되 오른쪽에서 왼쪽으로 진행
  • 어떤 노드가 히프의 요건을 만족시키는지 검사
  • 해당 노드와 그 아래쪽 노드 간의 키만 비교. 아래쪽으로만 스와핑
  • 상향식 히프 구성 결과와 하향식 히프 구성 결과가 다를 수 있음