[자료구조] 큐(Queue) & 원형 큐(Circle Queue)란?

안녕하세요, IT디자이너입니다.

 

이번 포스팅은 큐(Queue) & 원형 큐(Queue)에 관하여 포스팅하도록 하겠습니다.

 

 

- 큐(Queue) 란? 

큐(Queue)는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out)의 구조로 저장하는 형식입니다.

 

또한 Queue의 영어 단어로는 표를 사러 일렬로 늘어선 사람들을로 이루어진 줄을 뜻하기도 합니다.

 

즉, 먼저 줄을 선 사람이 먼저 나갈 수 있는 상황을 연상하면 됩니다.!

 

 

- 큐(Queue)의 front 와 rear 란?

큐(Queue)는 오로지 한쪽에서만 삽입이 이루어지고 다른 한쪽에서는 출력만 가능합니다. 

 

즉, 삽입이 이루어지는 쪽을 "rear" 출력이 이루어지는 쪽을 "front" 라고 합니다. 값을 삽입할 수록 rear 값은 증가하고,

 

또한 값을 출력할 수록 front의 값은 증가합니다.

 

큐(Queue) 자료구조

 

 

- 큐(Queue)의 문제점 

큐(Queue)를 구현을 하고 사용할 때 DeQueue() 함수로 front 위치의 하나의 값을 출력을 하면, front가 한 칸씩 뒤로 밀려나게 되는데, 이럴 경우 큐의 가용범위도 줄어들며, 큐의 재사용 또한 불가능하게 됩니다. 

 

만약에, 억지로 큐의 재사용을 위해 front를 출력하고 front 뒤의 인덱스를 한 칸씩 앞당긴다 하더라도 불필요한 연산이 너무 많아집니다. 예를 들어 인덱스가 1억개라면? 이거는 엄청난 반복 연산을 불러일으키게 됩니다.

 

이러한 문제점을 보안하기 위해 우리는 "원형 큐 (Circle Queue)"를 사용합니다.

 

 

- 원형 큐(Circle Queue) 란?

 

큐의 단점을 보안하기 위해 사용하는 "원형 큐(Circle Queue)" 입니다. 물리적으로는 큐와 동일하게 일직선의 배열로 구성되어 있지만, 논리적으로 배열을 원형으로 재해석한 자료구조입니다.

 

 

원형 큐(Circle Queue)의 특징은 dummy값입니다. front와 rear가 같은 위치에 있을 때 해당 큐가 비어있음을 뜻하며, rear가 front 이전의 위치에 있을 때는 큐가 꽉차 있음을 뜻합니다. 

 

 

- 원형 큐(Circle Queue) 사용 함수

• EnQueue() : rear에서 +1 연산을 한 후 값을 넣는 함수입니다.
• DeQueue() : front +1 연산 후 위치에 있는 요소를 출력하는 함수입니다. 
• Peek() : 다음 출력될 위치에 요소를 확인하는 함수입니다.
• isFull() : 스택이 꽉 찼는지 확인하는 함수입니다.
• isEmpty() : 스택이 현재 비어있는지 확인하는 함수입니다. 

 

 

 

- 원형 큐(Circle Queue) 구현

 

※ 원형 큐의 front와 rear은 배열의 최대 길이를 벗어나지 않기 위해 배열의 길이로 나머지 연산 후 값을 얻어야 합니다.

 

#include <iostream>
#include <Windows.h>

using namespace std;

#define MAX_QUEUE 5

int cQueue[MAX_QUEUE];

int front = 0;

int rear = 0;

bool EnQueue(int val); // 큐에 값을 넣는 함수

bool DeQueue(int *val); // 큐에 값을 출력하는 함수

bool isFull(); // 큐가 꽉 찼는지 확인하는 함수

bool isEmpty(); // 큐가 비었는지 확인하는 함수

bool Peek(int *val); // 다음에 출력될 값을 확인하는 

int main(void){

	int sel; // 메뉴 입력

	int num; // 스택에 값 입력 또는 출력할 때 쓰는 int

	while (1) {
		
		cout << "--------스택--------"<< endl;
		cout << "1.EnQueue "<< endl;
		cout << "2.DeQueue " << endl;
		cout << "3.Peek " << endl;
		cout << "4. 나가기"<< endl;
		cout << "번호 입력 : ";
		cin >> sel;

		cout << endl;
		switch (sel) {
		case 1:
			cout << "값을 입력하세요 : ";
			cin >> num;
			if (EnQueue(num) == false)
				cout << "큐가 꽉 찼습니다." << endl;
			break;
		case 2:
			if (DeQueue(&num) == true) {
				cout << "DeQueue() 결과 : " << num << endl;
			}
			else
				cout << "큐가 비어있습니다. " << endl;
			break;
		case 3:
			if(Peek(&num) == true)
				cout<<"Peek() 결과 : "<< num <<endl;
			else
				cout << "큐가 비어있습니다. " << endl;
			break;
		};

		cout << endl;
		if (sel == 4) {// 4번 입력 시 종료
			cout << "프로그램을 종료합니다." << endl;
			break;
		}
	}

}

bool EnQueue(int val){

	if (isFull() == true) // 큐가 꽉찼으면 isFull 함수는 true를 return
		return false;
	else {

		rear = ++rear % MAX_QUEUE; // 인덱스의 길이로 나누어 최대 길이를 벗어나지 않는다.
		cQueue[rear] = val;
		return true;
	}

}

bool DeQueue(int *val) {
	if (isEmpty() == true) // 스택이 비었으면 true를 return
		return false;
	else {

		front = ++front % MAX_QUEUE; // 인덱스의 길이로 나누어 최대 길이를 벗어나지 않는다.
		*val = cQueue[front];
		return true;
	}
}

bool isFull() {
	if ((rear+1) % MAX_QUEUE == front) // dummy 값 위치에 있을 때 원형 큐는 Full 이다
		return true;
	else
		return false;
}

bool isEmpty() {
	if (front == rear) // rear와 front의 위치가 같으면 비어있다.
		return true;
	else
		return false;
}

bool Peek(int *val) {

	if (isEmpty() == true) {
		return false;
	}
	else {
		*val = cQueue[(front+1) % MAX_QUEUE];
		return true;
	}
}

 

---

이렇게 원형 큐에 대하여 알아보고 구현하는 방법에 대하여 소개해드렸습니다.

 

IT디자이너였습니다.

 

감사합니다.