Queue(배열)

이인혁·2024년 6월 5일

자료구조

목록 보기

7/12

1. Queue 자료구조

Queue라는 자료구조는 Stack과 비슷한 구조를 이루는 자료구조입니다. Stack이 LIFO(Last In First Out, 후입선출)이었다면, Queue는 FIFO(First In First Out, 선입선출)입니다. Queue는 터널같은 모양으로 생각하면 쉽습니다. 정확히는 1차선 터널로 생각하시면 쉽습니다. 절대 앞을 추월할 수 없는 터널에서는 먼저 들어간 차가 먼저 나오게 됩니다. Stack과는 정반대의 모습을 보여줍니다.

Queue의 FIFO는 은행이나 병원같은 대기표시스템에서 사용됩니다. 먼저 뽑은 대기표가 먼저 뽑힐 수 있도록 해주는 프로그램입니다. 흔히 일상생활에서도 많이 볼 수 있는 자료구조입니다.

Queue는 Stack처럼 Queue의 기능을 만들어주는 함수가 존재합니다. 바로 Enqueue와 Dequeue입니다. Enqueue는 리스트에 데이터를 추가하는 함수이고, Dequeue는 리스트에서 데이터를 뽑는 함수 입니다. Queue는 Enqueue와 Dequeue가 가장 중요하기 때문에, 집중해서 보는게 좋습니다.

2. Queue를 배열로 구현

먼저 Queue를 배열로 구현해보겠습니다.

헤더파일

CircularQueue.h

#ifndef CIRCULAR_QUEUE_H
#define CIRCULAR_QUEUE_H

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

typedef int ElementType;

typedef struct tagNode {
	ElementType Data;
}Node;

typedef struct tagCircularQueue {
	int Capacity;
	int Front;
	int Rear;

	Node* Nodes;
}CircularQueue;

void CQ_CreateQueue(CircularQueue** Queue, int Capacity); -> Queue리스트 생성 함수
void CQ_DestroyQueue(CircularQueue* Queue); -> Queue리스트 삭제 함수
void CQ_Enqueue(CircularQueue* Queue, ElementType Data); -> Enqueue(데이터 추가)함수
ElementType CQ_Dequeue(CircularQueue* Queue); -> Dequeue(데이터 추출)함수
int CQ_GetSize(CircularQueue* Queue); -> Queue크기 반환하는 함수
int CQ_IsEmpty(CircularQueue* Queue); -> Queue가 비어있는지 알려주는 함수
int CQ_IsFull(CircularQueue* Queue); -> Queue가 꽉 차있는지 알려주는 함수

#endif

CircularQueue 구조체를 보면 Capacity와 Front, Rear, Node의 배열을 저장할 Node*가 있습니다.

Capacity는 배열의 총 개수인 것 같고, Front는 맨 앞 Rear는 맨 뒤를 의미하는 것 같습니다. 왜 다른 자료구조들이랑 다르게 Front와 Rear가 둘 다 존재하는지 궁금하실 수 있습니다. Stack은 아무리 Pop을 하여도, Head가 바뀌는 일은 없었습니다. 하지만 Queue는 Dequeue를 하면, Front가 추출되기 때문에, Front가 자주 바뀝니다. 그래서 배열의 길이를 index만으로 알 수 없기때문에, Rear까지 넣어줘서 배열의 길이를 알 수 있게 했습니다.

소스파일

CircularQueue.c

#include "CircularQueue.h"

void CQ_CreateQueue(CircularQueue** Queue, int Capacity) {
	//큐를 자유저장소에 생성
	(*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));

	//입력된 Capacity+1만큼의 노드를 자유 저장소에 생성
	(*Queue)->Nodes = (Node*)malloc(sizeof(Node) * (Capacity + 1));

	(*Queue)->Capacity = Capacity;
	(*Queue)->Front = 0;
	(*Queue)->Rear = 0;
}

void CQ_DestroyQueue(CircularQueue* Queue) {
	free(Queue->Nodes);
	free(Queue);
}

void CQ_Enqueue(CircularQueue* Queue, ElementType Data) {
	int Position = 0;

	if (Queue->Rear == Queue->Capacity) {
		Position = Queue->Rear;
		Queue->Rear = 0;
	}
	else
		Position = Queue->Rear++;

	Queue->Nodes[Position].Data = Data;
}

ElementType CQ_Dequeue(CircularQueue* Queue) {
	int Position = Queue->Front;

	if (Queue->Front == Queue->Capacity) {
		Queue->Front = 0;
	}
	else {
		Queue->Front++;
	}
	return Queue->Nodes[Position].Data;
}

int CQ_GetSize(CircularQueue* Queue) {
	if (Queue->Front <= Queue->Rear)
		return Queue->Rear - Queue->Front;
	else
		return Queue->Rear + (Queue->Capacity - Queue->Front) + 1;
}

int CQ_IsEmpty(CircularQueue* Queue) {
	return (Queue->Front == Queue->Rear);
}

int CQ_IsFull(CircularQueue* Queue) {
	if (Queue->Front < Queue->Rear) {
		return (Queue->Rear - Queue->Front) == Queue->Capacity;
	}
	else
		return (Queue->Rear + 1) == Queue->Front;
}

CQ_CreateQueue함수와 CQ_DestroyQueue함수를 보겠습니다.

void CQ_CreateQueue(CircularQueue** Queue, int Capacity) {
	(*Queue) = (CircularQueue*)malloc(sizeof(CircularQueue)); // Queue리스트 생성

	(*Queue)->Nodes = (Node*)malloc(sizeof(Node) * (Capacity + 1)); // Capacity개수 만큼 Node 생성

	(*Queue)->Capacity = Capacity; // 리스트 Capacity 초기화
	(*Queue)->Front = 0; // 리스트 Front 초기화
	(*Queue)->Rear = 0; // 리스트 Rear 초기화
}

void CQ_DestroyQueue(CircularQueue* Queue) {
	free(Queue->Nodes); // Queue의 노드배열 삭제
	free(Queue); // Queue 삭제
}

여기서 의문인거는
(*Queue)->Nodes = (Node*)malloc(sizeof(Node) * (Capacity + 1));
이 문장입니다. 왜 Capacity보다 1개 더 많이 Node를 생성할까요? 그것은 배열을 빈곳없이 채우면, 비었을 때와 가득찼을 때가 구분이 안되기 때문입니다. 그래서 한칸은 무조건 남겨두는 겁니다. 그랬을 때는 비었을때와 가득찼을때가 구분이 됩니다.

CQ_Enqueue함수

void CQ_Enqueue(CircularQueue* Queue, ElementType Data) {
	int Position = 0; -> 현재위치 초기화

	if (Queue->Rear == Queue->Capacity) { -> Rear가 배열 맨끝에 있을 때
		Position = Queue->Rear; -> 포지션을 Rear위치로 변경
		Queue->Rear = 0; -> Rear을 배열 맨 앞으로 보내기
	}
	else
		Position = Queue->Rear++; -> Rear위치에 Position 초기화, Rear +1

	Queue->Nodes[Position].Data = Data; -> Position 위치에 Data추가
}

이 함수에서 알 수 있는 것은 Rear에 있는 노드에는 데이터가 없다는 얘기입니다. 이 뜻은 한 칸을 비웠을 때, Front와 Rear가 겹치지 않는 다는 얘기이고, 구분이 가능하다는 얘기입니다.

CQ_Dequeue함수

ElementType CQ_Dequeue(CircularQueue* Queue) {
	int Position = Queue->Front; ->Front 요소 저장

	if (Queue->Front == Queue->Capacity) { ->Front가 맨 뒤에 있으면
		Queue->Front = 0; ->맨 앞으로 보내기
	}
	else {
		Queue->Front++; ->Front 증가(원래 Front삭제)
	}
	return Queue->Nodes[Position].Data; -> Position 값 반환
}

CQ_GetSize, CQ_IsEmpty, CQ_IsFull함수

int CQ_GetSize(CircularQueue* Queue) {
	if (Queue->Front <= Queue->Rear) -> Front가 앞에 있으면
		return Queue->Rear - Queue->Front; ->개수 반환(Front ~ Rear)
	else -> Front 가 뒤에 있으면
		return Queue->Rear + (Queue->Capacity - Queue->Front) + 1; -> 개수 반환(Front ~ Capacity, 0 ~ Rear)
}

int CQ_IsEmpty(CircularQueue* Queue) {
	return (Queue->Front == Queue->Rear); -> 비었으면 1, 아니면 0(Front == Rear는 비었다는 뜻)
}

int CQ_IsFull(CircularQueue* Queue) {
	if (Queue->Front < Queue->Rear) { -> Front가 앞에 있을 때
		return (Queue->Rear - Queue->Front) == Queue->Capacity; -> 개수가 Capacity랑 같으면 1, 아니면 0
	}
	else -> Front가 뒤에있을 때
		return (Queue->Rear + 1) == Queue->Front; -> 가득 차있으면(Front가 Rear보다 한칸 뒤) 1, 아니면 0
}

실행예시

적당한 main함수를 구현하여 실행해 보겠습니다.
CircularQueueMain.c

#include "CircularQueue.h"

int main() {
	int i;
	CircularQueue* Queue;

	CQ_CreateQueue(&Queue, 10);

	CQ_Enqueue(Queue, 1);
	CQ_Enqueue(Queue, 2);
	CQ_Enqueue(Queue, 3);
	CQ_Enqueue(Queue, 4);

	for (i = 0; i < 3; i++) {
		printf("Dequeue: %d", CQ_Dequeue(Queue));
		printf("Front: %d, Rear: %d\n", Queue->Front, Queue->Rear);
	}

	i = 100;
	while (CQ_IsFull(Queue) == 0) {
		CQ_Enqueue(Queue, i++);
	}

	printf("Capacity: %d, Size: %d\n\n", Queue->Capacity, CQ_GetSize(Queue));

	while (CQ_IsEmpty(Queue) == 0) {
		printf("Dequeue: %d, ", CQ_Dequeue(Queue));
		printf("Front: %d, Rear: %d\n", Queue->Front, Queue->Rear);
	}

	CQ_DestroyQueue(Queue);

	return 0;
}

결과

Dequeue: 1Front: 1, Rear: 4
Dequeue: 2Front: 2, Rear: 4
Dequeue: 3Front: 3, Rear: 4
Capacity: 10, Size: 10

Dequeue: 4, Front: 4, Rear: 2
Dequeue: 100, Front: 5, Rear: 2
Dequeue: 101, Front: 6, Rear: 2
Dequeue: 102, Front: 7, Rear: 2
Dequeue: 103, Front: 8, Rear: 2
Dequeue: 104, Front: 9, Rear: 2
Dequeue: 105, Front: 10, Rear: 2
Dequeue: 106, Front: 0, Rear: 2
Dequeue: 107, Front: 1, Rear: 2
Dequeue: 108, Front: 2, Rear: 2

이인혁

게임개발공부블로그

이전 포스트

Stack의 응용 : 사칙 연산 계산기

다음 포스트