C YC

IT Dev who working in Republic Of Korea

3 minute read

큐(Queue) 란?

큐는 FIFO(First In First Out), 즉 선입선출 방식을 따르는 자료구조입니다. 데이터를 삽입하는 것을 enqueue, 삭제하는 것을 dequeue라고 합니다. 큐는 다음과 같은 특징을 가지고 있습니다.

  • FIFO (First In First Out): 가장 먼저 들어온 데이터가 가장 먼저 나갑니다. 마치 줄을 서 있는 사람들처럼, 가장 앞에 있는 사람부터 나갑니다.
  • 양방향 접근 제한: 데이터는 큐의 뒤(rear)에서만 삽입하고, 앞(front)에서만 삭제할 수 있습니다. 마치 터널처럼, 큐의 중간에 있는 데이터에는 직접 접근할 수 없습니다.

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

선형 큐 (Linear Queue)

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

장점

  • 구현이 간단합니다.

단점

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

환형 큐 (Circular Queue)

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

장점

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

단점

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

장단점

장점

  • 공정한 처리: 먼저 들어온 데이터를 먼저 처리하므로 공정한 작업 처리가 가능합니다. 마치 은행 대기열처럼, 큐는 공정한 순서로 작업을 처리합니다.

  • 간단한 구조: FIFO 방식은 이해하기 쉽고 구현하기 간편합니다. 마치 줄 서기처럼, 큐는 직관적인 구조를 제공합니다.

  • 다양한 활용: 다양한 분야에서 활용됩니다. (프린터 대기열, CPU 스케줄링, 메시지 큐 등)

단점

  • 접근 제한: 큐의 중간에 있는 데이터에는 직접 접근할 수 없습니다. 마치 터널 중간에 있는 사람에게 직접 말을 걸 수 없는 것처럼, 큐는 중간 데이터 접근이 어렵습니다.

  • 크기 제한: 큐의 크기는 제한되어 있어 크기를 초과하는 데이터를 저장할 수 없습니다. 마치 정해진 공간의 주차장처럼, 큐는 미리 지정된 크기 이상의 데이터를 담을 수 없습니다.

  • 오버플로우/언더플로우: 큐가 가득 찬 상태에서 데이터를 삽입하려고 하면 오버플로우가 발생하고, 큐가 비어있는 상태에서 데이터를 삭제하려고 하면 언더플로우가 발생할 수 있습니다. 마치 꽉 찬 주차장에 차를 넣거나, 빈 주차장에서 차를 빼려고 하는 것처럼, 큐는 오버플로우/언더플로우에 주의해야 합니다.

사용하는 이유(용도)

  • 프린터 대기열: 프린터에 인쇄 작업을 요청하면 큐에 저장되어 순서대로 처리됩니다.
  • CPU 스케줄링: CPU가 처리해야 할 작업을 큐에 저장하여 순서대로 처리합니다.
  • 메시지 큐: 메시지를 큐에 저장하여 비동기 방식으로 처리합니다.
  • 네트워크 패킷 처리: 네트워크 패킷을 큐에 저장하여 순서대로 처리합니다.
  • 운영체제 작업 스케줄링: 운영체제가 처리해야 할 작업을 큐에 저장하여 순서대로 처리합니다.

문제점&주의사항

  • 크기 제한: 큐의 크기를 초과하는 데이터를 저장하려고 하면 오버플로우가 발생합니다. 따라서 큐를 사용할 때 적절한 크기를 지정해야 합니다. 마치 도시 계획처럼, 큐를 사용할 때는 데이터의 양을 미리 예측하고 적절한 크기를 할당해야 합니다.

  • 오버플로우/언더플로우: 큐가 가득 찬 상태에서 데이터를 삽입하거나, 큐가 비어있는 상태에서 데이터를 삭제하려고 하면 오버플로우/언더플로우가 발생할 수 있습니다. 따라서 큐의 상태를 확인하고 예외 처리를 해야 합니다. 마치 안전 점검처럼, 큐를 사용할 때는 오버플로우/언더플로우를 대비해야 합니다.

  • 구현 복잡도(환형 큐): 환형 큐의 경우, 선형 큐에 비해 구현이 복잡할 수 있습니다. front와 rear를 관리하는 로직을 주의해서 작성해야 합니다. 마치 미로 찾기처럼, 환형 큐는 구현 시 고려해야 할 사항들이 많습니다.

예제

[선형 큐(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

You May Also Enjoy