3-2 배열 Queue 구현

Queue는 선형 자료구조 중 하나로, 은행 업무와 비유를 해보면 사람들은 대기표를 뽑고 은행원들은 대기표의 번호 순에 따라 업무를 해결해 주는데 이때는 당연히 먼저 온 사람이 업무를 먼저 보고 빠져나가는 식입니다.

​

이처럼 큐는 First In First Out으로 선입선출의 특징을 가지고 있습니다.

큐의 대표적인 기능을 간단히 살펴보자면 다음과 같습니다.

​

1. 큐에 데이터 삽입 (= 대기표 뽑기)

2. 큐에 쌓여있는 데이터 조회 (= 대기인원 보여주기)

3. 큐에 있는 데이터를 앞에부터 제거 (= 순서대로 대기인원 호출)

​

위의 세 가지 기능은 대표적인 것이고 이외에 추가적으로 큐가 비어있는지 확인을 해주는 함수와 큐에 들어갈 수 있는 공간이 꽉 찼는지 확인하는 함수를 구현해보았습니다.

 

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

enum Queue_list {
	Add = 1,
	Pop,
	Display,
	Quit
};

int front = 0, rear = 0; // 삽입할 때 위치(rear), 제거할 때 위치(front)
int Queue_array[MAX]; // 큐에 들어갈 수 있는 최대 공간 0~9 

void Queue_insert(); // 큐 삽입 
void Queue_delete(); // 큐 데이터 삭제 
void Queue_display(); // 큐 출력 
int IsEmpty(); // 비어 있는 경우 예외 처리 
int IsFull(); // 큐가 데이터를 넣을 수 없는 경우 예외 처리(Memory overflow) 

int main() {
	enum Queue_list select;
	while(1) {
		printf("==============Queue Menu==============\n");
		printf("1. Add\n");
		printf("2. Pop\n");
		printf("3. Display\n");
		printf("4. Quit\n");
		scanf("%d",&select);
		switch(select) {
			case Add:
				Queue_insert();	
				break;
			case Pop:
				Queue_delete();
				break;
			case Display:
				Queue_display();
				break;
			case Quit:
				printf("프로그램을 종료합니다.\n");
				exit(0);
			default:
				printf("잘못 입력하셨습니다. 다시 입력해주세요.\n");
				break; 
		}
	}
	return 0;
}

void Queue_insert() {
	if(IsFull()) {
		printf("Queue가 꽉 찼습니다.\n");
		return;
	} 
	
	int data;
	printf("삽입 할 데이터 입력: ");
	scanf("%d",&data);
	Queue_array[rear++] = data;
}
void Queue_delete() {
	if(IsEmpty()) {
		printf("Queue가 비었습니다.\n");
		return;
	}
	
	printf("삭제된 데이터는 %d입니다.\n", Queue_array[front++]);
}
void Queue_display() {
	if(IsEmpty()) {
		printf("Queue가 비었습니다.\n");
		return;
	}
	
	int i;
	printf("==============Queue Print=============\n");
	for(i = front; i<rear; i++) {
		printf("%d ",Queue_array[i]);
	}
	printf("\n");
}

int IsEmpty() {  
	if(front == rear) 
		return 1;
	else 
		return 0;
}
int IsFull() {
	if(rear == MAX) 
		return 1;
	else 
		return 0;
}

 

자료구조를 처음 접하신다면 이해가 안 될 수는 있지만 그렇게 어렵지 않은 개념이니 천천히 따라오신다면 충분히

혼자서도 구현해볼 수 있을 것입니다. 소스코드를 자세히 확인해보겠습니다.

 

#include <stdio.h>
#include <stdlib.h>
#define MAX 10

enum Queue_list {
	Add = 1,
	Pop,
	Display,
	Quit
};

int front = 0, rear = 0; // 삽입할 때 위치(rear), 제거할 때 위치(front)
int Queue_array[MAX]; // 큐에 들어갈 수 있는 최대 공간 0~9 

void Queue_insert(); // 큐 삽입 
void Queue_delete(); // 큐 데이터 삭제 
void Queue_display(); // 큐 출력 
int IsEmpty(); // 비어 있는 경우 예외 처리 
int IsFull(); // 큐가 데이터를 넣을 수 없는 경우 예외 처리(Memory overflow)

 

이전과 마찬가지로 프로그램 종료를 위해 stdlib.h를 포함시켰으며, 큐에 들어갈 수 있는 데이터의 최대 개수를 10개로 정의하였습니다.

​

그다음은 열거형에 대한 코드인데, 열거형은 switch 분기문을 사용할 때 가독성을 높이는 데에도 좋고 유용하다고 하여 이번에는 열거형을 활용해서 각각의 기능을 숫자로 1부터 매칭 시켜 놓았습니다.

​

큐는 데이터를 삽입할 때와 삭제할 때에 변수가 총 2개가 필요하므로 삽입하고 나서 위치를 나타내는 rear와

제거하고 나서 위치를 나타내는 front 변수를 선언하고 0으로 초기화하였고, 사이즈만큼의 데이터가 들어갈 수 있는 큐 배열을 선언하였습니다.

​

이번에 선언한 함수들은 맨 위에 설명한 것과 같이 삽입, 삭제, 조회, 비어있는지 확인, 꽉 찼는지 확인해 주는 함수들로 5가지를 작성하였습니다.

 

int main() {
	enum Queue_list select;
	while(1) {
		printf("==============Queue Menu==============\n");
		printf("1. Add\n");
		printf("2. Pop\n");
		printf("3. Display\n");
		printf("4. Quit\n");
		scanf("%d",&select);
		switch(select) {
			case Add:
				Queue_insert();	
				break;
			case Pop:
				Queue_delete();
				break;
			case Display:
				Queue_display();
				break;
			case Quit:
				printf("프로그램을 종료합니다.\n");
				exit(0);
			default:
				printf("잘못 입력하셨습니다. 다시 입력해주세요.\n");
				break; 
		}
	}
	return 0;
}

 

위에서 열거형을 정의하였으므로 열거형 변수를 선언해 주면, switch 분기문에서 매칭된 열거형의 값에 따라 코드를 실행할 수가 있습니다. 다른 사람이 보았을 때도 코드 안에서 1번이 무엇인지, 2번이 무엇인지 이렇게 하나씩 외우지 않더라도 의미가 담긴 문자열로 case를 구분해 주니 가독성 측면에서 봤을 때도 이전보다 좋아진 것을 볼 수 있습니다.

​

while 문에서는 큐의 기능으로 어떤 것들이 있는지에 대한 메뉴를 출력해 주고, switch 문에서 사용자의 입력에 따라 case 별로 함수가 호출되거나 프로그램이 종료되게끔 작성을 하였습니다. 또한 잘못 입력하는 경우에 대한 예외 처리는 default에서 하게 되고, 처음으로 돌아가게 됩니다.

 

void Queue_insert() {
	if(IsFull()) {
		printf("Queue가 꽉 찼습니다.\n");
		return;
	} 
	
	int data;
	printf("삽입 할 데이터 입력: ");
	scanf("%d",&data);
	Queue_array[rear++] = data;
}

void Queue_delete() {
	if(IsEmpty()) {
		printf("Queue가 비었습니다.\n");
		return;
	}
	
	printf("삭제된 데이터는 %d입니다.\n", Queue_array[front++]);
}

 

삽입, 삭제 함수에 대한 코드를 보면 데이터를 처리하기 이전에 큐가 꽉 찼는지, 비어있는지 사전에 예외 처리를 해주는 코드를 작성하였습니다. 만약 예외에 걸린다면 return을 통해 함수가 바로 종료될 것입니다. 저는 여러 프로그램을 작성해보면서 알게 되었는데 의도치 않은 데이터가 처리되었을 때 잘못된 정보를 출력하는 경우가 은근히 많이 생겨 예외 처리가 굉장히 중요하다는 것을 깨달았습니다. IsEmpty, IsFull 함수는 간단하기 때문에 마지막에 보도록 하겠습니다.

 

 

​

Queue_insert 삽입 함수에서는 큐의 공간이 꽉 찬 게 아니라면 데이터를 입력받아서, 삽입할 때 위치를 나타내는 rear 변수를 이용하여 큐 배열의 인덱스 0부터 차례대로 입력받은 데이터가 들어가게 됩니다. 해당 메모리 공간에 데이터가 들어가면 다음 메모리 공간에 새로운 데이터를 입력받아야 하므로 후위 증감 연산을 통해 rear는 1씩 증가하게 됩니다.

​

Queue_delete 삭제 함수도 비슷한 원리로, 큐가 비어있지 않은 경우라면 삭제할 때의 인덱스 변수 front 변수를 통해 삭제를 할 수 있습니다. 선입선출의 특징을 생각해 봤을 때 insert를 한다면 rear가 계속 증가하니 delete 할 때는 front로 접근하여 앞에 있는 데이터를 삭제해야 되기 때문에 rear와 front 두 개의 변수를 사용하는 것입니다. 이때도 똑같이 front로 삭제를 하고 나서 다음 데이터에 해당되는 인덱스에 접근을 해야 삭제가 계속 가능하므로 front도 1씩 증가시켜 줘야 합니다.

 

void Queue_display() {
	if(IsEmpty()) {
		printf("Queue가 비었습니다.\n");
		return;
	}
	
	int i;
	printf("==============Queue Print=============\n");
	for(i = front; i<rear; i++) {
		printf("%d ",Queue_array[i]);
	}
	printf("\n");
}

 

Queue_display 함수를 통해 큐의 데이터들을 조회하게 되는데, 큐가 비어있지 않았을 때는 데이터가 있다는 의미이므로 큐의 앞에 있는 위치 front부터 가장 마지막 데이터 삽입을 했을 때의 위치인 rear-1까지의 데이터들이 반복문을 통해 출력됩니다. 삽입한 후 rear는 위의 설명처럼 1이 증가하므로 rear-1까지 범위를 설정해야 올바르게 출력 결과를 확인할 수 있습니다.

 

int IsEmpty() {  
	if(front == rear) 
		return 1;
	else 
		return 0;
}

int IsFull() {
	if(rear == MAX) 
		return 1;
	else 
		return 0;
}

 

front와 rear의 값이 같은 경우, 삽입과 삭제를 한 번도 하지 않았거나 삽입을 배열의 사이즈만큼 끝까지 하고 나서 모든 데이터들을 삭제했을 때 결국 front와 rear가 같은 값을 가지게 되는 것이므로 비어있다고 볼 수 있습니다. 따라서, 비어있다면 1을 반환하고 비어있지 않으면 0을 반환하게 됩니다.

​

IsFull 함수에서는 rear로 인덱스 0~9까지 10개의 데이터를 모두 입력을 한 후에 MAX가 되어 추가로 넣게 된다면 큐가 꽉 찼다고 할 수 있죠. 그렇기에, rear와 MAX 값이 같다면 1을 반환하고 그렇지 않다면 0을 반환합니다.

​

실행 결과는 다음과 같습니다.

 

 

삽입, 조회

​

제거, 조회

​

이렇게 배열로 Queue라는 자료구조를 구현해보았는데 한계점을 발견할 수 있을 것입니다.

front와 rear가 증가만 하므로 삭제를 했을 때 배열의 앞에 있는 메모리 공간이 비어 있어도 사용하지 못한다는 것입니다. 그렇기에 배열의 원소들을 왼쪽으로 하나씩 이동시켜야 한다는 번거로움이 있습니다.

​

나머지 연산자를 이용해 선형 큐의 단점을 보완한 자료구조가 있는데, 이를 원형 큐라고 부릅니다.

배열의 구조상 선형적이지만 순환하게끔 인덱스를 계산하여 원형으로 생각해서 코드를 작성하는 것입니다.

이 원형 큐는 추후 자료구조 파트에서 다뤄보거나 문제 풀이할 때에 이용해보겠습니다. 감사합니다.