[알고리즘] 0.4 은행 대기번호 관리

사람들이 차례를 기다리며 서있는 줄을 생각해보자.

앞에서부터 한 명씩 빠져나가 업무를 처리하는 줄을 큐(Queue)라고 한다.

 

은행에서 번호표를 받으면 큐에 들어가는 것을 볼 수 있고,

대기하던 고객이 자신의 번호가 불려져 창구에서 일을 처리하는 것은 큐에서 빠져나오는 것으로 볼 수 있다.

 

즉, 큐는 먼저 들어간 데이터가 먼저 나오는 자료구조를 말한다. 

반대로 스택(Stack)은 먼저 들어가나 데이터가 가장 나중에 나오는 자료구조다. 

여기서는 큐 자료구조를 구현해보자

 

1. 배열로 큐 작성하기

은행에서 대기 번호를 관리하는 프로그램을 작성해보자

 

[ 코드 ]

#include <iostream>

#define QUEIE_CAPACITY 8 // 큐에 사용되는 배열의 크기 설정

using namespace std;

int queue[QUEIE_CAPACITY];
int head = 0;
int tail = -1;
int queue_size = 0;

void enquene(int n){
	if (queue_size == QUEIE_CAPACITY){
		cout << "Queue Full !" << endl;
		return ;
	}
	tail++;
	queue_size++;
	queue[tail] = n;
}

int dequeue(){
	int r;
	if (queue_size ==0){
		cout << "Queue Empty!" << endl;
		return 0;
	}

	r = queue[head];
	head++;
	queue_size--;
	return r;
}

int main(void){
	int number, r;
	do {
		cout <<"Input number :" << endl;
		cin >> number;

		if (number >0){
			enquene(number);
		}

		else if (number ==0){
			r = dequeue();
			cout << r << endl;
		}
	}
	while (number >=0);

	return 0;
}

 

[ 결과 ] 

tot4766@tot4766:~/main/코딩/c++/알고리즘$ ./a.out
Input number :
1
Input number :
2
Input number :
3
Input number :
4
Input number :
5
Input number :
6
Input number :
7
Input number :
8
Input number :
9
Queue Full !
Input number :
0
1
Input number :
0
2
Input number :
0
3
Input number :
0
4
Input number :
0
5
Input number :
0
6
Input number :
0
7
Input number :
0
8
Input number :
0
Queue Empty!
0
Input number :
0
Queue Empty!
0
Input number :

 

2. 원형 큐 작성

앞의 배열의 경우에는 문제점이 있다.

앞의 번호들을 빼고, 다른 번호들을 넣었을 때라고 생각을 해보면,

Head의 위치가 고정되어 있으며, 이의 경우에는 상황에 따라 Head 위치를 지속적으로 반환시켜주어야 한다.

 

[ 코드 ]

#include <iostream>

#define QUEIE_CAPACITY 8 // 큐에 사용되는 배열의 크기 설정

using namespace std;

int queue[QUEIE_CAPACITY];
int head = 0;
int tail = -1;
int queue_size = 0;

void enquene(int n){
	if (queue_size == QUEIE_CAPACITY){
		cout << "Queue Full !" << endl;
		return ;
	}
	tail = (tail+1) % QUEIE_CAPACITY; // tail 증가
	queue_size++;
	queue[tail] = n;
}

int dequeue(){
	int r;
	if (queue_size ==0){
		cout << "Queue Empty!" << endl;
		return 0;
	}

	r = queue[head];
	head = (head+1) % QUEIE_CAPACITY;
	queue_size--;
	return r;
}

int main(void){
	int number, r;
	do {
		cout <<"Input number :" << endl;
		cin >> number;

		if (number >0){
			enquene(number);
		}

		else if (number ==0){
			r = dequeue();
			cout << r << endl;
		}
	}
	while (number >=0);

	return 0;
}

[ 결과 ]

tot4766@tot4766:~/main/코딩/c++/알고리즘$ ./a.out
Input number :
1
Input number :
2
Input number :
3
Input number :
4
Input number :
0
1
Input number :
0
2
Input number :
4
Input number :
5
Input number :
0
3
Input number :
0
4
Input number :
0
4
Input number :
0
5
Input number :
0
Queue Empty!
0
Input number :