자료구조 - 큐

자료구조 - 큐

이전에 공부했던 스택은 Top에서 삽입, 삭제가 발생하였지만 지금 구현할 큐는 삽입, 삭제가 각각 front, rear에서 발생합니다.

구조는 FIFO(First In - First Out) front에서 데이터가 삭제되고 rear에서 데이터가 추가됩니다.

- 추가 => enqueue

- 삭제 => dequeue

구현의 편의상 이중링크드 리스트로 구현하였다. 전체적인 구조는 비슷하고 노드를 잘 연결만 시켜주면 그리 어렵지 않게 구현 가능합니다.

---

이중링크드 리스트를 이용한 큐(queue) 구현

1. 구조체 구현

typedef struct _node{

    int value;

    struct _node *next;

    struct _node *prev;

}node, *nptr;

typedef struct _queue{

    nptr front;

    nptr rear;

    int count;

}queue;

2. init 구현

queue *init_queue()

{

    queue *qptr = (queue*)malloc(sizeof(queue));

    qptr->front = NULL;

    qptr->rear = NULL;

    qptr->count = 0;

    return qptr;

}

3. edqueue 구현

void enqueue(queue *qptr, int _value)

{

    node *new_node = (node*)malloc(sizeof(node));

    new_node->value = _value;

    new_node->next = NULL;

    new_node->prev = NULL;

    if(qptr->count == 0)

    {

       qptr->front = new_node;

       qptr->rear = new_node;

    }

    else

    {

        qptr->rear->next = new_node;

        new_node->prev = qptr->rear;

        qptr->rear = new_node;

    }

    qptr->count++;

}

4. dequeue 구현

void dequeue(queue *qptr)

{

    nptr remove;

    if(qptr->count == 0)

    {

        printf("Error : out of range\n");

    }

    else if(qptr->count == 1)

    {

        remove = qptr->rear;

        qptr->rear = NULL;

        qptr->front = NULL;

        qptr->count--;

        free(remove);

    }

    else

    {

        remove = qptr->front;

        remove->next->prev = NULL;

        qptr->front = remove->next;

        free(remove);

        qptr->count--;

    }

}

---

Result

=> 결과를 보면 입력은 마지막에 들어가고 출력은 처음에 입력된 값이 나오는 것을 알수 있다.

---