[자료구조] 큐(Queue)

큐(Queue)

: FIFO(First In First Out) 구조로, 먼저 들어온 데이터가 먼저 나가는 자료구조이다.

 

선형 큐의 문제점

• 사용하며 front, rear 값이 계속 증가하여 앞부분이 비어있음에도 불구하고 더 이상 삽입이 불가능한 경우가 생긴다.
• 위와 같은 공간 낭비가 이루어 진다.
• 위의 문제를 해결하기 위해 요소를 계속 이동시켜 줄 수도 있지만 비효율적이다.
• 해결방법 : 원형 큐를 구현해 사용하자.

 

변수

#define MAX_SIZE 10
typedef int element;
typedef struct {
	element queue[MAX_SIZE];
	int front;
	int rear;
}QueueType;​

front : 첫 번째 요소의 하나 앞의 인덱스이다. ( 초기값 : 0 )

rear : 마지막 요소의 인덱스 ( 초기값 : 0 )

enqueue는 원소의 삽입

dequeue는 앞의 원소 삭제

왜 front는 첫번째 요소의 하나 앞 인덱스일까?

front와 rear가 같은 인덱스를 가리킬 경우 이것이 비었는지 꽉 찼는지 구분이 안 가기 때문이다.

즉, front가 가리키는 인덱스는 항상 비어있는 상태이다.

 

전체 코드

#include <iostream>
using namespace std;
#define MAX_SIZE 10
typedef int element;
typedef struct {
	element queue[MAX_SIZE];
	int front;
	int rear;
}QueueType;
bool is_Full(QueueType* q)
{
	if ((q->rear + 1)%MAX_SIZE == q->front)
		return true;
	return false;
}
bool is_Empty(QueueType* q)
{
	if (q->front == q->rear)
		return true;
	return false;
}
bool enqueue(QueueType* q, element item) {
	if (is_Full(q))
	{
		cout << "큐가 꽉 찼습니다.\n";
		return false;
	}
	q->rear = (q->rear + 1) % MAX_SIZE;
	q->queue[q->rear] = item;
	return true;
}
element dequeue(QueueType* q) {

	if (is_Empty(q))
	{
		cout << "큐가 비었습니다.\n";
		return -1;
	}
	q->front = (q->front + 1) % MAX_SIZE;
	return q->queue[q->front];
}

int main(void)
{
	QueueType q;
	q.front = 0;
	q.rear = 0;
	for (int i = 1; i <= 11; i++)
	{
		if (enqueue(&q, i))
			cout << i << "를 담았습니다.\n";
		else
			cout << i << "담기 실패\n";
	}

	for (int i = 1; i <= 11; i++)
		cout<<dequeue(&q)<<"\n";

	if (is_Empty(&q))
		cout << "비었습니다.";
}

 

is_Full 함수

bool is_Full(QueueType* q)
{
	if ((q->rear + 1)%MAX_SIZE == q->front)
		return true;
	return false;
}

%MAX_SIZE 를 이용해 원형을 구현하였다 크기가 10인 배열에 9번째 인덱스에서 다음 인덱스로 가면

(9+1)%10 => 0이 된다.

 

is_Empty 함수

bool is_Empty(QueueType* q)
{
	if (q->front == q->rear)
		return true;
	return false;
}

front와 rear가 같은 곳을 가리킨다면 비어있다는 것이다.

 

enqueue 함수

bool enqueue(QueueType* q, element item) {
	if (is_Full(q))
	{
		cout << "큐가 꽉 찼습니다.\n";
		return false;
	}
	q->rear = (q->rear + 1) % MAX_SIZE;
	q->queue[q->rear] = item;
	return true;
}

rear은 현재 마지막 원소를 가리키므로

rear에 1을 더해 거기다 item을 넣어주자.

 

dequeue 함수

element dequeue(QueueType* q) {

	if (is_Empty(q))
	{
		cout << "큐가 비었습니다.\n";
		return -1;
	}
	q->front = (q->front + 1) % MAX_SIZE;
	return q->queue[q->front];
}

현재 front는 맨 앞(첫) 원소의 앞의 인덱스를 가리키므로

front를 +1 해주는 것만으로도 요소의 삭제를 의미할 수 있다.

 

실행할 main문

for (int i = 1; i <= 11; i++)
	{
		if (enqueue(&q, i))
			cout << i << "를 담았습니다.\n";
		else
			cout << i << "담기 실패\n";
	}

	for (int i = 1; i <= 11; i++)
		cout<<dequeue(&q)<<"\n";

	if (is_Empty(&q))
		cout << "비었습니다.";

1부터 11을 q에 삽입을 시도해보자

( 큐의 크기가 10이고 front는 항상 비워져 있어야 하므로 9개만 담을 수 있을 것이다.)

 

그리고 dequeue를 11번 시도해보자

( 1~9가 담겼을 텐데 9번 dequeue를 한 후. 10, 11번째 dequeue는 실패할 것이다. )

 

그리고 큐의 empty를 확인해보자.

( 모두 뺀 상태에서 확인을 하니 비어져있을 것이다. )

 

 

실행 결과