[Data Structure] 큐(Queue)

큐(Queue) 란?

---

큐(Queue)란?
-> Queue는 스택과(LIFO)는 반대로 FIFO(First In First Out) 구조를 가진 자료구조입니다.
즉, 가장 먼저 들어간 데이터가 가장 먼저 나가는 구조입니다.

Queue는 다음과 같은 특징을 가지고 있습니다.

• 선입선출(FIFO): 먼저 들어온 데이터가 먼저 나갑니다.
• 추가(enqueue): 큐의 뒷부분에 데이터를 추가합니다.
• 삭제(dequeue): 큐의 앞부분에서 데이터를 삭제합니다.

큐의 종류로는 2가지가 있습니다.

---

선형 큐 (Linear Queue)

배열을 이용하여 구현하는 가장 기본적인 큐입니다.

장점

• 구현이 간단합니다.

단점

• 배열의 크기가 고정되어 있어 미리 할당해야 합니다.
• 큐가 가득 찼을 때 추가적인 데이터를 삽입할 수 없습니다.
• 큐의 앞쪽에 빈 공간이 생기면 모든 데이터를 뒤로 이동해야 합니다.

---

환형 큐 (Circular Queue)

배열을 원형으로 연결하여 구현하는 큐입니다.

장점

• 배열의 공간을 효율적으로 사용할 수 있습니다.
• 큐가 가득 찼더라도 공간이 비어 있으면 데이터를 삽입할 수 있습니다.

단점

• 구현이 선형 큐보다 복잡합니다.
• front와 rear를 관리하는 로직이 필요합니다.

---

사용하는 이유(용도)

---

• 프린터의 출력 대기열, 버스 정류장의 승객 대기열
• CPU 스케줄링, 디스크 스케줄링
• 상기를 포함한 FIFO를 구현해야 하는 경우

문제점&주의사항

---

• 오버플로: 큐에 너무 많은 데이터가 들어가면 오버플로가 발생할 수 있습니다.
• 언더플로: 큐가 비어 있는 상태에서 데이터를 삭제하려고 하면 언더플로가 발생할 수 있습니다.
• 구현 복잡도: 환형 큐의 경우, 선형 큐에 비해 구현이 복잡할 수 있습니다.

예제

---

[선형 큐(Linear Queue)] - Array를 이용

#include <iostream>

using namespace std;

#define MAX_SIZE 100

int queue[MAX_SIZE];
int front = -1;
int rear = -1;

// 큐에 데이터 삽입
void enqueue(int data) {
    if (rear == MAX_SIZE - 1) {
        cout << "Queue Full" << endl;
        return;
    }
    rear++;
    queue[rear] = data;
}

// 큐에서 데이터 삭제
int dequeue() {
    if (front == rear) {
        cout << "Queue Empty" << endl;
        return -1;
    }
    front++;
    return queue[front];
}

[선형 큐(Linear Queue)] - List를 이용

#include <iostream>
#include <list>

using namespace std;

list<int> queue;

// 큐에 데이터 삽입
void enqueue(int data) {
    queue.push_back(data);
}

// 큐에서 데이터 삭제
int dequeue() {
    if (queue.empty()) {
        cout << "Queue Empty" << endl;
        return -1;
    }
    int data = queue.front();
    queue.pop_front();
    return data;
}

[환형 큐(Circular Queue)]

#include <iostream>

using namespace std;

#define MAX_SIZE 100

int queue[MAX_SIZE];
int front = -1, rear = -1;

bool isFull() {
    return (rear + 1) % MAX_SIZE == front;
}

bool isEmpty() {
    return front == rear;
}

void enqueue(int data) {
    if (isFull()) {
        cout << "Queue Overflow" << endl;
        return;
    }
    rear = (rear + 1) % MAX_SIZE;
    queue[rear] = data;
}

int dequeue() {
    if (isEmpty()) {
        cout << "Queue Underflow" << endl;
        return -1;
    }
    front = (front + 1) % MAX_SIZE;
    return queue[front];
}

int main() {
    enqueue(1);
    enqueue(2);
    enqueue(3);

    cout << dequeue() << endl;  // 1 출력
    cout << dequeue() << endl;  // 2 출력

    return 0;
}

Top