큐(Queue)

개념

• 큐 역시 리스트와 같은 선형 자료구조이다.
• 큐는 스택과 달리 FIFO(First In First Out) 구조이다.

• 스택의 삽입은 push, 삭제는 pop이었지만, 큐에서는 삽입은 enqueue, 삭제는 dequeue이다.

배열로 구현 - 순환 큐(Circular queue)

• 배열로 큐를 구현하는 경우, 순환 큐로 구현해야 한다.
• 그 이유는 순환 큐에서 데이터를 하나 빼면(dequeue) 이후의 모든 요소를 한 칸씩 움직여야 한다.

• 이는 매우 비효율적이기 때문에 굳이 한 칸씩 움직일 필요 없이 시작점과 끝점만 움직이도록 했고, 이것이 바로 순환 큐이다.

• 실제 코드 상으로는, 시작점과 끝점은 인덱스 값으로 표현되며 이는 데이터가 삽입될 때마다 +1이 될 뿐만 아니라 배열의 크기만큼 나누면 된다.
• 하지만 여기에도 문제점이 있는데, 시작점과 끝점이 완전히 같은 경우이다.

1. 공백 상태일 때 시작점과 끝점이 동일하다.
2. 포화 상태일 때 시작점과 끝점이 동일하다.

• 때문에 시작점과 끝점이 동일한 경우에는 포화 상태인지 공백 상태인지 파악할 수 없다.
• 이를 해결하기 위해 배열의 맨 끝에 더미 노드를 추가해서 포화 상태일 때에는 끝점의 위치가 더미 노드에 위치하도록 한다.

#define SIZE 1024
#define DUMMY SIZE
#define NEXT(index) ((index) + 1) % SIZE

typedef struct s_node {
    int data;
} t_node;

typedef struct {
    t_node* array;
    size_t entry;
    size_t end;
} t_queue;

void init_queue(t_queue* const queue) {
    queue->array = (t_node*)malloc(sizeof(t_node) * (SIZE + 1);
    if (!queue->array)
        exit(1);
    queue->entry = 0;
    queue->end = queue->entry;
}

void enqueue(t_queue* const queue, const t_node node) {
    if (end != DUMMY) {
        queue->end = NEXT(queue->end);
        queue->array[queue->end] = node;
    }
}

void dequeue(t_queue* const queue) {
    if (end != DUMMY) {
        queue->entry = NEXT(queue->entry);
    }
}

리스트로 구현

• 배열과 달리 연결 리스트로 큐를 구현하면 비교적 쉽다.
• 배열에서 나왔던 문제점 - 크기에 대한 제한과 순환 큐에서의 더미 노드 문제가 없다.

void enqueue(t_queue** const queue, t_queue* const node) {
    insert_back(queue, node);
}

void dequeue(t_queue** const queue) {
    remove_front(queue);
}

참고한 자료

• 이것이 자료구조 + 알고리즘이다 with C