Queue

큐

• 특정 자료를 저장할 수 있는 배열 형태의 자료구조이다.
• 데이터의 삽입은 뒤(rear)에서, 삭제는 앞(front)에서 일어나는 특징이 있다.
• 선입선출(FIFO, First-In First-Out) 구조로, 먼저 들어온 데이터가 먼저 나가는 방식이다.

특징 및 종류

선형 큐 (Linear Queue)

• 데이터를 꺼낼 때마다 front 포인터가 뒤로 이동한다.
• 배열의 앞부분이 비어 있어도 활용하지 못해 메모리 낭비가 발생할 수 있다.

원형 큐 (Circular Queue)

• 선형 큐의 단점을 보완하기 위해 배열의 처음과 끝이 연결된 것처럼 동작하게 만든다.
• 포인터가 배열의 끝에 도달하면 다시 0번 인덱스로 순환(Modular)하도록 처리하여 공간을 재사용한다.

기본 구현 방법

1. 데이터를 저장할 배열과 크기를 선언한다.
2. front와 rear라는 두 개의 포인터를 사용한다.
   • front: 가장 앞에 있는 데이터의 위치(또는 바로 앞)를 가리킨다.
   • rear: 가장 마지막에 데이터가 삽입된 위치를 가리킨다.
3. 삽입(Enqueue): rear를 다음 위치로 이동시킨 후 데이터를 저장한다.
4. 삭제(Dequeue): front를 다음 위치로 이동시키고 해당 위치의 데이터를 반환한다.

소스코드

#include <stdio.h>

typedef char bool;
const bool true = 1;
const bool false = 0;

#define MAX_IDX 100
int queue[MAX_IDX];
int front = 0;
int rear = 0;

// 큐가 비어있는지 확인
bool isEmpty() {
    return (front == rear);
}

// 큐가 가득 찼는지 확인
bool isFull() {
    return NONE; // 일반적으로는 큐의 길이를 매우 늘리기 때문에, 일어나지 않도록 조절함
}

// 데이터 삽입
void enqueue(int x) {
    if (isFull()) {
        printf("[Error] : Queue is full!\n");
        return;
    }
    queue[rear++] = x; // 다음 위치로 순환 이동
}

// 데이터 추출
int dequeue() {
    if (isEmpty()) {
        printf("[Error] : Queue is empty!\n");
        return -1;
    }
    int res = queue[front++]; // 다음 위치로 순환 이동
    return res;
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);

    printf("%d\n", dequeue()); // 10
    printf("%d\n", dequeue()); // 20
    
    return 0;
}

시간 복잡도

• 삽입 및 삭제: front와 rear 포인터만 이동시키면 되므로 $O(1)$의 복잡도를 가진다.
• 접근: 인덱스를 통해 특정 데이터에 접근할 경우 $O(1)$로 가능하다.