[자료구조] 큐(Queue)의 개념과 구현(C) & 용도

큐 (Queue)란?

• 스택과 마찬가지로 자료의 삽입과 삭제에 대한 규칙이 있는 자료구조 중 하나
• 가장 먼저 자료구조에 삽입(enqueue)된 데이터가 제일 처음에 삭제 (dequeue)됨
• 이를 선입선출 (First In First Out)이라고 함
• 스택과는 삭제 방향이 다르다
  
• 큐 역시 임의 접근은 안 됨
  • 언제나 제일 처음에 있는 자료만 제거 가능
  • 중간 자료로 임의 접근 안됨
    
    

큐의 구현

큐의 비효율적인 구현

• 그냥 배열을 사용하면 큐를 구현할 수는 있다.

• enqueue 하면 그냥 제일 뒤에 추가 O(1)

• 내부적으로는 insert_at(num_count, 60);
  

• dequeue하면 그냥 제일 앞에서 삭제 O(N)

  • dequeue();
  • 내부적으로는 remove_at(0)
  • 뒤에 있는 요소들을 모두 한 칸씩 땡겨야 한다
    

• 하지만 큐의 삭제도 O(1)으로 구현할 수 있다.

  • 내부적으로는 배열을 사용하되 원형 버퍼 (ring buffer)개념 이용
    
    

큐의 삽입

큐의 삽입

• 보통 enqueue라고 표현
  • 줄 제일 뒤에 세운다는 의미
• 시간 복잡도는 O(1)이다

큐의 삽입 예

enum { MAX_NUMS = 8 };
int s_nums[MAX_NUMS];

size_t s_front = 0;
size_t s_back = 0;
size_t s_num_count = 0;

void enqueue(int n)
{
    assert(s_num_count < MAX_NUMS)

    s_nums[s_back] = n;

    s_back = (s_back + 1) % MAX_NUMS;

    ++s_num_count;
}

int main(void)
{
    enqueue(10); // { 10 }, s_back = 1, s_num_count = 1
    enqueue(20); // { 10, 20 }, s_back = 2, s_num_count = 2
    enqueue(30);
    enqueue(40);
    enqueue(50);
    enqueue(60);
    enqueue(70); // { 10, 20, ... , 70 }, s_back = 7, s_num_count = 7
    enqueue(80); // { 10, 20, ... , 70, 80 }, s_back = 8, s_num_count = 8

    return 0;
}

큐의 삭제

큐의 삭제

• dequeue 라고 표현
  • 앞에서 하나 빼온다는 의미
• 시간복잡도는 삽입과 마찬가지로 O(1)이다

큐의 삭제 예

int is_empty(void)
{
    return (s_num_count == 0);
}

int dequeue(void)
{
    int ret;

    assert(is_empty() == FALSE);

    ret = s_nums[s_front];

    --s_num_count;
    s_front = (s_front + 1) % MAX_NUMS;

    return ret;
}

/* 메인 함수 */

/* s_nums = { 10, 20, 30, 40, 50 }*/
int item = dequeue(); /* item: 10 */

큐의 검색

• 제일 처음부터 찾을 때 가지 뒤져야 하므로 스택과 마찬가지로 시간복잡도는 O(N)이다
  • 제거에 O(N) + 원상 복구에 O(N) = O(2N) = O(N)
• 스택과 마찬가지로 보통 enqueue()와 dequeue()만 허용하므로 임의의 요소에 접근할 방법이 없다
  
  

큐의 용도

• 현실 세계에서 대기 줄이 필요한 경우 모두 적용 가능
• 데이터 유입 속도가 데이터 소모 속도보다 빠른 겨우
• 데이터 제공자의 수가 데이터 소비자의 수와 다른 경우
  • 예: 은행 창구는 여럿인데 줄은 한 줄 로만 설 때
  • 멀티 쓰레딩에서도 이런 일을 함
• 입출력 스트림 버퍼링도 같은 개념
  • 버퍼에 쌓아두고 앞에서 부터 차례대로 접근
    
    

References

• POCU 아카데미: C 언매니지드 프로그래밍