[자료구조] 04. Queue 배열 구조 예제 (C언어)

Queue는 Embedded에서도 많이 쓰는 구조이다.

CAN의 버퍼관리나, 진단 List 관리등에서 많이 사용될수 있는 기법이다.

따라서 예제 하나를 잘 정리해 놓으면 좋을 것 같다.

 

Queue 예제 1

/*-----------------------Include-----------------------*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <conio.h>

/*-----------------------Define-----------------------*/
#define TSIZE 45
#define MAXSIZE    4

#define TRUE 1
#define FALSE 0
/*-----------------------Typedef-----------------------*/
typedef unsigned int uint32_t;
typedef int int32_t;
typedef unsigned char uint8_t;

struct element
{
    char name[TSIZE];
}element;

typedef struct element Item;

typedef struct queue
{
    int front;
    int rear;
    int n_items;
    Item items[MAXSIZE];
}Queue;


/*---------------------- Static Function Header-----------------------*/


/*-----------------------Variable-----------------------*/


/*-----------------------Function-----------------------*/
void TraverseQueue(Queue* pq, void (*func)(Item item))
{
    int i;
    for(i= pq->front; i !=pq->rear; i = (i + 1) % MAXSIZE)
        (*func)(pq->items[(i+1)%MAXSIZE]);
}

void InitializeQueue(Queue* pq)
{
    pq->front = 0;
    pq->rear = 0;
    pq->n_items = 0;
}

uint8_t QueueIsFull(const Queue* pq)
{
    return (pq->rear + 1) % MAXSIZE == pq->front;
}

uint8_t QueueIsEmpty(const Queue* pq)
{
    return pq->front == pq->rear;
}

int QueueItemCount(const Queue* pq)
{
    return pq->n_items;
}

uint8_t EnQueue(Item item, Queue* pq)
{
    if(QueueIsFull(pq))
    {
        printf("Queue is fill. Cannot enqueue.\n");
        return FALSE;
    }

    pq->rear = (pq->rear + 1) % MAXSIZE;
    pq->items[pq->rear] = item;
    pq->n_items++;

    return TRUE;
}

uint8_t DeQueue(Item* pitem, Queue* pq)
{
    if(QueueIsEmpty(pq))
    {
        printf("Queue is empty. Cannot dequeue.\n");
        return FALSE;
    }

    pq->front = (pq->front +1)%MAXSIZE;
    *pitem = pq->items[pq->front];
    pq->n_items--;

    return TRUE;
}

Item get_item(const char* name)
{
    Item new_item;
    strcpy(new_item.name, name);
    return new_item;
}

void print_item(Item item)
{
    printf("%s ", item.name);
}

void print_queue(Queue* pq)
{
    printf("Front: %d, Rear: %d, Size: %d\n", pq->front, pq->rear, pq->n_items);

    printf("Queue : ");
    if(QueueIsEmpty(pq))
        printf("Empty");
    else
        TraverseQueue(pq, &print_item);
    printf("\n");
}

int main(void)
{
    Queue queue;
    Item temp;
    int i;

    InitializeQueue(&queue);

    EnQueue(get_item("Jack"),&queue);
    print_queue(&queue);

    EnQueue(get_item("Henry"),&queue);
    print_queue(&queue);

    EnQueue(get_item("Stan"),&queue);
    print_queue(&queue);

    EnQueue(get_item("Scott"),&queue);
    print_queue(&queue);

    if(DeQueue(&temp, &queue))
        printf("Item from Queue: %s\n", temp.name);
    print_queue(&queue);

    if(DeQueue(&temp, &queue))
        printf("Item from Queue: %s\n", temp.name);
    print_queue(&queue);

    if(DeQueue(&temp, &queue))
        printf("Item from Queue: %s\n", temp.name);
    print_queue(&queue);

    if(DeQueue(&temp, &queue))
        printf("Item from Queue: %s\n", temp.name);
    print_queue(&queue);

    printf("----- Circulation Test -------\n");

    InitializeQueue(&queue);

    for(i=0;i<10;i++)
    {
        EnQueue(get_item("Hello"),&queue);
        print_queue(&queue);

        if(DeQueue(&temp, &queue))
            printf("Item from queue : %s\n", temp.name);
        print_queue(&queue);
    }
    return 0;
}

실행결과는 아래와 같다.

Queue 예제 2

/*----------------Include--------------------*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/*----------------Define--------------------*/
#define TSIZE 100
#define MAX_QSIZE    4

#define TRUE    1
#define FALSE 0
/*----------------Typedef--------------------*/
typedef unsigned int uint32_t;
typedef int int32_t;
typedef unsigned char uint8_t;

typedef struct element
{
    char name[TSIZE];
}Element;

typedef struct queue
{
    int front;
    int rear;
    int n_times;
    Element items[MAX_QSIZE];
}Queue;

/*----------------Variable--------------------*/


/*----------------Function--------------------*/
void InitializeQueue(Queue* pQueue)
{
    pQueue->front = 0;
    pQueue->rear = 0;
    pQueue->n_times = 0;
}


uint8_t QueueIsFull(Queue* pQueue)
{
    if(((pQueue->rear + 1) % MAX_QSIZE) == pQueue->front)
    {
        printf("Queue is Full!\n");
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

uint8_t QueueIsEmpty(Queue* pQueue)
{
    if(pQueue->front == pQueue->rear)
    {
        printf("Queue is Empty!\n");
        return TRUE;
    }
    else
    {
        return FALSE;
    }
}

uint8_t EnQueue(Queue* pQueue, Element item)
{
    if(QueueIsFull(pQueue) == TRUE)
    {
        return FALSE;
    }
    pQueue->rear = (pQueue->rear + 1) % MAX_QSIZE; 
    pQueue->items[pQueue->rear] = item;
    pQueue->n_times++;
    return TRUE;
}

uint8_t DeQueue(Queue* pQueue, Element* pItem)
{
    if(QueueIsEmpty(pQueue)==TRUE)
    {
        return FALSE;
    }

    pQueue->front = (pQueue->front + 1)%MAX_QSIZE;
    *pItem = pQueue->items[pQueue->front];
    pQueue->n_times--;
    return TRUE;
}

void print_Item(Element Item)
{
    printf("%s ", Item.name);
}

void print_queue(Queue* pQueue)
{
    int i;

    if(QueueIsEmpty(pQueue) == TRUE)
    {
        printf("Queue Empty!\n");
    }
    else
    {
        printf("front: %d, rear: %d, n_items: %d\n",pQueue->front, pQueue->rear, pQueue->n_times);
    
        for(i=pQueue->front; i != pQueue->rear; i = (i +1) % MAX_QSIZE)
        {
            print_Item(pQueue->items[(i+1)%MAX_QSIZE]);
        }
        printf("\n");
    }
}

Element get_element(char* name)
{
    Element temp;
    strcpy(temp.name,name);
    return temp;
}

int main(void)
{
    Queue my_queue;
    Element temp;
    int i;

    InitializeQueue(&my_queue);
    (void)EnQueue(&my_queue, get_element("Tom"));
    print_queue(&my_queue);

    (void)EnQueue(&my_queue, get_element("Jack"));
    print_queue(&my_queue);

    (void)EnQueue(&my_queue, get_element("Kely"));
    print_queue(&my_queue);

    (void)EnQueue(&my_queue, get_element("Susan"));
    print_queue(&my_queue);

    DeQueue(&my_queue, &temp);
    printf("DeQueue Name : %s\n",temp.name);
    print_queue(&my_queue);

    (void)EnQueue(&my_queue, get_element("Susan"));
    print_queue(&my_queue);

    for(i=0;i<10;i++)
    {
        (void)EnQueue(&my_queue, get_element("Susan"));
        print_queue(&my_queue);

        DeQueue(&my_queue, &temp);
        printf("DeQueue Name : %s\n",temp.name);
        print_queue(&my_queue);
    }
    return 0;
}

실행 결과는 아래와 같습니다.