[알고리즘] 큐(Queue) 개념/용도/삽입/삭제/검색(C언어)

 

 큐(Queue) 개념/용도,  C언어로 삽입/삭제/검색 구현하기, 예제

 

 

스택은 출입구가 하나였다면 큐는 2개인 자료구조입니다. 

스택과 마찬가지로 자료의 삽입과 삭제에 대한 규칙이 있는 자료구조 중 하나입니다. 

선입선출(first in first out)로 먼저 들어간(enqueue) 데이터가 먼저 삭제(dequeue)됩니다. 

영어로 Queue도 한 줄로 서있는 상태를 의미하니 아래 그림을 기억하면 좋을 것 같습니다.  

 

이미지 출쳐:https://michaelscodingspot.com/c-job-queues/

 

데이터가 10, 20, 30 순으로 삽입되었으면 

삭제도 10, 20, 30 순입니다. 즉, 삽입 순서와 삭제순서가 같죠.

언제나 가장 처음에 있는 자료만 제거 가능하고, 중간 자료에 임의 접근 안 됩니다. 

 

 

 

---

■ 큐의 삽입

en                     +  queue                   = enqueue 

1. ~속에 넣다          1 대기줄                    큐에 넣다

2. ~이 되게 하다.    2 (컴퓨터) 큐

                             3 줄 서서 기다리다

 

시간 복잡도 O(1)

enum { MAX_NUMS = 8};

int s_nums[MAX_NUMS]; // 8개 요소를 넣을 수 있는 배열 생성
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); //8자리 이상 넣지 않도록 검사
    s_nums[s_back] = n;
    s_back = (s_back + 1) % MAX_NUMS; // 다음 자리 구하기 위해 +1하고 되돌아 오기 위한 나머지 연산
    ++s_num_count;
}
int main (void){
    enqueue(10);
    enqueue(20);
    enqueue(30);
    enqueue(40);
    enqueue(50);
    enqueue(60);
    enqueue(70);
    enqueue(80);

    return 0;
}

 

---

 

 

■ 큐의 삭제

de                     +  queue                   = dequeue 

1. ~의 반대          1 대기줄                        큐에서 분리/제거하다

2. 분리, 제거       2 (컴퓨터) 큐

                          3 줄 서서 기다리다

 

시간 복잡도 O(1)

int s_nums[MAX_NUMS]; // 8개 요소를 넣을 수 있는 배열 생성
size_t s_front = 0; // 시작, 줄 앞에서 빼야 되는 위치
size_t s_back = 0;  // 끝, 줄 뒤에 세워야 하는 위치
size_t s_num_count = 0; // 데이터를 넣을 자리(인덱스)

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;
    // 한 바퀴 돌고 올꺼라 8 나눈 나머지 연산함 
    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(2n)이지만 빅오표기법은 '정도'를 나타내기 때문에 O(n)이라고 합니다.

 

시간복잡도 O(n)

 

 

---

■ 큐의 용도

- 현실 세계에서 대기줄이 필요한 경우

- 데이터 유입 속도가 데이터 소모 속도보다 빠른 경우

- 데이터 제공자의 수가 데이터를 소비자의 수와 다른 경우

예) 영화 매표창구는 여러 개인데 대기하려면 한 줄로 서야할 때

 

 

 

------------------------------

알고리즘 개념 모아보기 

------------------------------