[C언어] 기초 자료구조 - 큐(Queue)

c언어

---

1. 큐(Queue)란?

• 큐는 선입선출(FIFO, First In First Out) 방식으로 동작하는 자료구조.
• 특징
  1. 데이터는 한쪽(뒤, rear)에서 삽입되고, 다른쪽(앞, Front)에서 제거됩니다.
• 활용 사례
  • 프로세스 스케줄링
  • 데이터 스트림 처리
  • BFS(너비 우선 탐색)구현
• 큐의 동작 원리, 주요 연산
  • Enqueue: 데이터를 큐의 뒤에 삽입.
  • Dequeue: 데이터를 큐의 앞에서 제거.
  • Peek(Front): 큐의 가장 앞 요소를 반환하지만 제거하지 않음.
  • IsEmpty: 큐가 비어 있는지 확인.
  • IsFull: 큐가 가득 찼는지 확인(배열 기반 큐에서)

---

2. 배열 기반 큐 구현

• 큐를 비열로 구현하면 고정된 크기의 정적 큐를 만들 수 있음.

#include <stdio.h>
#define MAX 5 // 큐의 최대 크기

int queue[MAX];
int front = 0, rear = -1, count = 0;

// Enqueue 함수
void enqueue(int data) {
    if (count == MAX) {
        printf("큐 오버플로우! 더 이상 삽입할 수 없습니다.\n");
        return;
    }
    rear = (rear + 1) % MAX;
    queue[rear] = data;
    count++;
}

// Dequeue 함수
int dequeue() {
    if (count == 0) {
        printf("큐 언더플로우! 큐가 비어 있습니다.\n");
        return -1;
    }
    int data = queue[front];
    front = (front + 1) % MAX;
    count--;
    return data;
}

// Peek 함수
int peek() {
    if (count == 0) {
        printf("큐가 비어 있습니다.\n");
        return -1;
    }
    return queue[front];
}

// IsEmpty 함수
int isEmpty() {
    return count == 0;
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("Peek: %d\n", peek()); // 10 출력
    printf("Dequeue: %d\n", dequeue()); // 10 제거
    printf("Dequeue: %d\n", dequeue()); // 20 제거
    printf("큐가 비어 있나요? %s\n", isEmpty() ? "예" : "아니오");
    return 0;
}

---

3. 연결 리스트 기반 큐 구현

연결 리스트를 사용하면 크기 제한 없는 동적 큐를 구현할 수 있음.

#include <stdio.h>
#include <stdlib.h>

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *front = NULL;
Node *rear = NULL;

// Enqueue 함수
void enqueue(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    if (rear == NULL) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
}

// Dequeue 함수
int dequeue() {
    if (front == NULL) {
        printf("큐 언더플로우! 큐가 비어 있습니다.\n");
        return -1;
    }
    int data = front->data;
    Node *temp = front;
    front = front->next;
    if (front == NULL) {
        rear = NULL;
    }
    free(temp);
    return data;
}

// Peek 함수
int peek() {
    if (front == NULL) {
        printf("큐가 비어 있습니다.\n");
        return -1;
    }
    return front->data;
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("Peek: %d\n", peek()); // 10 출력
    printf("Dequeue: %d\n", dequeue()); // 10 제거
    printf("Dequeue: %d\n", dequeue()); // 20 제거
    printf("큐가 비어 있나요? %s\n", front == NULL ? "예" : "아니오");
    return 0;
}

 

---

4. 우선 순위 큐(Priority Queue)

우선순위 큐는 각 데이터에 우선순위가 부여되며, 우선순위가 높은 데이터가 먼저 처리됨

• 배열 기반 우선순위 큐

#include <stdio.h>
#define MAX 5

typedef struct {
    int data;
    int priority;
} Element;

Element queue[MAX];
int size = 0;

// Enqueue 함수
void enqueue(int data, int priority) {
    if (size == MAX) {
        printf("큐 오버플로우! 더 이상 삽입할 수 없습니다.\n");
        return;
    }
    queue[size].data = data;
    queue[size].priority = priority;
    size++;
}

// Dequeue 함수
int dequeue() {
    if (size == 0) {
        printf("큐 언더플로우! 큐가 비어 있습니다.\n");
        return -1;
    }
    // 가장 높은 우선순위 요소 찾기
    int highestPriorityIndex = 0;
    for (int i = 1; i < size; i++) {
        if (queue[i].priority > queue[highestPriorityIndex].priority) {
            highestPriorityIndex = i;
        }
    }
    int data = queue[highestPriorityIndex].data;
    // 요소 제거 후 배열 정리
    for (int i = highestPriorityIndex; i < size - 1; i++) {
        queue[i] = queue[i + 1];
    }
    size--;
    return data;
}

int main() {
    enqueue(10, 1); // 데이터: 10, 우선순위: 1
    enqueue(20, 3); // 데이터: 20, 우선순위: 3
    enqueue(30, 2); // 데이터: 30, 우선순위: 2

    printf("Dequeue: %d\n", dequeue()); // 20 (우선순위 3)
    printf("Dequeue: %d\n", dequeue()); // 30 (우선순위 2)
    printf("Dequeue: %d\n", dequeue()); // 10 (우선순위 1)
    return 0;
}

• 힙(Heap) 기반 우선순위 큐
  • 힙(Heap)을 사용하면 우선순위 큐를 더 효율적으로 구현할 수 있음.
  • 힙은 우선순위 큐 구현에서 효율적인 자료구조.
  • 삽입과 삭제의 시간 복잡도가 O(log N).
  • 아래 포스트 참고

2025.01.21 - [개발/C] - [C언어] 기초 자료구조 - 힙(Heap)

---

5. 큐 활용 예제

• BFS(너비 우선 탐색)

#include <stdio.h>
#define MAX 100

int queue[MAX];
int front = 0, rear = -1;

void enqueue(int data) {
    queue[++rear] = data;
}

int dequeue() {
    return queue[front++];
}

int isEmpty() {
    return front > rear;
}

void bfs(int graph[][4], int start, int visited[], int n) {
    enqueue(start);
    visited[start] = 1;
    while (!isEmpty()) {
        int node = dequeue();
        printf("%d ", node);
        for (int i = 0; i < n; i++) {
            if (graph[node][i] == 1 && !visited[i]) {
                enqueue(i);
                visited[i] = 1;
            }
        }
    }
}

int main() {
    int graph[4][4] = {
        {0, 1, 1, 0},
        {1, 0, 1, 1},
        {1, 1, 0, 1},
        {0, 1, 1, 0}};
    int visited[4] = {0};
    printf("BFS 탐색 순서: ");
    bfs(graph, 0, visited, 4);
    return 0;
}

---

6. 큐의 한계와 주의점

• 배열 기반 큐
  • 고정 크기로 인해 메모리 낭비 또는 오버플로우 발생.
  • 원형 큐(Circular Queue)를 사용하면 이를 해결 가능
• 연결 리스트 기반 큐
  • 동적 메모리를 사용하므로 해제 필요
• 우선 순위 큐
  • 배열 기반 구현은 비효율적일 수 있으므로, 힙(Heap) 사용 권장