큐 . 자료구조

큐의 개념

큐는 일상생활에서 많이 예를 들 수 있습니다. 택시를 타기 위해 서있는 줄, 급식소에서 급식판을 들고 순서를 기다리는등이 좋은 예입니다. 거기에 컴퓨터 시스템에서도 많이 사용됩니다. 큐는 가장 처음에 제출되어 작업 대기줄에 들어간 작업이 가장 처음에 처리되는 스케줄을 표현하는 자료구조인데요. 앞서 공부했던 스택에 비교하면 공정한 편이라고 할 수 있죠. 말이 나온 김에 스택은 한쪽이 막힌 관처럼 생각해서 입구와 출구가 동일했다면, 큐는 양쪽이 뚫린 관이고 양쪽모두에서 삽입연산과 삭제연산이 이루어질 수 있습니다. 하지만 양쪽모두에서 일어나면 혼란스러울 수 있어 제한을 두어 한쪽에서는 삽입만이 다른 한쪽에선 삭제만이 이루어지게 했습니다. 큐는 스택과 달리 먼저 삽입된 원소가 먼저 삭제되어 선입 선출 또는 선착순 서브 알고리즘과 함께 사용됩니다.

큐의 모습예시

큐의 추상 자료형

• 큐에서는 원소의 삭제가 이루어지는 곳을 앞(front)라고 하고 삽입이 이루어지는 곳을 뒤(rear)이라고 한다.
• 큐에서 기본적으로 사용되는 연산은 원소를 삽입하는 Add(insert_q)와 삭제하는 Delete_q가 있다.
• Add_q연산자를 사용하면 rear포인트를 하나 올려준다.(스택에 top위치를 가리키는 것)
• 메모리에는 한계가 있고 그렇기에 큐의 크기에는 제한이 있다. 이제한은 큐에 삽입할 수 있는 항목의 개수를 제한한다. 그래서 Add_q연산 전에 여유공간을 확인해야 하는데 이를 검사하는 IsFull_q연산을 수행해야 한다. 만일 모두 꽉 차있다면 queueFull 메시지를 반환,, Add_q연산을 멈추게 된다. Full상태가 아니라면 큐의 rear포인터가 가리키는 위치에 삽입을 하고 rear포인터를 증가시키고 Add_q를 연산을 완료한다.
• Delete_q연산자를 사용하면 front포인터를 하나 줄인다.
• 그리고 큐에서 원소를 하나 삭제하려면 삭제할 항목이 있는지 IsEmpty_q로 검사를 해야 하는데, 큐가 Empty면 더 이상 삭제할 수 있는 원소가 없다는 queueEmpty를 메시지 반환하고 Delete_q연산을 멈추거나, Empty가 아니라면 큐의 front포인터가 가리키는 원소를 빼서 다른 장소에 저장하고 fornt포인터를 감소시키고 완료한다.

큐의 추상 자료형
1.Queue Create_q(maxQueueSize)
→ 큐의 크기가 maxQueueSize인 빈 큐를 생성하고 반환한다.
1.Boolean IsFull_q(queue, maxQueueSize)
→ if((queue의 원소 개수가) == maxQueueSize) then (TRUE 반환), else (FALSE 반환)
1.Queue Add_q(queue, item)
→if(IsFull_q(queue))
then(queueFull을 출력한다)
else(큐의 rear에서 item을 삽입하고 큐를 반환하고 rear의 포인터를 하나 올려준다.)
1.Boolean IsEmpty_q(queue)
→if(rear == front) , 두 개의 위치가 같다면 True, 아니라면 FALSE를 반환한다.
1.Element Delete_q(queue)
→if(IsEmpty_q(queue)) 
then('queueEmpty)를 출력한다.
else(큐의 front에 있는 원소를 삭제하고 front포인터를 하나 줄인다.

큐의 추상 자료형은 큐에 대한 객체의 정의와 적용 가능한 연산으로 이루어진다.

아래의 예시를 알아보자

1. Creat_q(4);  → 원소 네 개를 저장할 수 있는 큐를 생성, 이때 rear과 front의 위치는 모두 제일 앞에 위치해 있음
2. Add_q(queue, A)  →  A를 rear위치에 삽입하고 rear 포인터는 1 증가
3. Add_q(queue, B)  → B를 rear위치에 삽입하고 rear 포인터는 1 증가
4. Add_q(queue, C)  → C를 rear위치에 삽입하고 rear 포인터는 1 증가
5. Delete_q(queue)  → front위치에 있는 A를 삭제하고 front포인터 1 증가(B)
6. Delete_q(queue)  → front위치에 있는 B를 삭제하고 front포인터 1 증가(C)
7. Delete_q(queue)  → front위치에 있는 C를 삭제하고 front포인터 1 증가(이제는 front포인터와 rear의 위치가 같아짐 즉 queueEmpty)
8. Add_q(queue, D)  → D를 rear위치에 삽입하고 rear 포인터는 1 증가

큐의 응용

많은 프로그램은 CPU의 할당을 받기 위해 줄을 서서 대기하는데 CPU를 잘 관리하면 프로그램이 빨리 싱행되고 전체 컴퓨터의 처리 시간도 짧아지게 됩니다. 이때 큐를 활용하여 CPU의 관리방법을 알아자면 다음과 같습니다.

1. FCFS(first-come-first-saved) 스케줄링 기법 - 먼저 들어온 프로그램이 순수대로 CPU에 할당되는 기법이고, 중요하거나 짧은 작업이 나중에 들어온다면 덜 중요하고 오래 걸리는 작업을 기다려야 하는 단점이 있다.
2. BB(Round Robin) 스케줄링 기법 - 대화형 시스템에 사용되며 도착한 순서대로 CPU에 할당되지만 CPU의 시간 할당량 또는 시간 간격에 의해 제한을 받게 됩니다. ABC순서대로 있다면 A를 일정시간만 처리하다가 안되면 제일 뒤로 넘기고 B를 일정시간만처리하다가 안되면 뒤로 넘기는 것으로 프로그램이 CPU를 독점하지 않고 공평하게 이용할 수 있지만 우선순위가 높은 작업을 빨리 처리하기 어려운 단점도 있다.

배열을 이용한 큐의 구현

#define QUEUE_SIZE 5
typedef int element;
element queue(QUEUE_SIZE);
int front = -1;
int rear = -1;

큐의 크기를  5로 정의합니다.
큐의 원소인 element를 int형으로 정의하고요.
자료형 element를 저장할 수 있는 큐를 큐의 크기만큼 할당받습니다.
rear, front는 전역변수로 정의되고 큐의 삽입이 발생하는 rear과 삭제가 발생하는 front의 초기값을 -1로 저장하여 공백 상태로 합니다.

변수 rear의 값은 공백상태를 나타내는 -1로 시작해 주어야 하고 add_q연산을 수행한 이후에는 0이 되고 계속 수행한다면 4까지 증가합니다. rear의 값이 5인 큐는 풀상태를 의미하는 것이고요.

큐 삽입 연산

void Add_q(element item){
if(rear == QUEUE_SIZE-1)
{
printf("Queue is full!!");
return;
}
queue [++rear] = item;
return;
}

위의 예시는 삽입연산 Add_q를 호출했을 때 rear을 이용해 풀인지 검사해야 하는데 rear은 -1부터 시작되기 때문에 size에서 -1을 뺀 것과 같다면 풀상태이니 Queue is full!! 를 추력하고 아니라면 rear에 +1을 더한 곳에 값을 저장한다라는 것입니다.

큐의 삭제 연산

element Delete_q( ) {
if(front == rear) {
printf("Queue is empty");
return;}
return(queue [++fornt]);
}

Delete_q를 호출하면 전역변수 front는 큐의 삭제가 발생하는 위치 한 칸 앞부분을 가리키고 있고, 먼저 큐가 빈상태 이은 지 검사해야 하는데 큐가 비어있는 상태라면 front == rear일 테니 Queue is empty를 출력하고 아니라면 삭제할 수 있다는 것을 의미하고 삭제하기 위해 fornt값을 하나 증가시키고 위치에 있는 원소 값을 반환하게 됩니다.

 

큐의 삽입과 삭제연산은 다음예시와 같습니다.

원형큐

하지만 큐를 배우다 보니 의문이 생겼다 결국 원소가 채워지고 삭제를 하다 보면 5개의 원소를 저장할 수 있는 큐가 있다고 가정하면 결국에 언제 가는 front와 rear은 4번째 배열인 가장 나중에 오게 되면 더 이상 저장을 할 수 없고 그 앞에 공간은 사용을 못하는 것 아닌가?? 이거에 대한 내용이 원형큐에서 나온다.

 

위의 궁금증대로 위 그림에서 rear의 값이 -1에서 점점 증가해 4가 된다고 하더라도 실제로 rear의 값은 텅 비더라고 계속해서 4니까 결국 rear의 값은 큐의 만원 상태를 결정하는 것은 아니었다는 것이죠.  그래서 이러한 문제점을 해결하는 것이 원형큐라는 것인데 원형으로 입구와 출구 부분을 연결시킨 형태라고 생각할 수 있다. 근데 이것은 결국에 rear의 값을 다 4 다음에 -1일이 되게 해야 하는 것인데 이것을 연관 연관식에서 나머지를 계산하는 mod연산자를 사용하여 rear값을 관리하게 하는 이유라고 합니다. 오대단하다... 이런 걸 생각하다니..
원형 큐에 항목을 삽입하는 경우에는

rear ← (rear+1) mod n 혹은 front ← (front+1) mod n의 연산식을 이용할 수 있습니다.

예를 들어 rear가 3인 상태에서 삽입이 이루어진다고 가정해 보면 (3+1) mod 5의 연산식 결과인 4를 rear값으로 결정합니다 문제가 되는 rear가 4인상태에서 삽입이 이루어지면 (4+1) mod 5의 결과인 0을 rear값으로 결정하는 것이죠 나머지연산을 이용해 앞부분의 빈 공간을 원소의 삽입에 사용할 수가 있는 것으로 작은 아이디어 하나를 활용해 메모리 활용도를 높인 것이