큐(Queue)

자료 저장 형태 중 큐에 대해 설명

• 큐는 데이터를 선입선출 (FIFO, First-In-First-Out)의 원리로 관리한다. 즉, 가장 먼저 삽입된 데이터가 가장 먼저 삭제되는 구조이다.
• 데이터를 삽입하는 함수를 enqueue(), 데이터를 삭제하는 함수를 dequeue() 라고 하며 큐의 앞쪽에 위치한 요소를 front, 뒤쪽에 위치한 요소를 rear라고 한다.
• 작업 대기열, 메시지, 큐, 버퍼 등이 큐의 예시로 사용된다.

여러 작업이 동시에 발생할 경우, 큐를 사용해 작업을 순서대로 처리한다. 예를들어, 프린터의 출력 대기열의 경우, 새로운 출력 작업은 큐의 뒤쪽인 enqueue, 프린터는 큐의 앞쪽은 dequeue에서 처리해 프린터의 출력 대기열을 큐로 처리할 수 있다.

원형큐

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

#pragma warning (disable : 4996)

typedef struct queue	//원형큐
{
	int *arr;	//동적할당 된 메모리의 주소를 저장
	int rear;	//삽입하려는 쪽 배열의 인덱스
	int front;	//삭제하려는 배열의 인덱스
	int capacity;	//배열의 최대용량
	int count;	//저장된 개수
}queue;

void queueinitialize(queue *p, int size)	//p -> 8byte
{
	p->rear = p->front = p->count = 0;
	p->capacity = size;

	p->arr = (int*)malloc(sizeof(int) * size);

}

void enqueue(queue *p, int data)
{
	if(p->count >= p->capacity)		//overflow인 경우
	{
		printf("\n\n\t\tqueue overflow\n");
		return;
	}
	p->arr[p->rear] = data;
	printf("\n\n\t\t%d enqueue\n", p->arr[p->rear]);
	(p->rear)++;
	(p->count)++;

	if (p->rear >= p->capacity)	//마지막 인덱스라면?
	{
		p->rear = 0;	//0번 인덱스로 변경
	}
}

void dequeue(queue *p)
{
	if (p->count <= 0)
	{
		printf("\n\n\t\tdequeue underflow\n");
		return;
	}

	printf("\n\n\t\t%d dequeue\n", p->arr[p->front]);
	(p->front)++;	//삭제하려는 위치를 변경하므로 증가
	(p->count)--;	//개수 감소

	if (p->front >= p->capacity)	//마지막 인덱스라면?
		p->front = 0;	//0번 인덱스로 변경
}

void clear(queue *p)	//초기상태로 변환
{
	p->rear = p->front = p->count = 0;
}

void display(queue *p)
{
	int i, index;
	printf("\n\n\t\t queue data : ");
	for (i = 0; i < p->count; i++)	//저장된 개수만큼 반복
	{
		index = (p->front + i) % p->capacity;
		printf("%d ", p->arr[index]);
	}
	puts("");
	
} 

int main()
{
	int choice, size, data;
	queue* que;	//queue 구조체 변수 선언

	printf("\n\n큐의 크기 입력 : ");
	scanf("%d", &size);
	while (getchar() != '\n');

	queueinitialize(&que, size);
	while (1)
	{
		system("cls");
		printf("\n\n\t\t ***integer circular queue***\n");
		printf("1. enqueue(insertion)		2. dequeue(deletion)		3. print		4. clear		0.exit\n");
		printf("choice : [ ]\b\b");
		scanf("%d", &choice);
		while (getchar() != '\n');

		switch (choice)
		{
		case 1:
			printf("insert integer : ");
			scanf("%d", &data);
			while (getchar() != '\n');
			enqueue(&que, data);
			break;

		case 2:
			dequeue(&que);
			break;

		case 3:
			display(&que);	//구조체는 보통 크기가 크기 때문에 call by value가 아닌 call by address로 인수를 전달하는 것이 좋다.
							//call by value로 전달 시 메모리도 많이 들고 복사하는 처리시간도 필요하기 때문에 overhead가 높아진다.
			break;

		case 4:
			clear(&que);
			break;

		case 0:
			free(que->arr);	//que.arr이 가리키는 동적메모리 해제
			exit(0);
		}
		printf("\n\n\t\t");
		system("pause");

	}

	return 0;
}

실행결과

초기 실행에서 큐의 크기를 입력받는다.

enqueue선택 후 삽입하는 과정 반복

결과값 노출

가장 먼저 삽입된 '5' 삭제

초기화 후 종료(exit)

요세푸스 문제 (원형큐)

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

#pragma warning (disable : 4996)

typedef struct queue
{
	int* arr;
	int rear;
	int front;
	int capacity;
	int count;
} queue;

void enqueue(queue* que, int data)
{
	if (que->count == que->capacity)
	{
		printf("Queue is full!\n");
		return;
	}

	que->arr[que->rear] = data;
	que->rear = (que->rear + 1) % que->capacity;
	que->count++;
}

int dequeue(queue* que)
{
	if (que->count == 0)
	{
		printf("Queue is empty!\n");
		return -1; // 예외 처리를 위해 음수 값을 반환
	}

	int data = que->arr[que->front];
	que->front = (que->front + 1) % que->capacity;
	que->count--;

	return data;
}

void initializeQueue(queue* que, int size)
{
	que->arr = (int*)malloc(sizeof(int) * size);
	que->rear = 0;
	que->front = 0;
	que->capacity = size;
	que->count = 0;

	for (int i = 1; i <= size; i++)
		enqueue(que, i);
}

void josephus(queue* que, int kill)
{
	printf("\n\n\t\t처형 순서: ");

	while (que->count > 1)
	{
		for (int i = 1; i < kill; i++)
		{
			int data = dequeue(que);
			enqueue(que, data);
		}

		int executed = dequeue(que);
		printf("%d ", executed);
	}

	printf("\n\t\t최후 생존자: %d\n", que->arr[que->front]);
}

int main()
{
	int size, kill;
	queue que;

	do
	{
		printf("\n\n\t***요세푸스 문제***\n\n");
		printf("\t\t처형을 기다리는 사람은 몇 명입니까? ");
		scanf("%d", &size);
	} while (size <= 0);

	initializeQueue(&que, size);  // 동적할당 후 1부터 1씩 증가되는 값으로 초기화

	do
	{
		printf("\n\n\t\t1번 ~ %d번의 처형 대기자가 있습니다.\n", size);
		printf("\t\t몇 번째 사람을 처형 시키겠습니까? ");
		scanf("%d", &kill);
	} while (kill <= 0 || kill > size);

	josephus(&que, kill);

	free(que.arr);

	printf("\n\n\t\t");
	system("pause");

	return 0;
}

실행결과

🔥요세푸스란?

사람들이 순서대로 처형되는 상황에서 최후의 생존자를 구하는 문제

• 처형할 순서를 나타내는 m값이 주어지면, 순서대로 m번째 병사를 처형하여 다음 병사로 넘어간다. 이 과정을 N명의 병사가 모두 처형될 때까지 반복한다.
• 요세푸스 문제에서 구해야 하는 것은 마지막으로 남는 병사의 번호이다.