7. 큐 (Queue)

1. 큐의 이해와 ADT 정의

 

큐는 ‘FIFO(First-in, First-out) 구조’의 자료구조이다. 
때문에 먼저 들어간 것이 먼저 나오는, 일종의 줄서기에 비유할 수 있는 자료구조이다

 

▣ dequeue '큐'의 기본 연산

∙ enqueue : 큐에 데이터를 넣는 연산 
∙ dequeue : 큐에서 데이터를 꺼내는 연산

※ 큐는 운영체제 관점에서 보면 프로세스나 쓰레드의 관리에 활용이 되는 자료구조이다. 
이렇듯 운영 체제의 구현에도 자료구조가 사용이 된다. 
따라서 운영체제의 이해를 위해서는 자료구조에 대한 이해가 선행되어야 한다.

 

 

큐의 ADT 정의

 

ADT를 대상으로 배열 기반의 큐 또는 연결 리스트 기반의 큐를 구현할 수 있다

---

2. 큐의 배열 기반 구현

 

F :큐의 머리를 의미

R : 큐의 꼬리를 의미

 

enqueue 과정

 

큐의 꼬리를 의미하는 R을 한칸 이동시키고 새 데이터를 저장한다

 

 

dequeue 과정

 

큐의 머리를 의미하는 F가 가리키는 데이터를 반환하고 F를 한 칸 이동시킨다

 

▣  가장 기본적인 배열 기반 큐의 문제점

 

dequque한 배열

 

enqueue 한뒤, 끝까지 이동한 배열, 앞 원소는 비어있다

 

분명 배열은 비어있다. 
하지만 R을 오른쪽으로 한칸 이동시킬 수 없어서 더 이상 데이터를 추가할 수 없다!  

데이터를 더 추가하기 위해서는 R을 인덱스가 0인 위치로 이동시켜야 한다.
그리고 이러한 방식으로 문제를 해결한 것이 바로 ‘원형 큐’이다!

---

▣ 원형 큐

 

 

배열 큐 -> 원형 큐

배열의 머리와 끝을 연결한 구조를  원의 형태로 바라본다.

 

 

단순 배열단순 배열 큐와 마찬가지로 R이 이동한 다음에 데이터 저장한다

 

단순 배열 큐와 마찬가지로 F가 가리키는 데이터 반환 후 F 이동!

 

▣ 원형 큐의 단순한 연산의 문제점

 

큐가 Full 인 경우

 

 

큐가 없는 경우

 

F와 R의 위치만으로는 큐가 Full 이거나 빈경우를 구분 할 수가 없다!

▣ 원형 큐의 단순한 연산의 문제점 해결

 

 

해결 방법은 저장 공간 하나를 잃고 문제점을 해결한다

 

데이터가 하나 존재하는 경우 F와 R이 같은 위치를 가리켰는데, 
초기화 직후에 이 상태가 되게 한다

 

 

하나 비운 상태에선 FULL로 인정한다! 
그러면 Empty와 Full의 구분이 가능하다!

 

---

▣ 원형 큐 구현

 

 

//구조체 정의
#define QUE_LEN 100
typedef int  Data;

typedef struct _cQueue
{
	int _F;
	int _R;
	Data qArr[QUE_LEN]
}CQueue;

 

//이동할 인덱스를 알려줄 헬퍼 함수
int NextIndex(int pos)
{
	if (pos QUE_LEN - 1) 
		return 0;
	else 
		return pos + 1;
}

 

빈상 태와 풀 상태의 위치

 

void QueueInit(Queue * pq)
{
	pq->_F = 0;
	pq->_R = 0;
}


int QIsEmpty(Queue * pq)
{
	if (pq->_F == pq->_R)
		return true;
	else
		return false;
}

//rear을 이동시키고(NextPosIdx 함수의 호출을 통해), 그 위치에 데이터 저장
void Enqueue(Queue * pq, Data data)
{
	if (NextIndex(pq->_R) == pq->_F) // R 이 F와 같으면 NULL
	{
		cout << "Error" << endl;
	}
	//아니라면 R+1로 더해서 이동하고, 배열에 값을 넣는다.
	pq->_R = NextIndex(pq->_R); 
	pq->qArr[pq->_R] = data;
}

//front를 이동시키고(NextPosIdx 함수의 호출을 통해), 그 위치의 데이터 반환
Data Dequeue(Queue * pq)
{
	if (QIsEmpty(pq))
	{
		cout << "Error" << endl;
	}

	pq->_F = NextIndex(pq->_F);

	return pq->qArr[pq->_F];
}

Data QPeek(Queue * pq)
{
	if (QIsEmpty(pq))
	{
		cout << "Error" << endl;
	}
	pq->_F = NextIndex(pq->_F);

	return pq->qArr[NextIndex(pq->_F)];
}


int main()
{
	Queue q;
	QueueInit(&q);

	Enqueue(&q, 1);
	Enqueue(&q, 2);
	Enqueue(&q, 3);
	Enqueue(&q, 4);


	while (!QIsEmpty(&q))
		cout << Dequeue(&q) << endl;

	return 0;
}

 

 

---

3. 큐의 연결 리스트 기반 구현

 

 

스택과 큐의 유일한 차이점이 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니, 
이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하 면 큐가 될 것 같다

 

▣ 연결 리스트 기반 큐의 구현: Init

//구조체 정의
typedef struct _node
{
	Data data;
	struct _node * next;
}Node;

typedef struct _cQueue
{
	Node* _F;
	Node* _R;

} LQueue;

typedef LQueue Queue;

 

int QIsEmpty(Queue * pq)
{
	if (pq->_F == NULL)
		return true;
	else
		return false;
}

void QueueInit(Queue * pq)
{
	pq->_F = 0;
	pq->_R = 0;
}

 

 

▣  연결 리스트 기반 큐의 구현: enqueue

enqueue 과정

 

void Enqueue(Queue * pq, Data data)
{
	Node* newNode = new Node;
	
	newNode->next = NULL;
	newNode->data = data;

	if (QIsEmpty(pq))
	{
		pq->_F = newNode;
		pq->_R = newNode;
	}
	else 
	{
		pq->_R->next = newNode;
		pq->_R = newNode;

	}
}

 

 

▣  연결 리스트 기반 큐의 구현: dequeue

 

F가 다음 노드를 가리키게 하고, F가 이전에 가리키던 노드를 소멸시킨 결과

 

 

또 F가 다음 노드를 가리키게 하고, F가 이전에 가리키던 노드를 소멸시킨 결과

 

R은 그냥 내버려 둔다
그래야 dequeue의 흐름을 하나로 유지할 수 있다
그리고 R은 그냥 내버려 두어도 된다

 

 

dequeue 사용시 F를 이동한다

 

Data Dequeue(Queue * pq)
{
	Node* delNode;  //삭제할 노드를 저장할 노드
	Data rData;     //반환할 데이터

	
	if (QIsEmpty(pq))
	{
		cout << "Dequeue Error"<<endl;
	}
	//삭제하기 전에 데이터를 저장한다
	delNode = pq->_F;
	rData = pq->_F->data;

	
	pq->_F = pq->_F->next;
	delete delNode;

	return rData;
}

 

Data QPeek(Queue * pq)
{
	if (QIsEmpty(pq))
	{
		cout << "Error" << endl;
	}

	return pq->_F->data;
}


int main()
{
	Queue q;
	QueueInit(&q);

	Enqueue(&q, 1);
	Enqueue(&q, 2);
	Enqueue(&q, 3);
	Enqueue(&q, 4);


	while (!QIsEmpty(&q))
		cout << Dequeue(&q) << endl;

	return 0;
}