3. 큐 (Queue)

큐란?

위키디피아의 큐 이미지

 선입선출(First In First Out / FIFO) 특성을 가지는 선형 자료 구조이다. 앞서 살펴본 스택과는 대비되는 특성으로, 스택과는 반대로 먼저 들어온 데이터가 먼저 나오는 순서를 유지하는 구조를 가지고 있다.

큐의 연산

 큐에는 선형큐, 환형큐, 우선순위 큐 등의 바리에이션이 있지만 여기서는 선형큐를 기준으로 설명한다.

기능	명칭	시간복잡도
삽입	enqueue	O(1)
삭제	dequeue	O(1)

큐의 장점

 1. 작업의 순서를 유지하여야 하는 알고리즘에 적합하다.

 2. 효율적인 삽입과 삭제로 연산 시간이 매우 적다.

 3. 운영체제의 스케줄링, 네트워크 패킷 처리, 예약, 대기열 등 많은 분야에서 활용도가 높다.

 

큐의 단점

 1. 순서를 유지해야하는 특성상 스택과 배열에 비해서는 약간 복잡한 구조.

 2. 스택과 마찬가지로 중간에 있는 데이터에 임의 접근을 할 수 없는 구조.

 

큐의 예시

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

#define MAX 100

typedef struct {
    int data[MAX];
    int front;
    int rear;
} Queue;

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

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

int isFull(Queue *q) {
    return q->rear == MAX - 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->data[q->rear] = value;
}

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

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

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

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

    return 0;
}

 

 C언어 배열을 활용한 기본적인 큐의 예시이다. 순서를 유지하면서 삽입 삭제를 하기위해 front와 rear라는 변수가 주어지고, 삽입은 rear에, 삭제는 front에서 일어난다.