[자료구조] queue(큐) (C)

참고 | DO IT C언어 자료구조 입문편

🤷‍♀️ 이번 시간에는 큐에 대해서 알아보겠다.

• 큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 두기 위한 자료구조다.
• 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출 구조를 이루고 있다.
• 대표적인 예시로
  • 은행 창구에서 차례를 기다리는 대기열
  • 마트에서 계산을 기다리는 대기열

📢 배열을 이용해 큐를 구현해보자.

<그림 출처|https://juyeop.tistory.com/13>

위의 그림의 왼쪽은 실제 링 버퍼 큐에서 이루어지는 데이터 입 출력 과정을 표시한 것이다. 프런트의 값부터 순차적으로 데이터가 추가되는 모습을 볼 수 있다. 그림의 오른쪽은 링 버퍼 큐의 모양을 배열 큐 모습으로 변환시켜 놓은 것아다.

링 버퍼 큐는 배열 큐와 달리 데이터가 디큐가 된 후 인덱스 자리를 옮겨줘야 하는 등 불편한 점이 존재하지 않다. 지금까지 배열 큐와 링 버퍼 큐에 대해서 알아보았다. 이 둘은 각기 다른 것이 아닌 큐를 구현하는 모양의 차이다. 대부분의 사람들이 큐를 구현할 때는 배열 모양보다는 링 버퍼 모양으로 큐를 구현하는 것이 보편적이다.

큐를 헤더파일로 선언해보자.

#ifndef __IntQueue
#define __IntQueue

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


int Initialize(IntQueue* q, int max);

int Enque(IntQueue* q, int x);

int Deque(IntQueue* q, int* x);

int Peek(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);

void Prinf(const IntQueue* q);

void Terminate(IntQueue* q);

#endif

Queue Initialize 함수

int Initialize(IntQueue* q, int max) // 초기화 함수 
//큐를 구현하기 위해 배열의 메모리 공간 확보 등의 준비 작업하는 함수.
//큐는 처음 만들면, 큐는 비어 있으므로 num, front, rear 값을 모두 0으로 한다.
{
	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;
}

Queue Enque 함수

int Enque(IntQueue* q, int x) // 큐에 데이터를 인큐하는 함수다.
{
	if (q->num >= q->max)//인큐에 성공하면 0을 반환하지만, 
	{//큐가 가득 차서 인큐할 수 없으면(num >= max) - 1을 반환한다.
		return -1;
	}
	else
	{
		//que[rear]에 데이털 82를 인큐하고 rear와 num 값을 1만큼 증가하면, 인큐 작업이 끝난다.
		//만약 인큐하기 전의 rear 값이 11이면 Enque 함수를 수행한 다음에는 rear값이 12가되면서 max와 같아지는 문제가 발생한다.
		q->num++;
		q->que[++q->rear] = x;
		if (q->rear == q->max)
		{
			q->rear = 0;
		}
		return 0;
	}


}

Queue Deque함수

int Deque(IntQueue* q, int* x)
{
	if (q->num <= 0) // 큐가 비어 있으면 
	{
		return -1;
	}
	else
	{
		q->num--; //num값을 감소시킨다.
		*x = q->que[q->front++]; // 버퍼링을 통해서 Deque를 하게 되면 가장 먼저 앞에 있었던 front가 나가게 되고 front를 증가시킨다.
		if (q->front == q->max)
			q->front = 0;
		return 0;
	}
}

Deque 및 Enque는 두 가지 관점이있다.

• front에서 Deque / Enque 할 경우 & 링 버퍼
• Back에서 Deque 및 Enque 할 경우 & 링 버퍼와 연결지어 생각해야한다. (인덱스 초과 문제가 발생하기 때문에)
• 인덱스 초과 문제를 해결하기 위한 아이디어로
  큐의 front == 큐의 용량(max) 같아지면, front의 값을 배열의 처음인 0으로 변경한다. (rear도 동일하다.)

Queue Search

int Search(const IntQueue* q, int x) // Search의 근본적인 목적은 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;
}

num = 7이고, max 가 11이라고 가정할 떄, que[7], que[8], que[9], que[10], que[11], que[0], que[1]에 값이 있다. que[7]이 front 쪽 que[1]이 rear - 1 이다.

(i+q->front) % q->max라고 한다면,

i : 0 > 1 > 2> 3 > 4 > 5 > 6
idx : 7 > 8 > 9 > 10 > 11 > 0 > 1 이다.

나머지 Queue 함수구현

int Peek(const IntQueue * q, int* x) // que[front] 함수만 확인한다.
{
	if (q->num <= 0)
		return -1;
	
	*x = q->que[q->front]; //Peek 함수자체가 가장 꼭대기에 있는 것을(앞에 있는 것) 보여주기 때문에
	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;

}


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

	}
	putchar('\n');
}

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

}

앞에 Queue를 활용한 프로그램을 만들어보자.

IntQueue.c(main)

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

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)출력 (5)종료 :");
		scanf_s("%d", &m);

		if (m == 0)
		{
			break;
		}
		switch (m)
		{
		case 1:
			printf("데이터 : "); scanf_s("%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);
		}
	}
	Terminata(&que);
	return 0;
}

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(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);

void Prinf(const IntQueue* q);

void Terminata(IntQueue* q);

#endif

queue.c

#include <stdio.h>
#include <stdlib.h>
#include "IntQueue.h"


//typedef struct {
//	int max;
//	int num;
//	int front;
//	int rear;
//	int* que;
//}IntQueue;


int Initialize(IntQueue* q, int max) // 초기화 함수 
//큐를 구현하기 위해 배열의 메모리 공간 확보 등의 준비 작업하는 함수.
//큐는 처음 만들면, 큐는 비어 있으므로 num, front, rear 값을 모두 0으로 한다.
{
	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)//인큐에 성공하면 0을 반환하지만, 
	{//큐가 가득 차서 인큐할 수 없으면(num >= max) - 1을 반환한다.
		return -1;
	}
	else
	{
		//que[rear]에 데이털 82를 인큐하고 rear와 num 값을 1만큼 증가하면, 인큐 작업이 끝난다.
		//만약 인큐하기 전의 rear 값이 11이면 Enque 함수를 수행한 다음에는 rear값이 12가되면서 max와 같아지는 문제가 발생한다.
		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--; //num값을 감소시킨다.
		*x = q->que[q->front++]; // 버퍼링을 통해서 Deque를 하게 되면 가장 먼저 앞에 있었던 front가 나가게 되고 front를 증가시킨다.
		if (q->front == q->max)
			q->front = 0;
		return 0;
	}
}


int Peek(const IntQueue * q, int* x) // que[front] 함수만 확인한다.
{
	if (q->num <= 0)
		return -1;
	
	*x = q->que[q->front]; //Peek 함수자체가 가장 꼭대기에 있는 것을(앞에 있는 것) 보여주기 때문에
	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;

}


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 Terminata(IntQueue* q) 
{
	if (q->que != NULL)
	{
		free(q->que);
	}
	q->max = q->num = q->front = q->rear = 0;

}





int Search(const IntQueue* q, int x) // Search의 근본적인 목적은 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;
}

<결과>

📢 링버퍼에 대하여

• 링버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다.
• 대표적인 예로 요소의 개수가 n인 배열에 계속해서 데이터가 입력될 때, 가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버린다.
• 다음 예제를 보자.

#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_s("%d", &a[cnt++ % N]);
		printf("계속할까요 (Yes.. / No..) : ");
		scanf_s("&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;
	
}

1. 1,2,3,4,5,6,7,8,9,10,11를 입력하는 예제다.
2. 배열에 남아있는 10개만 저장되고 처음에 입력한 1은 제외된다.
   입력한 값을 저장하는 위치의 인덱스는 a[cnt++ % N]로 구현한다.

• 첫 번째 값을 입력했다.
  - cnt 0 / 10으로 나눈 나머지는 0이다. 입력값은 a[0]에 저장된다.
  - cnt 1 / 10으로 나눈 나머지는 1이다. 입력값은 a[1]에 저장된다.
  .....
  - cnt 10 / 10으로 나눈 나머지는 0이다. 입력값은 a[0]에 저장된다.
  - cnt 11 / 10으로 나눈 나머지는 1이다. 입력값은 a[1]에 저장된다.

<결과>

※내용정리

1. 큐에 대한 정의 및 예시
2. 큐 & 링버퍼
3. Queue 함수 구현 및 예시
4. 링버퍼 예시