[자료구조] 큐(Queue) PART.2

1. 연결 자료구조를 이용한 큐의 구현

1) 단순 연결 리스트를 이용한 큐

• 큐의 원소 : 연결 리스트의 노드
• 큐의 원소의 순서 : 노드의 링크 포인터로 연결
• 변수 front : 첫 번째 노드를 가리키는 포인터 변수
• 변수 rear : 마지막 노드를 가리키는 포인터 변수

 

2) 상태 표현

• 초기 상태와 공백 상태 : front = rear = NULL

 

3) 연결 큐의 구조

A	→	B	→	C	→	D	NULL
front						rear

 

4) 연결 큐 알고리즘

(1) 초기 공백 연결 큐 생성 알고리즘

• 초기화 : front = rear = NULL

 

isEmpty(LQ)
	if(front = NULL) then return true;
	else return false;
end isEmpty()

 

(2) 공백 연결 큐 검사 알고리즘

• 공백 상태 : front = rear = NULL

 

createLinkedQueue()
	front <- NULL;
	rear <- NULL;
end createLinkedQueue()

 

(3) 연결 큐 삽입 알고리즘

1. 삽입할 새 노드를 생성
2. 데이터 필드에 item을 저장
3. 삽입할 새 노드는 연결 큐의 마지막 노드가 되어야 하므로 링크 필드에 NULL을 저장
4. 새 노드를 삽입하기 전에 연결 큐가 공백인지 아닌지 검사
    - 연결 큐가 공백일 때 삽입할 새 노드가 큐의 첫 번째 노드이자 마지막 노드이므로 포인터 front와 rear가 모두 새 노드를 가리키도록 설정
5. 큐가 공백이 아닌 경우
    - 노드가 있을 때는 현재 큐의 마지막 노드의 뒤에 새 노드를 삽입하고 마지막 노드를 가리키는 rear가 삽입한 새 노드를 가리키도록 설정

 

enQueue(LQ, item)
	new <- getNode();	// 1
	new.data <- item;	// 2
	new.link <- NULL;	// 3
	if(front = NULL) then{	// 4
		rear <- new;
		front <- new;
	}
	else{	// 5
	rear.link <- new;
	rear <- new;
	}
end enQueue()

 

(4) 연결 큐 삭제 알고리즘

1. 삭제 연산에서 삭제할 노드는 큐의 첫 번째 노드로써 포인터 front가 가리키고 있는 노드다. front가 가리키는 노드를 포인터 old가 가리키게 하여 삭제할 노드를 지정
2. 삭제 연산 후에는 현재 front 노드의 다음 노드가 front 노드(첫 번째 노드)가 되어야 하므로 포인터 front를 재설정
3. 현재 큐에 노드가 하나뿐이어서 삭제연산 후에 공백 큐가 되는 경우 : 큐의 마지막 노드가 없어지므로 포인터 rear를 NULL로 설정
4. 포인터 old가 가리키고 있는 노드를 삭제하고 메모리 공간을 시스템에 반환(return Node())

 

deQueue(LQ)
	if(isEmpty(LQ)) then Queue_Empty();
	else{
		old <- front;	// 1
		item <- front.data;
		front <- front.link;	// 2
		if(isEmpty(LQ)) then rear <- NULL;	// 3
		return Node(old);	// 4
		return item;
	}
end deQueue()

delete(LQ)
	if(isEmpty(LQ)) then Queue_Empty();
	else{
		old <- front;
		front <- front.link;
		if(isEmpty(LQ)) then rear <- NULL;
		return Node(old);
	}
end delete()

 

 

2. 큐의 응용

1) 연결 큐의 문제점

기존 큐의 문제는 front와 rear가 붙어있으면 포화상태로 잘못 인식하여 잘못된 연산을 수행한다.

 

삭제 ←			← 삽입
	front	rear

 

위와 같은 상황 시에 원소들을 배열의 앞부분으로 이동시켜서 위치를 조정해야 한다. 그러나 위치를 조정하기에는 이동 작업 연산이 복잡하고 큐의 효율성을 떨어뜨린다. 그래서 고안한 게 원형 큐다.

 

2) 원형 큐의 구조

• 초기 공백 상태 : front = rear = 0
• front와 rear의 위치가 배열의 마지막 인덱스 n - 1에서 논리적인 다음 자리인 인덱스 0번으로 이동하기 위해서 나머지 연산자 mod를 사용
• 3 / 4 = 0 ... 3 (몫 = 0, 나머지 = 3)
• 3 mod 4 = 3
• 공백 상태와 포화 상태 구분을 쉽게 하도록 front가 있는 자리는 사용하지 않고 항상 빈자리로 둔다.

 

3) 원형 큐 알고리즘

(1) 초기 공백 원형 큐 생성 알고리즘

• 크기가 n인 1차원 배열 생성
• front와 rear를 0으로 초기화

 

createQueue()
	cQ[n];
	front <- 0;
	rear <- 0;
end createQueue()

 

(2) 원형 큐의 공백 상태, 포화상태 검사 알고리즘

• 공백 상태 : front = rear
• 포화 상태 : 삽입할 rear의 다음 위치 = front의 현재 위치
• (rear + 1) mod n = front

 

isEmpty(cQ)
	if(front = rear) then return true;
	else return false;
end isEmpty()

isFull(cQ)
	if(((rear + 1) mod n) = front) then return true;
	else return false;
end isFull()

 

(3) 원형 큐의 삽입 알고리즘

• rear의 값을 조정하여 삽입할 자리준비 : rear <- (rear + 1) mod n;
• 준비한 자리 cQ[rear]에 원소 item을 삽입

 

enQueue(cQ, item)
	if(isFull(cQ)) then Queue_Full();
	else{
		rear <- (rear + 1) mod n;
		cQ[rear] <- item;
end enQueue()

 

(4) 원형 큐의 삭제 알고리즘

• front의 값을 조정하여 삭제할 자리를 준비
• 준비한 자리에 있는 원소 cQ[front]를 삭제하여 반환

 

deQueue(cQ)
	if(isEmpty(cQ)) then Queue_Empty();
	else{
		front <- (front + 1) mod n;
		return cQ[front];
	}
end deQueue()

delete(cQ)
	if(isEmpty(q)) then Queue_Empty();
    else front <- (front + 1) mod n;
end delete()