[lecture] 큐

큐란 스택과 마찬가지로 삽입과 삭제의 위치가 제한되어 있는 유한 순서 리스트이다. 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조이다. > 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입한 원소는 맨 앞에 있다가 가장 먼저 삭제된다. > 선입선출구조

선형 큐

스택이 연탄이면, 큐는 한줄서기 > push. pop : enQueue. deQueue

모든 자료구조는 array(seq structure)와 linked list 로 이루어져 있다.

초기상태(공백 큐)는 front = rear = -1 이다. 삽입된 상태(enQueue(Q,A))에서는 rear가 A를 가리키고, enQueue(Q,B)에서는 rear가 B를 가리키는 상태가 된다. 원소를 삭제할 때(deQueue(Q))는 front를 A에 위치시킨다음 그 A를 삭제시킨다. 다시말해 front index = 1st element - 1 이 되고, rear index = last element index 가 된다. 그 상태에서 C를 삽입하려면 그 위치로 rear index를 하나 증가시킨 후 그 위치에 C를 삽입시킨다. 뺄 때는 index를 하나 증가시키고 거기 있는 것을 삭제하면 된다. 그렇다면 front는 빈 곳을 가리키게 된다. 이 상태를 overhead 라고 하며 불편한 상황이라고 본다.

위에서 말한 1차원 배열을 이용한 큐를 선형 큐라고 한다. 큐의 크기는 배열의 크기와 같고, 변수의 front는 저장된 첫 번째 원소의 인덱스를 저장하며, 변수 rear는 저장된 마지막 원소의 인덱스를 저장한다. 이 상태를 표현할 때, 초기 상태는 front = rear = -1, 공백 상태는 front = rear 그리고 포화 상태는 rear = 배열의 크기 - 1 = 배열의 마지막 인덱스 라고 한다.

#define MAX_QUEUE_SIZE 100
typedef struct{
	int key;
    /* other fields */
} element;
element queue[MAX_QUEUE_SIZE];
int rear = -1;
int front = -1;
//IsEmptyQ(queue)
return (front == rear)
//IsFullQ(queue)
return rear == (MAX_QUEUE_SIZE - 1)
//add to a queue
void addq(int *prear, element item){
	if(*prear == MAX_QUEUE_SIZE - 1){
    	queue_full();
        return;
    }
    queue[++*prear] = item;
}
//delete from a queue
element deleteq(int *pfront, int rear){	//empty check를 위해서
	if(*pfront == rear)
    	return queue_empty();
    return queue[++*front];
}

(실제로는 queue full은 없다, 인덱스를 앞으로 땡기면 해결되기 때문이다. 하지만 이러한 이동 작업은 연산이 복잡해 효율성이 떨어진다.)

//초기 상태 큐 생성 알고리즘
/* 크기가 n인 1차원 배열을 생성, front와 rear를 -1로 초기화한다.*/
createQueue()
	Q[n];
    front <- -1;
    rear <- -1;
end createQueue()

선형 큐의 잘못된 포화 상태 인식을 해결하기 위한 방법 1. 원형 큐 2. 연결 큐(?)

원형 큐

원형 큐(Circular Queue)란 1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정하고 사용한다. 원형 큐에서 0 <= front, rear <= n-1 이기 때문에 초기 공백 상태는 front = rear = 0, front와 rear의 위치가 배열의 마지막 인덱스 n-1에서 논리적인 다음 자리인 인덱스 0 번으로 이동하기 위해서 나머지 연산자 mod를 사용한다.(front = (front + 1) % n) 공백 상태와 포화 상태 구분을 쉽게 하기 위해서 front가 있는 자리는 사용하지 않고 항상 빈자리로 둔다.  >> array로 queue를 만들려면 circular queue를 이용해야 한다.

원형 큐의 특징 : full queue와 empty queue 검사는 동일하지만 구분하기 위해서는, 1. 최대 원소 개수는 MAX_QUEUE_SIZE - 1 해야 한다. (둘 사이를 구분하기 위해) 2. 다 채우고 싶다면 둘을 구분해줄 변수 하나를 추가해줘야 한다.

full이 아닌데 full로 인식하는 오류 있을 때 앞으로 땡기는 오버 헤드가 컸던 선형 큐와 다르게, 원형 큐는 그러한 오버헤드는 없다. (O(n) > O(1)) >> 시간 복잡도 감소

createQueue(); 에서 front 와 rear 값은 0으로 되어 있다.

enQueue(cQ,A); 로 새로운 원소 A를 삽입하는 경우 항상 rear에 집어 넣는다. 집어 넣기 전에 인덱스 값을 증가시켜주고, (rear인덱스의 초기값은 0인데,이것을 1로 증가시켜주고) A를 삽입시켜준다. 이 상태에서 front는 첫번째 원소 그 앞의 인덱스이다.(여기서 첫번째 인덱스는 A > 따라서 이 앞의 인덱스는 [0]) 여기서 1st element = last element이다.  > rear <= (0+1) mod 4; cQ[1] <- A;

front index는  시계반대 방향으로 가리켜야 한다.

이 큐에 몇 개 들어있는지 확인하는 식 : (rear - front) mod n 여기서 n은 배열의 크기 > n이기 때문에 범위가 0부터 n-1까지이다.

6번 이후 enqueue(cQ,E)를 한다면, [1]에 E가 들어가야 할 상황인데, rear를 [1]로 이동시켜둔다면 rear = front 상황이 발생하여 full인데, entity 인지 분간이 어렵다. 여기서 circular Queue에서 full인 상황일 때는 원소의 개수가 n-1일 때를 말한다. 따라서 이 상황은 full 이기 때문에 원소를 집어 넣을 수 없다. 

//add to a circular queue
void addq(int front, int *prear, element item){
	*prear = (*prear + 1) % MAX_QUEUE_SIZE;
    if (front == *prear){
    	queue_full(prear);
        	/* reset rear and print error >> *prear = (*prear - 1) % MAX_QUEUE_SIZE */
        return;
    }
    queue[*prear] = item;
}
//delete from a circular queue
element deleteq(int *pfront, int rear){
	element item;
    if(*pfront == rear)
    	return queue_empty();
        	/* queue_empty returns an error key */
    *pfront = (*pfront + 1) % MAX_QUEUE_SIZE;
    return queue[*pfront];    
}

연결 큐

연결 큐(linked Queue)는 단순 연결 리스트를 이용한 큐이다. 큐의 원소는 단순 연결 리스트의 노드이고, 큐의 원소의 순서는 노드의 링크 포인터로 연결하며, 변수 front 는 첫 번째 노드를 가리키는 포인터 변수이고 변수 rear는 마지막 노드를 가리키는 포인터 변수를 의미한다. 초기 상태와 공백 상태는 front = rear = null 이다. 다시말해 front는 header 역할을 겸용하며 rear는 tail의 역할을 겸용한다. 

큐의 응용

운영체제의 작업 큐는 예를 들어 수강신청, 기차표 예매이다.