큐 Queue

자료구조

큐 Queue

아옳이 2021. 9. 1. 17:53

큐(Queue) : FIFO(First-In-First-Out) = 선입선출

-리스트와 마찬가지로 선형 자료구조 But 자료의 추가는 맨 뒤(Rear)에서, 제거는 맨 앞(Front)에서

큐의 연산

인큐(enqueue): 큐의 맨 뒤에 새로운 자료를 추가

디큐(dequeue): 큐의 맨 앞에서 있는 자료를 제거한 뒤 반환

피크(peek): 큐의 맨 앞에 있는 자료를 제거하지 않고 반환

배열을 이용한 선형 큐

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

typedef struct ArrayQueueNodeType		// 노드 구현, 노드로 자료를 감싸는 이유는 동시에 여러개의 자료를 저장하기 위해
{
	char			data;
} ArrayQueueNode;

typedef struct ArrayQueueType
{
	int				maxCount;			// 최대 자료 개수
	int				currentCount;		// 현재 재료 개수
	int				front;				// 프런트 위치
	int				rear;				// 리어 위치
	ArrayQueueNode	*pData;				// 자료를 저장하는 1차원 배열 포인터
} ArrayQueue;

ArrayQueue	*createArrayQueue(int size)
{
	ArrayQueue	*pReturn = NULL;
	pReturn = (ArrayQueue *)malloc(sizeof(ArrayQueue));
	memset(pReturn, 0, sizeof(ArrayQueue));
	pReturn->maxCount = size;
	pReturn->front = -1;				// 빈 큐에 처음으로 자료룰 추가하면 노드의 인덱스가 0이 되야하기 떄문
	pReturn->rear = -1;

	pReturn->pData = (ArrayQueueNode *)malloc(sizeof(ArrayQueueNode) * size);
	memset(pReturn->pData, 0, sizeof(ArrayQueueNode) * size);

	return (pReturn);
}

int		isArrayQueueFull(ArrayQueue *pQueue)
{
	int	ret = 0;

	if (pQueue != NULL)
	{
		if (pQueue->currentCount == pQueue->maxCount		// 현재 저장된 자료개수가 최대 자료개수와 같으면
			|| pQueue->rear == pQueue->maxCount - 1)		// 리어인덱스가 마지막 인덱스애 도달하면
			ret = 1;
	}

	return (ret);
}

int		enqueueAQ(ArrayQueue *pQueue, char data)
{
	int	ret = 0;

	if (pQueue != NULL)
	{
		if (isArrayQueueFull(pQueue) == 0)
		{
			pQueue->rear++;
			pQueue->pData[pQueue->rear].data = data;
			pQueue->currentCount++;
			ret = 1;
		}
		else
			printf("오류, 큐가 가득 찼습니다, enqueueAQ()\n");
	}

	return (ret);
}

int		isArrayQueueEmpty(ArrayQueue *pQueue)
{
	int	ret = 0;

	if (pQueue != NULL)
	{
		if (pQueue->currentCount == 0)
			ret = 1;
	}

	return (ret);
}

ArrayQueueNode	*dequeueAQ(ArrayQueue *pQueue)
{
	ArrayQueueNode	*pReturn = NULL;
	if (pQueue != NULL)
	{
		if (isArrayQueueEmpty(pQueue) == 0)
		{
			pReturn = (ArrayQueueNode *)malloc(sizeof(ArrayQueueNode));
			if (pReturn != NULL)
			{
				pQueue->front++;
				pReturn->data = pQueue->pData[pQueue->front].data;
				pQueue->currentCount--;
			}
			else
				printf("오류, 메모리 할당, dequeueAQ()\n");
		}
	}

	return (pReturn);		// 동적할당한 주소를 반환, 메모리 해제는 호출한 곳에서
}

ArrayQueueNode	*peekAQ(ArrayQueue *pQueue)
{
	ArrayQueueNode	*pReturn = NULL;
	if (pQueue != NULL)
	{
		if (isArrayQueueEmpty(pQueue) == 0)
			pReturn = &(pQueue->pData[pQueue->front + 1]);
	}

	return (pReturn);
}

void	deleteArrayQueue(ArrayQueue *pQueue)
{
	if (pQueue != NULL)
	{
		if (pQueue->pData != NULL)
			free(pQueue->pData);
		free(pQueue);
	}
}

void	displayArrayQueue(ArrayQueue *pQueue)
{
	int	i = 0;

	if (pQueue != NULL)
	{
		printf("큐의 크기: %d, 현재 노드 개수: %d\n",
			pQueue->maxCount,
			pQueue->currentCount);

		for (i = pQueue->front + 1; i <= pQueue->rear; i++)
			printf("[%d]-[%c]\n", i, pQueue->pData[i].data);
	}
}

int	main(void)
{
	ArrayQueue *pQueue = NULL;
	ArrayQueueNode	*pNode = NULL;

	pQueue = createArrayQueue(4);
	if (pQueue != NULL)
	{
		enqueueAQ(pQueue, 'A');
		enqueueAQ(pQueue, 'B');
		enqueueAQ(pQueue, 'C');
		enqueueAQ(pQueue, 'C');
		displayArrayQueue(pQueue);

		pNode = dequeueAQ(pQueue);
		if (pNode != NULL)
		{
			printf("Dequeue Value-[%c]\n",
				pNode->data);
			free(pNode);
		}
		displayArrayQueue(pQueue);

		pNode = peekAQ(pQueue);
		if (pNode != NULL)
			printf("Peek Value-[%c]\n",
				pNode->data);
		displayArrayQueue(pQueue);

		enqueueAQ(pQueue, 'E');			// Error
		displayArrayQueue(pQueue);
	}
	deleteArrayQueue(pQueue);

	return (0);
}

배열선형큐는 dequeue로 맨 앞에 빈 노드가 있어도 rear 의 값이 변하지 않아 여유공간이 있어도 사용할 수 없다는 단점이 있다.

이러한 단점을 보완하기 위해 사용하는 것이 '배열 원형 큐' 이다.

배열 원형 큐 (선형 큐와 다른 부분만)

int		isArrayQueueFull(ArrayQueue *pQueue)
{
	int	ret = 0;

	if (pQueue != NULL)
	{
		//if (pQueue->currentCount == pQueue->maxCount		// 현재 저장된 자료개수가 최대 자료개수와 같으면
		//	|| pQueue->rear == pQueue->maxCount - 1)		// 리어인덱스가 마지막 인덱스애 도달하면
		if (pQueue->currentCount == pQueue->maxCount)
			ret = 1;
	}

	return (ret);
}

int		enqueueAQ(ArrayQueue *pQueue, char data)
{
	int	ret = 0;

	if (pQueue != NULL)
	{
		if (isArrayQueueFull(pQueue) == 0)
		{
			//pQueue->rear++;
			pQueue->rear = (pQueue->rear + 1) % pQueue->maxCount;		// 나머지 연산을 이용해 배열의 마지막을 처음과 논리적으로 연결
			pQueue->pData[pQueue->rear].data = data;
			pQueue->currentCount++;
			ret = 1;
		}
		else
			printf("오류, 큐가 가득 찼습니다, enqueueAQ()\n");
	}

	return (ret);
}

ArrayQueueNode	*dequeueAQ(ArrayQueue *pQueue)
{
	ArrayQueueNode	*pReturn = NULL;
	if (pQueue != NULL)
	{
		if (isArrayQueueEmpty(pQueue) == 0)
		{
			pReturn = (ArrayQueueNode *)malloc(sizeof(ArrayQueueNode));
			if (pReturn != NULL)
			{
				//pQueue->front++;
				pQueue->front = (pQueue->front + 1) % pQueue->maxCount;
				pReturn->data = pQueue->pData[pQueue->front].data;
				pQueue->currentCount--;
			}
			else
				printf("오류, 메모리 할당, dequeueAQ()\n");
		}
	}

	return (pReturn);		// 동적할당한 주소를 반환, 메모리 해제는 호출한 곳에서
}

void	displayArrayQueue(ArrayQueue *pQueue)
{
	int	i = 0;
	int position = 0;

	if (pQueue != NULL)
	{
		printf("큐의 크기: %d, 현재 노드 개수: %d\n",
			pQueue->maxCount,
			pQueue->currentCount);

		//for (i = pQueue->front + 1; i <= pQueue->rear; i++)
		for (i = pQueue->front + 1; i <= pQueue->front + pQueue->currentCount; i++)	// front 위치부터 저장된 자료 개수만큼
		{
			position = i % pQueue->maxCount;
			printf("[%d]-[%c]\n", position, pQueue->pData[i].data);
		}
	}
}

포인터를 이용한 연결 큐(Linked Queue)

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

typedef struct LinkedQueueNodeType
{
	char	data;
	struct	LinkedQueueNodeType	*pLink;
} LinkedQueueNode;

typedef struct LinkedQueueType
{
	int	currentCount;
	LinkedQueueNode	*pFront;
	LinkedQueueNode	*pRear;
} LinkedQueue;

LinkedQueue	*createLinkedQueue()
{
	LinkedQueue	*pReturn = (LinkedQueue *)malloc(sizeof(LinkedQueue));
	memset(pReturn, 0, sizeof(LinkedQueue));

	return (pReturn);
}

int	isLinkedQueueEmpty(LinkedQueue *pQueue)
{
	int	ret = 0;

	if (pQueue != NULL)
	{
		if (pQueue->currentCount == 0)
			ret = 1;
	}

	return (ret);
}

int	enqueueLQ(LinkedQueue *pQueue, char data)
{
	int ret = 0;
	LinkedQueueNode *pNode = NULL;

	pNode = (LinkedQueueNode *)malloc(sizeof(LinkedQueueNode));
	pNode->data = data;
	pNode->pLink = NULL;

	if (isLinkedQueueEmpty(pQueue) == 0)
	{
		pQueue->pRear->pLink = pNode;
		pQueue->pRear = pNode;
	}
	else
	{
		pQueue->pFront = pNode;
		pQueue->pRear = pNode;
	}
	pQueue->currentCount++;
	ret = 1;

	return (ret);
}

LinkedQueueNode	*dequeueLQ(LinkedQueue *pQueue)
{
	LinkedQueueNode	*pReturn = NULL;
	if (isLinkedQueueEmpty(pQueue) == 0)
	{
		pReturn = pQueue->pFront;
		pQueue->pFront = pQueue->pFront->pLink;
		pReturn->pLink = NULL;

		pQueue->currentCount--;

		if (isLinkedQueueEmpty(pQueue) == 1)
			pQueue->pRear = NULL;
	}

	return (pReturn);
}

LinkedQueueNode	*peekLQ(LinkedQueue *pQueue)
{
	LinkedQueueNode	*pReturn = NULL;
	if (pQueue != NULL)
	{
		if (isLinkedQueueEmpty(pQueue) == 0)
			pReturn = pQueue->pFront;
	}

	return (pReturn);
}

void	deleteLinkedQueue(LinkedQueue *pQueue)
{
	LinkedQueueNode	*pNode = NULL;
	LinkedQueueNode	*pDelNode = NULL;

	if (pQueue != NULL)
	{
		pNode = pQueue->pFront;
		while (pNode != NULL)
		{
			pDelNode = pNode;
			pNode = pNode->pLink;
			free(pDelNode);
		}
		free(pQueue);
	}
}

void	displayLinkedQueue(LinkedQueue *pQueue)
{
	LinkedQueueNode	*pNode = NULL;
	int	i = 0;

	if (pQueue != NULL)
	{
		printf("현재 노드 개수: %d\n",
			pQueue->currentCount);
		pNode = pQueue->pFront;
		while (pNode != NULL)
		{
			printf("[%d]-[%c]\n", i, pNode->data);
			i++;
			pNode = pNode->pLink;
		}
	}
}

int	main(void)
{
	LinkedQueue	*pQueeu = NULL;
	LinkedQueueNode	*pNode = NULL;

	pQueeu = createLinkedQueue();
	if (pQueeu != NULL)
	{
		enqueueLQ(pQueeu, 'A');
		enqueueLQ(pQueeu, 'B');
		enqueueLQ(pQueeu, 'C');
		enqueueLQ(pQueeu, 'D');
		displayLinkedQueue(pQueeu);

		pNode = dequeueLQ(pQueeu);
		if (pNode != NULL)
		{
			printf("Dequeue Value-[%c]\n", pNode->data);
			free(pNode);
		}
		displayLinkedQueue(pQueeu);

		pNode = peekLQ(pQueeu);
		if (pNode != NULL)
			printf("Peek Value-[%c]\n", pNode->data);
		displayLinkedQueue(pQueeu);

		enqueueLQ(pQueeu, 'E');
		displayLinkedQueue(pQueeu);
	}

	return (0);
}

dequeue() 를 수행해도, 프런트노드의 인덱스 값이 0이다