[DS] 큐(Queue)란?

큐(Queue)란?

FIFO(First in First out)특성을 가지는 linear list입니다.

Linear list의 한 쪽 끝(rear)위치에서 insert가 이뤄지고 다른 끝(front)에서 delete가 일어납니다.

 

 

 

그림과 같이 array를 사용해서 queue를 구현하면 rear와 front가 모두 증가하는 형식으로 변화가 이뤄집니다.

그렇게 되면 언젠가는 rear가 array 끝 위치에 도달하게 될 것이고 원소를 더 이상 추가하지 못하게 됩니다.

 

즉 공간 사용이 너무 효율적이지 못하게 되는거죠.

 

그래서 나온 해결 방안이 circular queue입니다.

Circular queue에도 문제점은 있습니다.

full과 empty를 구분하는 방법이 모호해지기 때문입니다.

 

 

그래서 마지막 남은 한 개의 빈 공간을 사용하지 않습니다.

즉, front 직전의 마지막 한 원소가 비어 있는 상태를 full로 판정하게 됩니다.

따라서 queue_full 판정의 조건은 ((rear+1)%Q_SIZE == front)이 됩니다.

 

어떤 메소드(method)를 수행한 후 front와 rear의 위치는 front+1(or rear+1)을 queue의 size로 나눈 나머지 값입니다.

 

 

Circular queue를 구현하기 위한 ADT 정의

---

class queue {
    int q[Q_SIZE];
    int front, rear;
public:
    queue();
    void insert_q(int e);
    int delete_q();
    bool queue_full();
    bool queue_empty();
};

queue - queue을 생성한 초기 empty 상태

insert_q - queue에 원소 한 개 추가

delete_q - queue에 원소 한 개 제거

queue_full - 현재 queue가 full인지에 대한 상태 확인

queue_empty - 현재 queue가 empty인지에 대한 상태 확인

 

 

 

함수 구현

---

queue::queue() {
    front = 0;
    rear = 0;
}

queue class의 생성자(constructor)에서는 front와 rear의 값을 0으로 초기화시켜 줍니다.

 

front - queue에서 원소 한 개가 제거될 위치

rear -queue에 원소 한 개를 추가할 위치

 

 

void queue::insert_q(int e) {
    if(!queue_full()) {
        q[rear] = e;
        rear = (rear+1) % Q_SIZE;
    }
}

insert_q는 원소 한 개를 추가하는 함수입니다.

원소를 넣기 전 queue가 가득 찼는지 확인을 해주고 자리가 남았으면 rear 위치에 원소를 넣어줍니다.

rear의 값은 (rear+1)에서 queue의 size로 나눈 나머지 값입니다.

 

 

int queue::delete_q() {
    int tmp;
    if(!queue_empty()) {
        tmp = q[front];
        front = (front+1) % Q_SIZE;
    }
    return tmp;
}

delete_q는 queue에서 원소 한 개를 제거하는 함수입니다.

원소를 제거하기 전 queue가 비어있는지 확인을 해주고 원소가 있다면 front 위치에서 원소를 제거합니다.

원소를 제거 후 front의 값은 (front+1)에서 queue의 size로 나눈 나머지 값입니다.

 

 

bool queue::queue_full() {
    if((rear+1)%Q_SIZE == front) return true;
    else return false;
}

queue_full은 queue가 꽉 찬 상태인지 확인하는 함수입니다.

앞에서도 언급했듯이 circular queue는 front와 rear를 구분하는 방법이 모호해지기 때문에 마지막 자리는 사용하지 않습니다.

즉, rear에서 +1된 값이 front와 같다면 queue는 꽉 찼다는 의미이기 때문에 true를 return합니다.

 

 

bool queue::queue_empty() {
    if(front == rear) return true;
    else return false;
}

queue_empty는 queue가 빈 상태인지 확인하는 함수입니다.

front와 rear의 값이 같으면 queue가 빈 상태라는 의미이기 때문에 true를 return합니다.

 

 

 

 

main함수 구현

---

int main() {
    queue q;
    int tmp;

    q.insert_q(1);
    q.insert_q(2);
    q.insert_q(3);
    q.insert_q(4);
    q.insert_q(5);
    q.insert_q(6);

    while(!q.queue_empty()) {
        cout << q.delete_q() << endl;
    }
    
    return 0;
}

1부터 6까지 원소를 하나씩 queue에 넣어줍니다.

하나씩 원소를 가져오면 숫자가 들어간 순서대로 출력되는 것을 확인할 수 있습니다.

 

 

 

◡̈