큐 (Queue)

큐(Queue)란?

선입선출(FIFO, First In First Out) 구조를 따르는 선형 자료구조
즉, 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 방식으로 동작하며, 줄 서기나 버퍼와 같은 형태
넓이 우선 탐색(BFS), 프린터 대기열 관리, CPU 작업 스케줄링 등 순서가 중요한 작업에 자주 사용

주요 연산

1. enqueue: 큐의 뒤에 새로운 요소를 추가
2. dequeue: 큐의 앞에 있는 요소를 제거하고 반환
3. peek 또는 front: 큐의 앞에 있는 요소를 반환 (제거하지 않음)
4. isEmpty: 큐가 비어 있는지 확인
5. size: 큐에 있는 요소의 개수를 반환

특징

1. 선입선출 (FIFO): 가장 먼저 삽입된 요소가 가장 먼저 제거됩니다.
2. 양쪽 접근 제한: 삽입과 삭제가 큐의 양 끝에서만 이루어짐
3. 연산의 단순성: 삽입과 삭제 연산 시간 복잡도가 O(1)

장점

1. 순서 보장: 큐는 데이터의 순서를 유지하며, 순차적으로 처리
2. 효율적 데이터 흐름 관리: 데이터가 들어오는 순서대로 처리할 때 효율적

단점

1. 중간 접근 불가: 큐의 중간에 있는 요소를 접근하거나 수정할 수 없음
2. 제한된 탐색 기능: 큐는 순차 접근만 가능하므로, 특정 요소를 검색하는 데 비효율적

구현 예시

배열을 이용한 구현

큐의 front와 rear를 사용하여 요소를 관리

#include <iostream>
using namespace std;

#define MAX 5  // 큐의 최대 크기

class Queue {
    int front, rear;
    int arr[MAX];

public:
    Queue() {
        front = -1;  
        rear = -1;  // 초기화
    }

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

    // 큐가 가득 찼는지 확인
    bool isFull() {
        return rear == MAX - 1;
    }

    // 큐에 요소 추가
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is Full\n";
            return;
        }
        if (front == -1) front = 0;  // 첫 번째 요소 삽입 시 front 초기화
        arr[++rear] = value;  // rear를 증가시키고 요소 추가
        cout << value << " enqueued to queue\n";
    }

    // 큐에서 요소 제거
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is Empty\n";
            return;
        }
        cout << arr[front] << " dequeued from queue\n";
        front++;
        if (front > rear) {  // 큐가 비면 초기화
            front = rear = -1;
        }
    }

    // 큐의 맨 앞 요소 반환
    int peek() {
        if (isEmpty()) {
            cout << "Queue is Empty\n";
            return -1;
        }
        return arr[front];
    }

    // 큐 출력
    void printQueue() {
        if (isEmpty()) {
            cout << "Queue is Empty\n";
            return;
        }
        cout << "Queue: ";
        for (int i = front; i <= rear; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
    }
};

int main() {
    Queue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.printQueue();  // Queue: 10 20 30
    q.dequeue();
    q.printQueue();  // Queue: 20 30
    return 0;
}

라이브러리

#include <iostream>
#include <queue>
using namespace std;

int main() {
    queue<int> q;

    // 요소 삽입
    q.push(10);
    q.push(20);
    q.push(30);

    cout << "큐의 맨 앞 요소: " << q.front() << endl;  // 10
    cout << "큐의 맨 뒤 요소: " << q.back() << endl;   // 30

    // 요소 제거
    q.pop();  // 10 제거
    cout << "큐의 맨 앞 요소 (제거 후): " << q.front() << endl;  // 20

    return 0;
}

원형 큐(Circular Queue)란?

고정된 크기의 배열을 사용하여, 큐의 앞과 뒤가 연결된 순환 구조
일반 큐는 사용하지 않는 공간이 발생할 수 있지만, 원형 큐는 메모리 낭비가 발생하지 않음

특징

1. 순환 구조: 배열의 끝에 도달하면 다시 처음으로 이동하여 빈 공간을 채움
2. 메모리 효율: 원형 큐는 모든 공간을 활용하여 메모리 낭비를 줄임
3. Front와 Rear의 순환 갱신: rear와 front의 인덱스가 배열의 끝에 도달하면, 다시 0으로 갱신되어 계속해서 삽입 및 삭제 가능

선형 큐의 front와 rear값이 계속 증가하기만 한다는 문제점을 극복한 구조

사용 예시

1. 네트워크 패킷 버퍼: 고정된 크기의 버퍼에서 패킷을 관리하여 메모리 효율성을 높임
2. 데이터 스트림 처리 (Data Stream Handling): 데이터 스트림을 관리할 때 데이터가 순환적으로 처리되도록 하는 데 사용
   실시간 데이터가 계속 입력되고, 일정 시간 후 오래된 데이터가 삭제되는 경우에 유용 (센서, 로그 등)
3. 캐시 구현 (Circular Buffer Cache): 브라우저 캐시, 최근 사용한 파일 목록 관리 등에서 새 항목이 들어오면 가장 오래된 항목이 제거되도록 함

데이터가 순환해야 하거나, 제한된 메모리에서 큐를 효율적으로 사용할 때 유리

구현 예시

#include <iostream>
using namespace std;

#define SIZE 5

class CircularQueue {
    int front, rear;
    int arr[SIZE];

public:
    CircularQueue() {
        front = rear = -1;
    }

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

    // 큐가 가득 찼는지 확인
    bool isFull() {
        return (rear + 1) % SIZE == front;
    }

    // 요소 추가 (enqueue)
    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue is Full\n";
            return;
        }
        if (front == -1) front = 0;
        rear = (rear + 1) % SIZE;
        arr[rear] = value;
        cout << value << " enqueued to queue\n";
    }

    // 요소 제거 (dequeue)
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue is Empty\n";
            return;
        }
        cout << arr[front] << " dequeued from queue\n";
        if (front == rear) front = rear = -1;
        else front = (front + 1) % SIZE;
    }

    // 큐의 맨 앞 요소 반환
    int peek() {
        if (isEmpty()) return -1;
        return arr[front];
    }
};

int main() {
    CircularQueue q;
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    q.dequeue();  // 10 dequeued
    q.enqueue(40);
    q.enqueue(50);
    q.dequeue();  // 20 dequeued
    q.enqueue(60);  // 원형 큐에서 메모리 재활용
    return 0;
}

std::deque라이브러리를 사용하면 원형 큐와 유사한 기능을 손쉽게 구현 가능