큐의 활용

출처 : 윤성우의 열혈 자료구조

 

햄버거 가게에서 손님대기를 위한 큐를 만든다.

1시간 동안 고객이 15초당 1명씩 주문을 한다. 분당 4명*60분 = 240명

버거를 만드는 시간은 치즈버거 12초, 불고기버거15초, 더블버거 24초이다.

 

큐 넉넉하지 않아도 되고, 꽉 차는 상황이 발생해야 한다.

 

큐의 크기 30 : 안정적일 확률 50%

큐의 크기 50 : 안정적일 확률 70%

큐의 크기 100 : 안정적일 확률 90%

큐의 크기 200 : 안정적일 확률100%

 

안정적이라는 의미는 10회 시뮬레이션 결과 대기 고객 전부를 수용하는 것이 불가능한 상황이 몇회 발생했는가 이다.

50%는 10회중 5회 발생 했다는 의미이다.

 

#include<stdio.h>
#include<time.h>
#include<stdlib.h>

#define CUS_COME_TERM   15

#define CHE 0
#define BUL 1
#define DUB 2

#define CHE_T 12
#define BUL_T 15
#define DUB_T 24

typedef int Data;

typedef struct _node{
    Data data;
    struct _node * next;
}Node;

typedef struct queue{
    Node * front;
    Node * rear;
}Que;

void QInit(Que * pq){
    pq->front = NULL;
    pq->rear = NULL;
}

int QIsEmpty(Que * pq){
    if(pq->front == NULL)
        return 1;
    else
        return 0;
}

void Enqueue(Que * pq,Data data){
    Node * newNode = (Node*)malloc(sizeof(Node));
    newNode->next = NULL;
    newNode->data = data;

    if(QIsEmpty(pq)){
        pq->front = newNode;
        pq->rear = newNode;
    }
    
    else{
        pq->rear->next = newNode;
        pq->rear = newNode;
    }
}

Data Dequeue(Que * pq){
        if(QIsEmpty(pq)){
            printf("Queue memory error");
            exit(0);
        }

        Data rdata=pq->front->data;
        Node * delNode = pq->front;
        
        pq->front = pq->front->next;
        
        free(delNode);
        
        return rdata;
}

int main(){
    int makeproc=0;
    int cheord=0,bulord=0,dubord=0;
    int sec;

    Que que;

    QInit(&que);
    srand(time(NULL));

    //for문 1번당 1초의 시간
    for(sec =0;sec<3600;sec++){
        if(sec % CUS_COME_TERM == 0){
            switch(rand()%3){
                case CHE:
                    Enqueue(&que,CHE_T);
                    cheord+=1;
                    break;
                
                case BUL:
                    Enqueue(&que,BUL_T);
                    bulord+=1;
                    break;
                
                case DUB:
                    Enqueue(&que,DUB_T);
                    dubord+=1;
                    break;
            }
        }

    }   
    printf("cheese :%d\n",cheord);
    printf("bul :%d\n",bulord);
    printf("double :%d\n",dubord);
}