큐(프로그래밍)

개요

큐(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)의 특징

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

큐의 기본 연산

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

큐의 구현 방식

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

1. 배열 기반 구현

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

장점

• 구현이 간단하다.
• 랜덤 접근이 가능하다.

단점

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

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;
}

2. 연결 리스트 기반 구현

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

장점

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

단점

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

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;
}

큐의 응용 분야

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

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

큐의 변형

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

결론

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