[자료구조] 큐(Queue)

선입 선출의 자료구조.

 

[큐의 종류]

 

• 배열을 기반으로 구현된 큐
• 리스트를 기반으로 구현된 큐

 

 

[배열을 기반으로 구현된 큐] = 원형 큐

 

※ 스택과 큐는 차이가 별로 없어보이지만 구현방법에는 차이가 크다 !

 

▶ ADT 

필요한 기능 : 큐 초기화, 큐 비었는지 확인, 큐에 데이터 넣기, 큐에서 데이터 꺼내기, 다음에 나올 데이터 들여다보기

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);
void Enqueue(Queue * pq, Data data); //데이터 삽입
Data Dequeue(Queue * pq); //데이터 삭제
Data QPeek(Queue * pq);

 

▶ 배열을 기반으로 구현된 리스트의 문제점

★ 위 그림에서 front의 index를 1씩 더하여 Dequeue 하고 rear을 참조하여 Enqueue 한다

문제점 : 배열의 끝에 너무 빨리 도달하게 된다 ! 

→ 해결 : 데이터의 출입이 반복되면 앞부분은 비어 있기 때문에 R을 앞부분으로 이동시킨다 = 원형 큐 구현!!

 

▶ 원형 큐란?

<특징>

• 배열을 꽉 채우면 front와 rear를 가지고 텅빈 경우와 꽉 찬 경우를 구분할수 없으므로 배열을 한칸 남겨둔다.
• Enqueue 연산 시 rear가 가리키는 위치를 한 칸 이동시킨 다음에 rear가 가리키는 위치에 데이터를 저장한다.
• Dequeue 연산 시 front가 가리키는 위치를 한 칸 이동시킨 다음에 front가 가리키는 위치에 저장된 데이터를 삭제한다.

원형 큐가 꽉찬 경우 : rear가 가리키는 위치의 앞을 front가 가리킨다

원형 큐가 텅빈 경우 : 초기 상태와 같이 front 와 rear가 동일한 위치를 가리킨다

 

▶ 구현

 

• 원형 큐를 의미하는 구조체 - 그림의 front, rear, 값을 저장할 배열

typedef struct _cQueue
{
	int front;
	int rear;
	Data queArr[100];
} CQueue;

• 원형 큐의 핵심 함수 -> 큐의 다음 위치에 해당하는 배열의 인덱스 값을 반환하는 함수 (front와 rear의 회전을 돕는다)

int NextPosIdx (int pos)
{
    if(pos == 99) // 끝에 도달하면
    	return 0; // 처음으로 돌아간다
    else
    	return pos+1;

 

• ADT의 구현

void QueueInit(Queue * pq) //큐 초기화
{
	pq->front = 0;
	pq->rear = 0;
}

int QIsEmpty(Queue * pq) 
{
	if(pq->front == pq->rear) //큐 비어 있으면 front rear 위치 같음
		return TRUE;
	else
		return FALSE;
}

int NextPosIdx(int pos) // 가장 중요한 함수
{
	if(pos == QUE_LEN-1)
		return 0;
	else
		return pos+1;
}

void Enqueue(Queue * pq, Data data)
{
	if(NextPosIdx(pq->rear) == pq->front) //큐가 꽉찬경우
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

	pq->rear = NextPosIdx(pq->rear);
	pq->queArr[pq->rear] = data;
}

Data Dequeue(Queue * pq)
{
	if(QIsEmpty(pq))//큐가 빈경우
	{
		printf("Queue Memory Error!");
		exit(-1);
	}

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

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

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

 

<특징>

Enqueue

→ rear 값을 먼저 한칸 옮기고 데이터를 삽입한다

Dequeue

→ front 값을 먼저 한칸 옮기고 데이터를 삭제한다

QIsEmpty

→ 데이터가 비어 있으면 rear 값과 front 값이 같고, 데이터가 꽉 차있으면 front값이 rear값보다 한칸 앞서있다

 

---

[연결리스트를 기반으로 구현된 큐] 

 

※ 배열기반 큐는 스택과 큐의 구현차이가 컸지만 연결리스트 기반 큐는 스택과 큐의 구현차이가 적다

 

▶ ADT 

필요한 기능 : 큐 초기화, 큐 비었는지 확인, 큐에 데이터 넣기, 큐에서 데이터 꺼내기, 다음에 나올 데이터 들여다보기

void QueueInit(Queue * pq);
int QIsEmpty(Queue * pq);
void Enqueue(Queue * pq, Data data); //데이터 삽입
Data Dequeue(Queue * pq); //데이터 삭제
Data QPeek(Queue * pq);

▶ 구현 목표

 

▶ 구현

 

• 원형 큐를 의미하는 구조체 - 맨 앞과 맨 뒤를 가리킴

typedef struct _lQueue
{
	Node * front;
	Node * rear;
} LQueue;

 

• ADT의 구현

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

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

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; //rear를 새로운 노드로 옮김
	}
}

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; //맨 마지막 데이터 삭제의 경우 pq->front->next가 null임
	free(delNode);
	return retData;
}

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

	return pq->front->data;
}

 

<특징>

Enqueue

→ 큐가 비어있지 않으면 맨 마지막 데이터의 next에 새로운 노드를 연결하고 rear를 새로운 노드로 바꿈

Dequeue

→  front를 한칸 뒤로 댕기고 그 전에 front 였던걸 삭제함 ( 여기서 맨 마지막 데이터를 삭제하는 경우 맨 마지막 데이터의 next는 null이므로 front에 null이 저장됨

 

▶ 시뮬레이션에서 사용되는 큐

시뮬레이션 : 특정 상황에 놓인 복잡한 문제의 해결을 위해서 실제와 비슷한 상황을 연출하는것

시뮬레이션이라는 주제에서 큐가 자주 활용됨