큐(queue)에 대해서

Steve Jack·2021년 8월 11일
자료구조 알고리즘(C)
0

자료구조 알고리즘(C)

목록 보기
4/20
post-thumbnail
post-custom-banner

큐란?

큐(queue)는 스택과 마찬가지로 테이터를 일시적으로 쌓아 두기 위한 자료구조입니다.

  • 데이터의 입력과 출력 순서 : 선입선출(FIFO) 구조
  • 큐 활용 예시 : 프린터의 인쇄 대기열, 은행 업무

배열에서 큐

  • enque : 데이터를 넣는 작업
  • deque : 데이터를 꺼내는 작업
  • front : 데이터를 꺼내는 쪽
  • rear : 데이터를 넣는 쪽

  1. enque
  • 데이터 24를 rear에 enque합니다.
  • 시간 복잡도는 O(1) 이며, 적은 비용으로 구현가능합니다.
  1. deque
  • 데이터 22를 front에서 deque합니다.
  • deque 후에 deque한 위치 다음 요소들을 모두 맨 앞으로 옮여야 하므로 시간 복잡도는 O(n)입니다. 데이터를 꺼낼때 마다 효율이 떨어집니다.

링 버퍼로 큐 구현

이번에는 배열 요소를 앞쪽으로 옮기지 않는 큐를 구현해 보겠습니다.
이를 위해 사용하는 자료구조가 링 버퍼(ring buffer)입니다. 링 버퍼는 아래의 그림처럼 배열의 처음이 끝과 연결되었다고 보는 자료구조입니다. 어떤 요소가 첫 번째요이고 마지막 요소인지 식별하기 위한 변수가 front와 rear입니다.

  • front : 맨 처음 요소의 인텍스
  • rear : 맨 끝 요소이 하나 뒤의 인덱스(다음 요소를 enque할 위치를 미리 지정)

그림 A

  • 5개의 데이터 22, 37, 15, 26, 49가 차레대로 저장됩니다.
  • front는 5 이고, rear는 2입니다.

그림 B

  • 25를 rear에 enque한 후 rear를 1증가시킵니다.

그림 C

  • front에 22를 deque하고 front를 1증가시킵니다.

이렇게 큐를 front와 rear를 업데이트를 하며 enque와 deque를 실행하면 앞에서 발생한 배열의 요소 이동 문제를 해결할 수 있습니다.


링버퍼로 큐를 구현하는 프로그램

좀 더 자세히 링버퍼로 큐를 구현하여봅시다.

아래는 IntQueue.h 소스파일입니다.

/* int형 큐 IntQueue.h(헤더) */
#ifndef ___IntQueue
#define ___IntQueue

/*--- 큐를 구현하는 구조체 ---*/
typedef struct {
	int max;	/* 큐의 최대 용량 */
	int num;	/* 현재 요소의 개수 */
	int front;	/* 프런트 */
	int rear;	/* 리어 */
	int *que;	/* 큐의 첫 요소에 대한 포인터 */
} IntQueue;

/*--- 큐 초기화 ---*/
int Initialize(IntQueue *q, int max);

/*--- 큐에 데이터를 인큐 ---*/
int Enque(IntQueue *q, int x);

/*--- 큐에서 데이터를 디큐 ---*/
int Deque(IntQueue *q, int *x);

/*--- 큐에서 데이터를 피크 ---*/
int Peek(const IntQueue *q, int *x);

/*--- 모든 데이터를 삭제 ---*/
void Clear(IntQueue *q);

/*--- 큐의 최대 용량 ---*/
int Capacity(const IntQueue *q);

/*--- 큐에 저장된 데이터의 개수 ---*/
int Size(const IntQueue *q);

/*--- 큐가 비어 있는가? ---*/
int IsEmpty(const IntQueue *q);

/*--- 큐가 가득 찼는가? ---*/
int IsFull(const IntQueue *q);

/*--- 큐에서 검색(요소 인덱스) ---*/
int Search(const IntQueue *q, int x);

/*--- 큐에서 검색(요소 맨 앞 요소부터 몇번째 값) ---*/
int Search2(const IntQueue* q, int x);

/*--- 모든 데이터 출력 ---*/
void Print(const IntQueue *q);

/*--- 큐 종료 ---*/
void Terminate(IntQueue *q);
#endif

  • 큐 구조체 IntQueue : 큐를 관리하는 구조체

  1. 큐로 사용할 배열을 가리키는 포인터 : que
    enque하는 데이터를 저장하기 위한 큐로, 사용할 배열의 첫 번째 요소에 대한 포인터입니다.

  2. 큐의 최대 용량 : max
    큐의 최대 용량을 저장하는 멤버로, 이값은 배열 que에 저장할 수 있는 최대 요소의 개수와 같습니다.

  3. front
    enque한 데이터 가운데 첫 번째 요소의 인덱스 저장한 멤버입니다.

  4. rear
    enque한 데이터 가운데 맨 나중에 저장한 요소의 하나 뒤의 인덱스를 저장한 멤버입니다.

  5. 현재 데이터 개수 : num
    큐에 쌓아 놓은 데이터 수를 나타내는 멤버입니다. front와 rear는 enque와 deque에 하면서 업데이트 되어 매번 값이 달라집니다. front와 rear 만으로는 큐가 비어있는지 가득 찼는지 구별할 수 없는 상황입니다. num은 0일때 비어있고, max값과 같을때 가득 차있습니다.


아래는 IntQueue.c 소스파일입니다.

/* int형 큐 IntQueue(소스) */
#include <stdio.h>
#include <stdlib.h>
#include "IntQueue.h"

/*--- 큐 초기화 ---*/
int Initialize(IntQueue *q, int max)
{
	q->num = q->front = q->rear = 0;
	if ((q->que = calloc(max, sizeof(int))) == NULL) {
		q->max = 0;			/* 배열 생성에 실패 */
		return -1;
	}
	q->max = max;
	return 0;
}

/*--- 큐에 데이터를 인큐 ---*/
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;
	}
}

/*--- 큐에서 데이터를 디큐 ---*/
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;
	}
}

/*--- 큐에서 데이터를 피크 ---*/
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;				/* 검색 실패 */
}

/*--- 큐에서 검색(요소 맨 앞 요소부터 몇번째 값) ---*/
int Search2(const IntQueue* q, int x)
{
	int i;

	for (i = 0; i < q->num; i++) {
		if (q->que[(i + q->front) % q->max] == x) // i : 맨 앞 요소로부터 몇번째 위치에 있는 값
			return i;		/* 검색 성공 */
	}
	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;
}

* 큐관련 함수 만들기

  1. 초기화 함수 : Initialize
    큐를 구현하기 위한 배열의 메모리 공간 확보 등의 준비하는 작업을 하는 함수입니다. 큐에는 비어 있으므로 num, front, rear 모두 0으로 해줍니다. 또한 max로 큐의 최대용량을 받아 max에 저장하여 que의 메모리 공간을 확보합니다.

  2. 데이터 인큐 함수 : Enque
    큐에 데이터를 인큐하는 함수입니다. 인큐에 성공하면 0을 반환하고 큐에 가득차서 인큐할 수 없으면 -1을 반환합니다. 인큐에 성공하면 rear와 num의 값을 1씩 증가시킵니다. rear가 max와 같아지는 시접에는 배열의 처음으로 가야하기 때문에 rear를 0으로 번경해줍니다.

  3. 데이터 디큐 함수 : Deque
    큐에 데이터를 디큐하는 함수입니다. 디큐에 성곤하면 0을 반환하고 큐가 비어있다면 -1을 반환합니다. 디큐에 성공하면 front 값을 1만큼 증가하고 num 값을 1만큼 감소합니다. Enque 함수와 마찬가지로 front가 max값과 같아지면 배열의 처음으로 가야하기 때문에 front를 0으로 변경해줍니다.

  4. 맨 앞의 데이터를 몰래 엿보는 함수 : Peek
    que[front]의 값을 출력만 합니다. 피크성공하면 0을 반환하고 실패하면 -1을 반환합니다.

  5. 모든 데이터를 삭제하는 함수 : Clear
    num, front, rear을 0으로 만들어 줍니다.

  6. 최대 용량을 확인하는 함수 : Capacity
    max값을 반환해줍니다.

  7. 데이터 개수를 확인하는 함수 : Size
    num값을 반환해줍니다.

  8. 큐가 비어있는지 판단하는 함수 : IsEmpty
    num이 0보다 판단한 후 작으면 1, 크면 0을 반환해줍니다.

  9. 큐가 가득 찼는지 판단하는 함수 : IsFull
    num이 max값과 같거나 큰 경우 1, 아니라면 0을 반환해줍니다.

  10. 검색 함수 : Search
    큐의 배열에서 x와 같은 데이터가 저장되어 있는 인덱스를 반환하는 함수입니다. 배열의 첫 요소가 아닌 큐의 첫 요소붙 선형 검색을 수행합니다. 현재 검색하는 위치의 인덱스를 구하는 식은 (i + q->front) % q->max입니다. front 부터 시작해서 인댁스를 증가시켜 찾습니다. 큐의 크기로 나눠주어 front에서 시작해도 인덱스를 벗어 나지 않게 구현해줍니다.

  11. 검색 함수 : Search2
    큐이 맨 앞의 요소로부터 상대적으로 몇 번째 위치에 있는지에 대한 인덱스 값을 반환합니다. 검색요소에 대해 front에서 i만큼 떨어진 확인하여 i를 반환합니다. 검색에 실패할 경우에는 -1을 반환합니다.

  12. 모든 데이터를 출력하는 함수 : Print
    Search 함수와 마찬가지로 큐의 첫 요소부터 끝까지 출력해줍니다.

  13. 종료함수 : Terminate
    큐가 메모리가 할당되어 있으면 메모리를 해제하고 모든 멤버를 0으로 만듭니다.


아래는 IntQueueTest.c 소스파일입니다.

/* int형 큐 IntQueue를 사용하는 프로그램 */
#pragma warning (disable:4996)
#include <stdio.h>
#include "IntQueue.h"

int main(void)
{
	IntQueue que;

	if (Initialize(&que, 64) == -1) {
		puts("큐의 생성에 실패했습니다.");
		return 1;
	}

	while (1) {
		int m, x;
		int idx;

		printf("현재 데이터의 수：%d / %d\n", Size(&que), Capacity(&que));
		printf("(1)인큐 (2)디큐 (3)피크 (4)출력 (5)검색 (6)클리어 (7)빈 상태 / 가득 찬 상태 (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;

		case 5: /*--- 검색 ---*/
			printf("검색 데이터：");
			scanf("%d", &x);
			if ((idx = Search(&que, x)) == -1)
				puts("\a오류 : 검색에 실패했습니다.");
			else {
				printf("데이터는 인덱스 %d 위치에 있습니다.\n", idx);
				printf("큐의 맨 앞의 요소에서 %d 만큼 뒤에 있습니다.\n", Search2(&que, x));
			}
			break;

		case 6: /*--- 모든 데이터 삭제 ---*/
			Clear(&que);
			break;

		case 7: /*--- 비어 있는지 판단 ---*/
			printf("큐가 비어 있%s.\n", IsEmpty(&que) ? "습니다" : "지 않습니다");
			printf("큐가 가득 %s.\n", IsFull(&que) ? "찼습니다" : "차지 않았습니다");
			break;
		}
	}

	Terminate(&que);

	return 0;
}


링 버퍼의 활용

링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있습니다. 예를 들어 배열 크기가 n인 배열이 있습니다. 계속해서 인큐를 하여 데이터가 n개가 넘어도 가장 최근에 들어온 n개만 저장하는 것입니다. 아래의 코드를 살펴봅시다.

#pragma warning (disable:4996)
#include <stdio.h>

#define N 10

int main() {
	int i;
	int a[N]; // 데이터를 저장할 배열
	int cnt = 0; // 입력한 데이터의 개수
	int retry; // 다시 시도 ?
	puts("정수를 입력하세요.");
	do {
		printf("%d번째 정수 : ", cnt + 1);
		scanf("%d", &a[cnt++ % N]); // 배열 크기 벗어나도 계속 입력
		printf("계속할까요?(Yes 1/No 0 : )");
		scanf("%d", &retry); 
	} while (retry == 1); 
	i = cnt - N; // 데이터 개수와 배열 크기의 차
	if (i < 0) i = 0; // 입력한 데이터 개수가 배열 크기보다 작을 경우
	for (; i < cnt; i++)
		printf("%2d 번째 정순 = %d\n", i + 1, a[i % N]);
	return 0;
}

아래는 정수 12개를 입력의 예입니다.
11, 15, 9, 25, 68, 34, 22, 55, 31, 12, 6, 23
위 코드에서 배열의 크기가 10이므로 가장 오래전에 입력된 11, 15는 벼려지고 그자리에 새로운 값들이 차례대로 입력됩니다.

  • cnt : 데이터 입력 개수를 저장할 cnt를 선언해줍니다. 입력된 데이터가 몇번째 정수인지 확인할 수 있도록 합니다.

  • a[cnt++ % N] : 배열의 크기인 N으로 배열 크기를 벗어나도 계속 입력 받을수 있도록합니다. 입력된 값이 링 버퍼(배열)에 순환하여 저장됩니다.

  • i = cnt - N : 데이터 개수와 배열 크기의 차로 i를 N으로 나눈 나머지는 배열의 첫번째 요소(디큐할 위치)입니다.

  • if (i < 0) i = 0 : 배열 크기를 초과하지 않을 경우에는 i를 배열의 시작인 0으로 변경합니다.

  • for (; i < cnt; i++) : 배열의 첫번째 요소부터 가장 최근에 들어온 값까지 a[i % N]으로 출력합니다.

아래의 결과와 같이 가장 먼저 입력된 11, 15는 버려지고 3번째로 입련된 정수부터 링 버퍼(배열)에 저장되고 있음을 알수 있습니다.

profile
Steve Jack
To put up a flag.
이전 포스트

스택(Stack)에 대해서

다음 포스트

덱(Deque)에 대해서

post-custom-banner

0개의 댓글