Queue?

First In First Out(FIFO) 방식으로 데이터를 삽입/삭제하는 자료구조이다.

Queue를 이해할 때는 가장 대표적으로 줄 서기를 떠올릴 수 있다. 우리는 어떤 대기 줄에서 첫 번째로 온 사람이 가장 먼저 들어간다. 나중에 온 사람은 그 이후에 들어갈 수 있다.

간단하게 말하자면, 뒤로 추가되고 앞에서 삭제된다.

이게 바로 자료구조 Queue이다.

구조체 정의

Linked List 구조체의 자료에서 Queue를 구현한다고 가정한다.

typedef struct _linkedlist
{
	int size;
	ListNode *head;
} LinkedList;

typedef struct _queue
{
	LinkedList ll;
} Queue;

삽입 enqueue 함수

5개의 값을 Queue에 추가하는 과정은 다음과 같다. 기존 Queue의 tail 노드 뒤에 새로운 노드를 추가한다.

1. size-1 의 인덱스를 가진 tail 노드를 찾는다.
2. tail 노드의 next 포인터가 새로운 노드를 가리키게 한다.

void enqueue(Queue *q, int item)
{
    // 새 노드 생성
    ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
    newNode->item = item;
    newNode->next = NULL;

    // 큐가 비어 있으면 head에 바로 추가
    if (q->ll.head == NULL)
    {
        q->ll.head = newNode;
    }
    else
    {
        // tail 노드를 찾아서 newNode를 붙이기
        ListNode *cur = q->ll.head;
        while (cur->next != NULL)
            cur = cur->next;
        cur->next = newNode;
    }

    q->ll.size++;
}

삭제 dequeue 함수

Queue 자료구조에서 삭제 연산은 앞에서 이루어진다. 먼저 추가된 원소가 먼저 삭제 되어야 하기 때문이다.

따라서 head 노드를 삭제해주면 된다.

1. Queue의 head 노드를 가리키는 포인터를 head→next 노드로 바꿔준다.
2. 기존 head 노드를 할당 해제(free) 해준다.

int dequeue(Queue *q)
{
    if (q->ll.head == NULL)
        return -1; // 큐가 비어있음

    ListNode *temp = q->ll.head;
    int item = temp->item;

    // head를 다음 노드로 옮기고 원래 head는 free
    q->ll.head = q->ll.head->next;
    free(temp);
    q->ll.size--;

    return item;
}