Chap 07. 큐(Queue) [윤성우의 열혈 자료구조]

*본 내용은 [윤성우의 열혈 자료구조] 책과 강의를 보고 공부하면서 요점 정리한 내용입니다.

Chap 07-1: 큐의 이해와 ADT 정의

🔳 큐(Queue)의 이해

• 큐는 먼저 들어간 것이 먼저 나오는, 일종의 줄서기에 비유할 수 있는 자료구조이다.
• 큐는 FIFO(First-in, First-out)구조의 자료구조이다.
• 큐의 기본 연산
  ∙ enqueue: 큐에 데이터를 넣는 연산
  ∙ dequeue: 큐에서 데이터를 꺼내는 연산
• 큐는 운영체제 관점에서 보면 프로세스나 쓰레드의 관리에 활용이 되는 자료구조이다. 이렇듯 운영체제의 구현에도 자료구조가 사용이 된다. 따라서 운영체제의 이해를 위해서는 자료구조에 대한 이해가 선행되어야 한다.

🔳 큐의 ADT 정의

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

• void QueueInit(Queue * pq);
  ∙ 큐의 초기화를 진행한다.
  ∙ 큐 생성 후 제일 먼저 호출되어야 하는 함수이다.

• void QIsEmpty(Queue * pq);
  ∙ 큐가 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

• void Enqueue(Queue * pq, Data data);
  ∙ 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

• Data Dequeue(Queue * pq);
  ∙ 저장순서가 가장 앞선 데이터를 삭제한다.
  ∙ 삭제된 데이터는 반환된다.
  ∙ 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

• Data QPeek(Queue * pq);
  ∙ 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.
  ∙ 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Chap 07-2: 큐의 배열 기반 구현

🔳 큐의 구현 논리

[보편적이고도 올바른 enqueue 연산에 대한 방식]

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

[보편적이고도 올바른 dequeue 연산에 대한 방식]

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

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

• 분명 배열은 비어있다. 하지만 R을 오른쪽으로 한 칸 이동시킬 수 없어서 더 이상 데이터를 추가할 수 없다!
• 데이터를 더 추가하기 위해서는 R을 인덱스가 0인 위치로 이동시켜야 한다.
  그리고 이러한 방식으로 문제를 해결한 것이 바로 원형 큐이다!

🔳 원형 큐

✔ 원형 큐

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

✔ 원형 큐의 단순한 연산

[원형 큐의 enqueue 연산]

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

[원형 큐의 dequeue 연산]

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

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

• 데이터가 하나 존재할 때 F와 R이 동시에 가리키는 경우(F==R인 경우) 문제점이 발생한다.
• 큐가 완전히 채워졌을 때와 비워졌을 때의 F와 R의 관계가 같아 구분할 수 없다.

✔ 원형 큐의 문제점 해결

• 저장 공간 하나를 잃고 문제점을 해결하자.
• 데이터가 하나 존재하는 경우 F와 R이 같은 위치를 가리켰는데. 초기화 직후에 이 상태가 되게 한다.
• 그냥 하나 비운 상태에서 FULL로 인정한다. 그러면 Empty와 Full의 구분이 가능하다!
• R == F → Empty
  R+1 == F → Full
  
  

🔳 원형 큐의 구현

✔ 실행을 위해 필요한 파일들

• CircularQueue.h
• CircularQueue.c
• CircularQueueMain.c

• 실행 결과
  1 2 3 4 5 // 저장된 순서대로 출력된다.
  

✔ 헤더파일

#define QUE_LEN	100
typedef int Data;

/*** 원형 큐 ***/
typedef struct _cQueue
{
	int front; 		// F
	int rear;		// R
	Data queArr[QUE_LEN];	// 배열
} CQueue;

typedef CQueue Queue;

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);

#endif

✔ Helper Function: NextPosIdx

int NextPosIdx(int pos)
{
	if(pos == QUE_LEN-1) // 배열의 마지막 인덱스 값일 때
		return 0; // 0 반환 (배열의 첫 번째 인덱스 값)
	else
		return pos+1;
}

• 큐의 연산에 의해서 F(front)와 R(rear)이 이동할 때 이동해야 할 위치를 알려주는 함수이다.
• 원형 큐를 완성하게 하는 실질적인 함수이다.
• F 또는 R의 인덱스 값을 전달받아 F나 R이 한 칸 이동했을 때 가지고 있어야 하는 인덱스를 반환한다.

✔ 함수의 정의

void QueueInit(Queue * pq)
{
	pq->front = 0; 
	pq->rear = 0;
    // 0이 아닌 다른 인덱스 값이어도 괜찮다.
}

int QIsEmpty(Queue * pq)
{
	if(pq->front == pq->rear)
		return TRUE;
	else
		return FALSE;
}

• enqueue와 dequeue 모두 rear와 front를 우선 이동시키는 구조이다.

void Enqueue(Queue * pq, Data data)
{ // rear을 이동시키고(NextPosIdx 함수의 호출을 통해), 그 위치에 데이터 저장
	if(NextPosIdx(pq->rear) == pq->front) // R+1 == F인 경우(full인경우)
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	pq->rear = NextPosIdx(pq->rear); // R++
	pq->queArr[pq->rear] = data; // 데이터 저장
}

Data Dequeue(Queue * pq)
{ // front를 이동시키고(NextPosIdx 함수의 호출을 통해), 그 위치의 데이터 반환
	if(QIsEmpty(pq)) // 비어있는 경우
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	pq->front = NextPosIdx(pq->front); // F++
	return pq->queArr[pq->front]; // 데이터 반환
    // 굳이 데이터를 삭제할 필요는 없다.

}

Data QPeek(Queue * pq)
{
	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	return pq->queArr[NextPosIdx(pq->front)];
}

✔ main 함수

int main(void)
{
	// Queue의 생성 및 초기화 ///////
	Queue q;
	QueueInit(&q);

	// 데이터 넣기 ///////
	Enqueue(&q, 1);  Enqueue(&q, 2);
	Enqueue(&q, 3);  Enqueue(&q, 4);
	Enqueue(&q, 5);

	// 데이터 꺼내기 ///////
	while(!QIsEmpty(&q))
		printf("%d ", Dequeue(&q)); 

	return 0;
}

Chap 07-3: 큐의 연결 리스트 기반 구현

🔳 연결 리스트 기반 큐의 구현

✔ 실행을 위해 필요한 파일들

• ListBaseQueue.h
• ListBaseQueue.c
• ListBaseQueueMain.c

• 실행 결과
  1 2 3 4 5
  

✔ 헤더파일

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
} Node;

typedef struct _lQueue
{
	Node * front;	// F (삭제 위해)
	Node * rear;	// R (삽입 위해)
} LQueue;

typedef LQueue Queue;

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);

void Enqueue(Queue * pq, Data data);
Data Dequeue(Queue * pq);
Data QPeek(Queue * pq);

• 배열 기반의 구현보다 연결 리스트 기반의 구현에서 논의할 내용이 더 적다!
• 연결 리스트 기반 큐의 경우, 스택과 큐의 유리한 차이점이 앞에서 꺼내느냐 뒤에서 꺼내느냐에 있으니, 이전에 구현해 놓은 스택을 대상으로 꺼내는 방법만 조금 변경하면 큐가 될 것.

✔ 초기화

void QueueInit(Queue * pq)
{
	pq->front = NULL;
	pq->rear = NULL;
}

int QIsEmpty(Queue * pq)
{
	if(pq->front == NULL)
		return TRUE;
	else
		return FALSE;
}

• F만을 가지고 empty를 판단한다.
• why? F만으로 empty 판단이 충분히 가능한데다 마지막 원소를 Dequeue할 때 F = NULL을 만들어 줄 때 R = NULL로 만들어 줄 필요가 없기 때문이다. 자세한 건 Dequeue에서 알아보자.

✔ enqueue

• enqueue의 과정은 두 가지로 나뉜다.

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

	if(QIsEmpty(pq)) // 첫 번째 노드 삽입
	{
		pq->front = newNode;
		pq->rear = newNode;
	}
	else // 두 번째 이후 노드 삽입
	{
		pq->rear->next = newNode;
		pq->rear = newNode;
	}
}

✔ dequeue

Data Dequeue(Queue * pq)
{
	Node * delNode;
	Data retData;

	if(QIsEmpty(pq))
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	// 백업
	delNode = pq->front;
	retData = delNode->data;
    // 이동
	pq->front = pq->front->next;

	free(delNode); // 삭제
	return retData;
}

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

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

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

✔ main 함수

#include <stdio.h>
#include "ListBaseQueue.h"

int main(void)
{
	// Queue의 생성 및 초기화 ///////
	Queue q;
	QueueInit(&q);

	// 데이터 넣기 ///////
	Enqueue(&q, 1);  Enqueue(&q, 2);
	Enqueue(&q, 3);  Enqueue(&q, 4);
	Enqueue(&q, 5);

	// 데이터 꺼내기 ///////
	while(!QIsEmpty(&q))
		printf("%d ", Dequeue(&q)); 

	return 0;
}

Chap 07-4: 큐의 활용

🔳 시뮬레이션

• 시뮬레이션 할 상황.
  햄버거가게에서 대기실(큐)의 크기를 결정하는데 필요한 정보를 추출하는 것이 목적!

• 시뮬레이션을 통해서 추출된 정보의 형태
  ∙ 수용인원이 30명인 공간 - 안정적으로 고객을 수용할 확률 50%
  ∙ 수용인원이 50명인 공간 - 안정적으로 고객을 수용할 확률 70%
  ∙ 수용인원이 100명인 공간 - 안정적으로 고객을 수용할 확률 90%
  ∙ 수용인원이 200명인 공간 - 안정적으로 고객을 수용할 확률 100%

• 점심시간은 1시간이고 그 동안 고객은 15초에 1명씩 주문을 하는 것으로 간주한다.
• 한 명의 고객은 하나의 버거만을 주문한다고 가정한다.
• 주문하는 메뉴에는 가중치를 두지 않는다. 모든 고객은 무작위로 메뉴를 선택한다.
• 햄버거를 만드는 사람은 1명이다. 그리고 동시에 둘 이상의 버거가 만들어지지 않는다.
• 주문할 메뉴를 받을 다음 고객은 대기실에서 나와서 대기한다.

• 종류별 햄버거를 만드는데 걸리는 시간은 다음과 같다.
  ∙ 치즈버거 12초
  ∙ 불고기버거 15초
  ∙ 더블버거 24초

• CircularQueue.h
  CircularQueue.c
  HamburgerSim.c

• 실행 결과 1

Simulation Report!
- Cheese burger: 80
- Bulgogi berger: 72
- Double burger: 88
- Waiting room size: 100 // 큐 사이즈

• 실행 결과 2

Queue Memorry Error!

Chap 07-5: 덱(Deque)의 이해와 구현

🔳 덱의 이해와 ADT

✔ 덱의 이해

• 덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조

• 덱의 4가지 연산
  ∙ 앞으로 넣기
  ∙ 앞에서 빼기
  ∙ 뒤로 넣기
  ∙ 뒤에서 빼기

• Deque는 double ended queue의 줄인 표현으로, 양쪽 방향으로 모두 입출력이 가능함을 의미한다. 그리고 스택과 큐의 특성을 모두 지니고 있다고도 말한다. 덱을 스택으로도 큐로도 활용할 수 있기 때문이다.

✔ 덱의 ADT

• void DequeInit(Deque * pdeq);
  ∙ 덱의 초기화를 진행한다.
  ∙ 덱 생성 후 제일 먼저 호출되어야 하는 함수이다.

• int DQIsEmpty(Deque * pdeq);
  ∙ 덱이 빈 경우 TRUE(1)을, 그렇지 않은 경우 FALSE(0)을 반환한다.

• void DQAddFirst(Deque * pdeq, Data data); // 앞으로 넣기
  ∙ 덱의 머리에 데이터를 저장한다. data로 전달된 값을 저장한다.

• void DQAddLast(Deque * pdeq, Data data); // 뒤로 넣기
  ∙ 덱의 꼬리에 데이터를 저장한다. data로 전달된 값을 저장한다.

• Data DQRemoveFirst(Deque * pdeq); // 앞에서 빼기
  ∙ 덱의 머리에 위치한 데이터를 반환 및 소멸한다.

• Data DQRemoveLast(Deque * pdeq); // 뒤로 빼기
  ∙ 덱의 꼬리에 위치한 데이터를 반환 및 소멸한다.

• Data DQGetFirst(Deque * pdeq); // 앞에서 PEEK
  ∙ 덱의 머리에 위치한 데이터를 소멸하지 않고 반환한다.

• Data DQGetLast(Deque * pdeq); // 뒤에서 PEEK
  ∙ 덱의 꼬리에 위치한 데이터를 소멸하지 않고 반환한다.

🔳 덱의 구현

✔ 헤더파일 정의

typedef int Data;

typedef struct _node
{
	Data data;
	struct _node * next;
	struct _node * prev;
} Node;

typedef struct _dlDeque
{
	Node * head;
	Node * tail;
} DLDeque;

typedef DLDeque Deque;

void DequeInit(Deque * pdeq);
int DQIsEmpty(Deque * pdeq);

void DQAddFirst(Deque * pdeq, Data data);
void DQAddLast(Deque * pdeq, Data data);

Data DQRemoveFirst(Deque * pdeq);
Data DQRemoveLast(Deque * pdeq);

Data DQGetFirst(Deque * pdeq);
Data DQGetLast(Deque * pdeq);

• 덱의 구현에 가장 어울리는 자료구조는 양방향 연결 리스트이다. (삭제시 앞 뒤의 노드를 알기 유용하므로)
• 앞과 뒤로 입출력 연산이 이뤄지기 때문에 head뿐만 아니라 tail도 정의되어야 한다.

✔ 함수의 정의

• 이전에 구현한 양방향 연결 리스트와의 차이점은 tail의 존재 유무가 전부이다.