큐(프로그래밍) 편집하기

== 개요 ==
큐(Queue)는 컴퓨터 과학에서 널리 사용되는 추상 자료형으로, 데이터를 순서대로 저장하고 관리하는 자료 구조이다. 큐의 가장 큰 특징은 '선입선출'(FIFO: First In First Out) 원칙을 따른다는 점이다. 이는 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 의미한다.

== FIFO vs LIFO ==
데이터 구조를 이해하는 데 있어 FIFO와 LIFO의 개념은 매우 중요합니다.

=== FIFO (First In First Out) ===
* FIFO는 '''"먼저 들어온 것이 먼저 나간다"'''는 원칙이다.
* 큐(Queue)가 대표적인 FIFO 구조다.
* 실생활의 예: 계산대에 줄 서 있는 사람들, 프린터의 인쇄 대기열

=== LIFO (Last In First Out) ===
자세한 내용은 [[스택(프로그래밍)]] 문서를 참고하세요!

* LIFO는 '''"나중에 들어온 것이 먼저 나간다"'''는 원칙이다.
* 스택(Stack)이 대표적인 LIFO 구조다.
* 실생활의 예: 접시 쌓기, 웹 브라우저의 뒤로 가기 버튼

== 큐(Queue)의 특징 ==
# FIFO 원칙: 가장 먼저 들어온 데이터가 가장 먼저 나간다.
# 주요 작업:
## Enqueue: 큐의 뒤쪽(rear)에 새로운 요소를 추가한다.
## Dequeue: 큐의 앞쪽(front)에서 요소를 제거한다.
# 주요 위치:
## Front: 큐의 첫 번째 요소 위치
## Rear: 큐의 마지막 요소 위치

== 큐의 기본 연산 ==
# enqueue(item): 큐의 뒤쪽(rear)에 새로운 요소를 추가한다.
# dequeue(): 큐의 앞쪽(front)에서 요소를 제거하고 반환한다.
# front(): 큐의 첫 번째 요소를 반환하지만 제거하지는 않는다.
# isEmpty(): 큐가 비어있는지 확인한다.
# isFull(): 큐가 가득 찼는지 확인한다. (배열로 구현된 경우)

== 큐의 구현 방식 ==
큐는 주로 두 가지 방식으로 구현된다:

=== 1. 배열 기반 구현 ===
배열을 사용하여 큐를 구현하는 방식이다. 

==== 장점 ====
* 구현이 간단하다.
* 랜덤 접근이 가능하다.

==== 단점 ====
* 크기가 고정되어 있어 큐가 가득 찼을 때 새로운 요소를 추가할 수 없다.
* 큐에서 요소를 제거할 때마다 모든 요소를 앞으로 이동시켜야 할 수 있다.

==== C언어 예제 ====
<syntaxhighlight lang="c">
#include <stdio.h>
#define MAX_SIZE 100

typedef struct {
    int items[MAX_SIZE];
    int front;
    int rear;
} Queue;

void initializeQueue(Queue *q) {
    q->front = -1;
    q->rear = -1;
}

int isEmpty(Queue *q) {
    return (q->front == -1 && q->rear == -1);
}

int isFull(Queue *q) {
    return (q->rear == MAX_SIZE - 1);
}

void enqueue(Queue *q, int value) {
    if (isFull(q)) {
        printf("Queue is full!\n");
        return;
    }
    if (isEmpty(q)) {
        q->front = 0;
    }
    q->rear++;
    q->items[q->rear] = value;
}

int dequeue(Queue *q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    int item = q->items[q->front];
    if (q->front == q->rear) {
        initializeQueue(q);
    } else {
        q->front++;
    }
    return item;
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));

    return 0;
}
</syntaxhighlight>

=== 2. 연결 리스트 기반 구현 ===
연결 리스트를 사용하여 큐를 구현하는 방식이다.

==== 장점 ====
* 크기가 동적으로 조절된다.
* 요소의 추가와 제거가 효율적이다.

==== 단점 ====
* 추가적인 메모리가 필요하다. (포인터를 저장해야 하므로)
* 랜덤 접근이 불가능하다.

==== C언어 예제 ====
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* front;
    Node* rear;
} Queue;

void initializeQueue(Queue* q) {
    q->front = q->rear = NULL;
}

int isEmpty(Queue* q) {
    return (q->front == NULL);
}

void enqueue(Queue* q, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty(q)) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty!\n");
        return -1;
    }

    Node* temp = q->front;
    int item = temp->data;

    q->front = q->front->next;
    free(temp);

    if (q->front == NULL) {
        q->rear = NULL;
    }

    return item;
}

int main() {
    Queue q;
    initializeQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("%d\n", dequeue(&q));
    printf("%d\n", dequeue(&q));

    return 0;
}
</syntaxhighlight>

== 큐의 응용 분야 ==
큐는 다양한 분야에서 활용된다:

# 운영 체제의 작업 스케줄링
# 네트워크의 데이터 패킷 전송
# 프린터의 인쇄 작업 대기열
# 웹 서버의 요청 처리
# 너비 우선 탐색(BFS) 알고리즘
# 캐시(Cache) 구현

== 큐의 변형 ==
# 원형 큐(Circular Queue): 배열의 처음과 끝이 연결된 형태의 큐.
# 우선순위 큐(Priority Queue): 각 요소에 우선순위가 부여되어 있어, 우선순위가 높은 요소가 먼저 나가는 큐.
# 데크(Deque, Double-ended Queue): 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐.

== 결론 ==
큐는 FIFO 원칙을 따르는 간단하면서도 강력한 자료 구조이다. 이 구조는 많은 실제 상황을 모델링하는 데 이상적이며, 컴퓨터 과학의 여러 분야에서 중요한 역할을 한다. 큐의 개념을 이해하고 적절히 활용할 수 있다면, 다양한 프로그래밍 문제를 효과적으로 해결할 수 있을 것이다.<s>악 코딩테스트</s>

<!--분류-->
[[분류:자료구조]] [[분류:알고리즘]] [[분류:컴퓨터 과학]]