4. 큐 (Queue)

큐 역시 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조이다.

스택과의 다른 점이라함은, 선입선출 (First in, First out) 형태를 지닌다는 점이다.

 

큐에 데이터를 넣는 작업을 인큐(enqueue)라 하고, 데이터를 꺼내는 작업을 디큐(dequeue)라고 한다.

데이터를 꺼내는 쪽을 프론트(Front), 넣는 쪽을 리어(rear)라고 한다.

출처 : https://velog.io/@pa324

 

큐 역시 배열로 구현이 가능하다.

19		19		22
22		22		37
37		37		53
53		53		24
		24

1) que[0] ~ que[3] 까지 데이터가 저장되어 있다.

2) 24를 인큐한다. que[3]의 데이터 다음인 que[4] 에 24를 저장. 이 때 시간 복잡도는 O(1)

3) 19를 디큐한다. que[0]에 저장된 19를 꺼낸 다음, 모든 요소들을 한 칸씩 옮긴다. 이 때 시간 복잡도는 O(n)

 

 

선형 큐의 단점을 보완한 것이 원형 큐이다.

 

출처 : https://yonssa.tistory.com/

큐의 front와 rear를 연결시켜, 원형 구조를 나타내는 형태이다.

Rear = (Rear+1) % QueueSize

Front = (Front +1) % QueueSize

이제 큐를 코드로 구현해보자.

typedef struct
{
	int max; // 큐 최대 용량
	int num; // 현재의 요소 개수
	int front; // 프론트
	int rear; //리어
	int* que; // 큐의 맨 앞 요소에 대한 포인터
}IntQueue;

먼저 큐를 관리하는 구조체이다.

큐로 사용할 배열, 최대용량, 프런트, 리어, 현재 데이터 개수로 구성되어 있다.

 

1. 초기화

int Initialize(IntQueue* q, int max)
{
	q->num = q->front = q->rear = 0; // 프론트와 리어가 같아야 하며 둘 다 0이어야 큐가 비어있음
	if ((q->que = (int*)calloc(max, sizeof(int)) == NULL))
	{	
    	// 큐 생성 실패
		q->max = 0;
		return -1;
	}
	q->max = max;
	return 0;
}

메모리 공간 확보를 위한 작업으로서, 큐를 처음 만들면 큐는 비어있으므로, num, front, rear 값을 모두 0으로 한다.

그리고 최대 용량 max를 매개변수로 받아 큐의 max에 저장함에 따라 메모리 공간을 확보한다.

 

2. 인큐

int Enque(IntQueue* q, int x)
{
	if (q->num >= q->max)
		return -1;
	else
	{
		q->num++;
		q->que[q->rear++] = x;
		if (q->rear == q->max)
		{
			q->rear = 0;
		}
	}
	return 0;
}

큐에 데이터가 가득 차면, -1을 반환한다.

인큐 동작 시, 원소 x를 넣고, rear를 증가 시키고, 원소 개수 num 변수를 증가시킨다.

그리고 리어 값이 max와 같아지면 안되므로, 이를 방지하기 위해, 같은 경우 rear를 0번 인덱스로 옮겨준다.

 

3. 디큐

int Deque(IntQueue* q, int* x)
{
	if (q->num <= 0)
		return -1;
	else
	{
		q->num--;
		*x = q->que[q->front++];
		if (q->front == q->max)
		{
			q->front = 0;
		}
	}
	return 0;
}

원소 개수가 0이되면 큐 내부가 빈 상태임에 따라 -1을 반환한다.

그리고 디큐를 하면, 프론트에서 원소를 빼내는 것으로, 원소 개수를 줄이고, 프론트 위치도 한 칸 증가시킨다.

즉 , 큐 내부에 1, 2, 3이 있을 때, 1을 디큐하면 프론트는 2를 가리키므로, 프론트의 인덱스가 0에서 1로 바뀐다.

 

그 외의 함수 구현은 아래와 같다.

int Peek(const IntQueue* q, int* x)
{
	if (q->num <= 0)
	{
		return -1;
	}
	*x = q->que[q->front];
	return 0;

}

void Clear(IntQueue* q)
{
	q->num = q->front = q->rear = 0;
}

int Capacity(const IntQueue* q)
{
	return q->max;
}

int Size(const IntQueue* q)
{
	return q->num;
}

int IsEmpty(const IntQueue* q)
{
	return q->num <= 0;
}

int IsFull(const IntQueue* q)
{
	return q->num >= q->max;
}

int Search(const IntQueue* q, int x)
{
	int i, idx;
	for (i = 0; i < q->num; i++)
	{
		if (q->que[idx = (i + q->front) % q->max] == x)
			return idx;
	}
	return -1;
}

void Print(const IntQueue* q)
{
	int i;
	for (i = 0; i < q->num; i++)
	{
		printf("%d", q->que[(i + q->front) % q->max]);
	}
	putchar('\n');

}

void Terminate(IntQueue* q)
{
	if (q->que != NULL)
		free(q->que);
	q->max = q->num = q->front = q->rear = 0;
}

이제 위의 함수들을 가지고 예제를 작성해보자.

int main(void)
{
	IntQueue que;

	if (Initialize(&que, 64) == -1)
	{
		puts("큐 생성에 실패하였습니다.");
		return 1;
	}
	while (1)
	{
		int m, x;

		printf("현재 데이터 수 : %d / %d \n", Size(&que), Capacity(&que));
		printf("(1)인큐 (2)디큐 (3)피크 (4)출력 (0)종료 :");
		scanf("%d", &m);

		if (m == 0) break;
		switch (m)
		{
		case 1:
			printf("데이터 : ");
			scanf("%d", &x);
			if (Enque(&que, x) == -1)
				puts("\a오류 : 인큐에 실패하였습니다.");
			break;

		case 2:
			if (Deque(&que, &x) == -1)
				puts("\a오류 : 디큐에 실패하였습니다.");
			else
				printf("디큐한 데이터는 %d입니다.\n", x);
			break;

		case 3:
			if (Peek(&que, &x) == -1)
				puts("\a오류 : 피크에 실패하였습니다.");
			else
				printf("피크한 데이터는 %d입니다.\n", x);
			break;

		case 4:
			Print(&que);
			break;
		}
	}
	Terminate(&que);
	return 0;

}