Queue - 큐 코드 구현

Queue 코드 구현

문제 .

4명의 사람이 각자 물건들을 사들고 마트 계산 줄에 서있습니다.

차례대로 4명이 카트에 물건을 올려두면, 점원이 계산을 해주게 됩니다.

이 때 어떤 자료구조를 써야하며, 어떻게 구현해야 하나요?

목표 결과물:

소스 파일 다운로드:

queue.c

queue.h

구현시 주의사항

1. makeNode에서, 현재 node는 item이 포인터로 지정이 되어 있기 때문에 동적 할당을 통해 만들어주어야 합니다.

2. enqueue할때에는, Q의 count가 0일 경우엔 집어넣는 노드를 front이면서 rear인 상태로 만들어주어야 합니다.

3. dequeue가 특히 주의하여야 할 점이 많은데, 들어가 있는 node의 개수가 몇개인지에 따라서 조건문을 분기시켜야 합니다.

또한 rear에서 node를 빼내야 하므로, rear의 바로 전 node를 rear로 만들어주고, 그 노드의 next는 NULL로 바꿔주어야 합니다.

그림으로 그리면서 생각해보면 답이 나옵니다!

typedef struct _product {
    int price;
    int count;
    char name[20];
}Product, *pProduct;
 
typedef struct _node {
    pProduct item;
    struct _node *next;
}Node, *pNode;
 
typedef struct _queue {
    int count;  // 노드의 갯수를 저장한다.
    pNode front; // 첫번째 노드를 가리킨다.
    pNode rear; // 첫번째 노드를 가리킨다.
}Queue, *pQueue;
 
 
 
pQueue makeQueue() {
    pQueue tmp = (pQueue)malloc(sizeof(Queue));
    tmp->front = NULL;
    tmp->rear = NULL;
    tmp->count = 0;
    return tmp;
}
pNode makeNode(char *name, int price, int count) {
    pNode tmp = (pNode)malloc(sizeof(Node));
    tmp->item = (pProduct)malloc(sizeof(Product));
    tmp->item->count = count;
    tmp->item->price = price;
    strcpy(tmp->item->name, name);
    tmp->next = NULL;
    return tmp;
}
 
void enqueue(pQueue Q, pNode N) {
    N->next = Q->front;
    Q->front = N;
    if(Q->count==0)
        Q->rear = N;
    Q->count++;
}
 
pNode dequeue(pQueue Q) {
    pNode tmp = Q->front;
    pNode temp;
    if (Q->count == 0){
        return NULL;
    }else if (Q->count == 1) {
        Q->front = NULL;
        Q->rear = NULL;
        Q->count--;
        return tmp;
    }
    else {
        while (1) {
            if (tmp->next == Q->rear)
                break;
            tmp = tmp->next;
        }
        Q->count--;
        temp = tmp->next;
        Q->rear = tmp;
        tmp->next = NULL;
        return temp;
    }
}
 
void dequeueAll(pQueue Q) {
    int count = Q->count;
    pNode tmp;
    for (size_t i = 0; i < count; i++)
    {
        tmp = dequeue(Q);
        if(tmp!=NULL)
            printf("계산하실 금액은 : %s %d개, %d원입니다. \n", tmp->item->name, tmp->item->count, tmp->item->price);
    }
    printf("\n");
}
 

---