CSDataStructure

[자료구조] 큐(Queue)

CS, DataStructure

큐(Queue)

1. 큐의 개념

한쪽 끝에서는 삽입 작업만, 또 다른 한쪽 끝에서는 삭제 작업만!

큐(Queue)는 스택과 마찬가지로 삽입과 삭제의 위치와 방법이 제한되어 있는 유한 순서 리스트이지만, 스택과 달리 리스트의 한쪽 끝에서는 삽입 작업이 이루어지고 반대쪽 끝에서는 삭제 작업이 이루어져서, 삽입된 순서대로 삭제되는 선입선출(FIFO, First In Frist Out)의 구조로 운영된다.


2. 큐 - 자료의 삽입과 삭제

큐는 한쪽 끝은 front로 정하여 삭제 연산만 수행하도록 하고, 다른 쪽 끝은 rear로 정하여 삽입 연산만 수행하도록 한다. 따라서 가장 먼저 들어온 프런트 원소가 가장 먼저 삭제되므로 선입선출 구조가 된다.


3. 자료의 삽입

1
2
3
4
5
6
7
enQueue(Q, item)
    if(isFull(Q)) then Queue_Full();
    else {
        rear <- rear + 1;
        Q[rear] <- item;
    }
end enQueue()

포화 상태가 아닌 큐에 원소를 삽입하려면 배열에 저장되어 있는 마지막 원소의 다음 자리에 삽입을 해야 하므로, 마지막 원소의 인덱스를 저장한 rear의 값을 하나 증가시켜 삽입할 자리를 준비하고, 그 인덱스에 해당하는 배열 원소 Q[rear]에 item을 저장한다.


4. 자료의 삭제

1
2
3
4
5
6
7
deQueue(Q)
    if(isEmpty(Q)) then Queue_Empty();
    else {
        front <- front + 1;
        return Q[front];
    }
end deQueue()

공백 상태가 아닌 큐에서 원소의 삭제는 언제나 큐에 저장된 원소 중에서 가장 앞에 있는 원소, 즉 가장 먼저 큐에 들어와 있는 원소를 가장 먼저 삭제해야 한다. 그러기 위해서 front의 위치를 한 자리 뒤로 조정하여 큐에 남아있는 첫 번째 원소의 위치로 이동하여 삭제할 자리를 준비하고, 그 자리의 원소를 삭제하여 반환한다.

1
2
3
4
delete(Q)
    if(isEmpty(Q)) then Queue_Empty();
    else front <- front + 1;
end delete();

delete()연산은 front의 원소를 삭제하는 연산이고 deQueue()연산은 front의 원소를 삭제하고 삭제한 원소를 반환하는 연산이다.

Share