본문 바로가기
알고리즘 문제풀이

[알고리즘] 큐(Queue)를 이용한 대기번호

by 마스터누누 2017. 4. 18.
728x90
반응형

큐(Queue)를 이용한 대기번호




자료구조를 배우면 가장 먼저 등장하는 스택, 큐, 링크드리스트.

이 중 큐를 이용하여 대기번호 알고리즘을 작성해보겠다.


큐는 선입선출(First In First Out, FIFO)의 구조를 가지고 있으며

OS에도 호출과 관련하여 스택과 같이 빈번하게 사용된다.


은행에서 대기번호를 받을 때 먼저 대기표를 받고 자신의 차례를 기다린다.

이후 순서가 돌아오면 번호표대로 업무를 보기 시작한다.

이와같은 구조는 선입선출의 큐 구조와 동일한 모습을 보인다.

따라서 대기번호의 경우 큐로 구현이 가능하다.




1. 배열로 만든 큐

(Add-Enqueue)

 

1
2
3
4
5
6
7
8
9
10
11
12
13
int add(int num){
    if(tail==Q_Capacity){
        printf("Queue is Full!");                                                                          
        return 0;
    }
    
    Q_size++;
    tail++;
    Q[tail] = num;
    
    return 0;
}
 
cs
 

큐는 제일 첫번째 부분이 Head, 마지막 부분의 tail이 되며, 

각각의 인덱스를 통해 구분을 한다.

위의 소스는 큐에 데이터를 삽입하는 add함수이다.

add함수를 실행시킬 경우 먼저 큐가 꽉차있는지 확인하게 된다.

문제가 발생 할 경우 큐가 꽉 차있다는 메세지를 출력하며, 

없을 경우 더하기 연산을 진행한다.


큐에 데이터가 들어가는 연산은 다음과 같다.

1. 큐의 사용 사이즈를 늘린다.

2. 큐의 tail 인덱스를 다음 번호로 늘린다.

3. tail에 해당하는 배열에 데이터를 넣는다.





(delete-Dequeue)

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int del(){
    int del_data;
    
    if(tail<head){
        printf("There is no Data!");                                                                       
        return 0;
    }
    
    del_data = Q[head];
    head++;
    Q_size—;
    
    return del_data;
}
 
cs


반대로 큐의 데이터를 삭제하는 연산이다.

삽입과 마찬가지로 큐 내부에 삭제할 데이터가 있는지 확인한다.

문제가 발생 할 경우 큐가 비어있다는 메세지를 출력하고, 

있을경우 빼는 연산을 진행한다.


큐에 데이터를 삭제하는 연산은 다음과 같다.

1. 삭제되는 데이터를 임시 변수에 저장한다.

2. head 인덱스를 다음 번호로 늘린다.

3. 큐의 사용 사이즈를 줄인다.


삭제 되는 데이터를 임시 변수에 저장하는 이유는 반환한후 출력하기 위함이다.

해당 과정이 필요 없는 경우는 없애도 큰 무리는 없지만 

삭제한 데이터값 확인이 불가하다






(전체 코드)

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdio.h>
 
#define Q_Capacity 10
 
int add(int num);
int del();
 
int Q[Q_Capacity] = {};
int head = 0;
int tail = -1;
int Q_size = 0;
 
int main(int argc, const char * argv[]) {
    
    int i;
    
    add(1);
    add(14);
    add(16);
    
    for(i=head; i<=tail; i++){
        printf("%d ", Q[i]);
    }
       
    printf("\n%d\n",del());
  
    for(i=head; i<=tail; i++){
        printf("%d ", Q[i]);
    }
    
    
    return 0;
}
 
 
int add(int num){
    if(tail==Q_Capacity-1){
        printf("Queue is Full!");                                  
        return 0;
    }
    
    Q_size++;
    tail++;
    Q[tail] = num;
    
    return 0;
}
 
int del(){
    int del_data;
    
    if(tail<head){
        printf("There is no Data!");
        return 0;
    }
    
    del_data = Q[head];
    head++;
    Q_size--;
    
    return del_data;
}
 
cs


예제 코드의 경우 전역변수로 설정하였지만, 

전역변수는 가급적 사용을 줄이는 것이 좋다.

따라서 실제로 프로젝트 등에서 큐를 구현할 경우 

전역이 아닌 형태로 데이터를 저장하는것을 권장한다.



반응형

댓글