개념

• FIFO (First-In-First-Out, 선입선출)
• 프런트(front): 큐의 제일 앞
• 리어(rear): 큐의 제일 끝

---

연산

인큐(Enqueue)

• 끝(rear)에 자료 추가
• 넘침(Overflow) 현상 고려

디큐(Dequeue)

• 앞(front)의 자료 삭제
• 부족(Underflow) 현상 고려

피크(Peek)

• 앞(front) 자료 반환

---

구현

• Array list를 이용한 원형 큐
  👉 데이터 삭제 시 필요한 연산의 수를 줄이고 남은 데이터 공간을 낭비하지 않기 위함

구조체와 함수 원형

typedef struct ArrayQueueNodeType
{
	char	data;
}	ArrayQueueNode;

typedef struct ArrayQueueType
{
	int				maxElementCount;		// 최대 원소 개수
	int				currentElementCount;	// 현재 원소의 개수
	int				front;					// front 위치
	int				rear;					// rear 위치
	ArrayQueueNode	*pElement;				// 노드 저장을 위한 1차원 배열 포인터
}	ArrayQueue;

ArrayQueue*		createArrayQueue(int maxElementCount);
int				enqueueAQ(ArrayQueue* pQueue, ArrayQueueNode element);
ArrayQueueNode	*dequeueAQ(ArrayQueue* pQueue);
ArrayQueueNode	*peekAQ(ArrayQueue* pQueue);
void			deleteArrayQueue(ArrayQueue** pQueue);
int				isArrayQueueFull(ArrayQueue* pQueue);
int				isArrayQueueEmpty(ArrayQueue* pQueue);
void			displayArrayQueue(ArrayQueue *pQueue);

생성

• 최대 크기 지정
• 헤드 노드가 배열의 첫 번째 주소, front와 rear의 인덱스를 가짐

ArrayQueue*	createArrayQueue(int maxElementCount)
{
	ArrayQueue	*queue;

	queue = (ArrayQueue *)malloc(sizeof(ArrayQueue));
	if (queue == NULL)
		return (NULL);
	queue->maxElementCount = maxElementCount;
	queue->currentElementCount = 0;
	queue->pElement = (ArrayQueueNode *)malloc(sizeof(ArrayQueueNode) * maxElementCount);
	if (queue->pElement == NULL)
	{
		free(queue);
		queue = NULL;
		return (NULL);
	}
	return (queue);
}

인큐(Enqueue)

• 새로 추가할 rear의 인덱스는 (rear + 1) % maxElementCount

int	enqueueAQ(ArrayQueue* pQueue, ArrayQueueNode element)
{
	int	index;

	if (isArrayQueueFull(pQueue) == TRUE)
		return (FALSE);
	if (isArrayQueueEmpty(pQueue) == TRUE)
	{
		pQueue->front = 0;
		pQueue->rear = 0;
		(pQueue->pElement)[0] = element;
	}
	else
	{
		index = (pQueue->rear + 1) % pQueue->maxElementCount;
		(pQueue->pElement)[index] = element;
		pQueue->rear = index;
	}
	pQueue->currentElementCount++;
	return (TRUE);
}

디큐(Dequeue)

• 디큐 후 front의 인덱스는 (front + 1) % maxElementCount

ArrayQueueNode	*dequeueAQ(ArrayQueue* pQueue)
{
	ArrayQueueNode	*new;

	if (isArrayQueueEmpty(pQueue) == TRUE)
		return (NULL);
	new = peekAQ(pQueue);
	if (new == NULL)
		return (NULL);
	pQueue->front = (pQueue->front + 1) % pQueue->maxElementCount;
	pQueue->currentElementCount--;
	return (new);
}

피크(Peek)

ArrayQueueNode	*peekAQ(ArrayQueue* pQueue)
{
	ArrayQueueNode	*new;

	if (isArrayQueueEmpty(pQueue) == TRUE)
		return (NULL);
	new = (ArrayQueueNode *)malloc(sizeof(ArrayQueueNode));
	if (new == NULL)
		return (NULL);
	*new = (pQueue->pElement)[pQueue->front];
	return (new);
}

🔗 배열 리스트로 구현한 원형 큐 전체 코드