[C++] 큐 Queue 구현 방법 코드

큐 Queue 는 먼저 줄 선 사람이 맛집 먼저 들어가고 늦게 온 사람이 늦게 들어가는 원리의 자료구조이다.

다르게 말하면, 

한 쪽 끝(rear)에선 삽입만 하고, 다른 한 쪽 끝(front)에선 삭제만 하는 

사람으로 따지면 마치 입(음식 삽입)과 응꼬(음식 배출) 같다고 보면 된다.

먼저 들어간 음식이 지금 뱃속 어디에 있는지는 확인할 수 없다. 

<예시>

Queue는 컴퓨터에서 CPU 관리 방법에 사용되는 자료구조다. 

CPU는 스케줄링할 때 FCFS(First come first served) 방식으로 먼저 Ready Queue에 도착한 프로그램 또는 작업 순서대로 CPU가 할당받아 일을 한다.

 

이제는 진짜 코드를 짜야 할 시간이다. 

처음에 rear와 queue가 -1이 되게 설정해서 queue가 비어있는 상태로 만들어준다.

queue에서 삽입 연산이 발생하면, rear 변수가 +1이 되고

queue에서 삭제 연산이 발생하면 front 변수가 +1이 된다.

먼저 intQueue 클래스를 정의하면 아래와 같다.

#pragma once
#include <iostream>
using namespace std;
typedef int element;
constexpr auto QUEUE_SIZE = 5;

class intQueue {
	element rear;
	element front;
	element buf[QUEUE_SIZE];

public:
	intQueue() : rear(-1), front(-1) {
		for (int i = 0; i < QUEUE_SIZE; i++) {
			buf[i] = -1;
		}
		cout << "Queue is created! GO! " << endl;
		printQueue();
	}

	void printQueue() const {
		for (int i = 0; i < QUEUE_SIZE; i++) {
			cout << "[" << buf[i] << "]";
			if (front == i) {
				if (rear == i)
					cout << " <- front & rear ";
				else
					cout << " <- front ";
			}
			else if (rear == i)
				cout << " <- rear ";
			cout << endl;
		}
		cout << endl;
	}

	bool chkEmpty() const {
		if (rear == front)
			return true;
		else
			return false;
	}

	bool chkFull() const {
		if (rear >= QUEUE_SIZE - 1)
			return true;
		else
			return false;
	}

	void addQueue(element tmp) {
		if (chkFull() == true)
			cout << "Queue is full ! " << endl;
		else {
			buf[++rear] = tmp;
			cout << tmp << " is added to Queue! " << endl;
		}
	}

	element delQueue() {
		if (chkEmpty() == true) {
			cout << "Queue is empty ! " << endl;
			return 0;
		}
		else {
			element temp = buf[++front];  //처음에 -1이였기 때문에~ 1 더해줘야한다.
			cout << temp << " is removed from Queue! " << endl;
			buf[front] = -1;
			return temp;
		}
	}

};

 

이걸 이용하기 위해 main함수를 정의하면 아래와 같다. 이번에도 꽉 찬 경우와 텅 빈 경우를 보여주기 위해 극단적으로 코드를 구성했다 ㅎ.

#include <iostream>
#include "intQueue.h"
using namespace std;

int main()
{
	intQueue qoo;
	qoo.addQueue(4);
	qoo.printQueue();
	qoo.addQueue(6);
	qoo.printQueue();
	qoo.addQueue(8);
	qoo.printQueue();
	qoo.addQueue(10);
	qoo.printQueue();
	qoo.addQueue(40);
	qoo.printQueue();
	qoo.addQueue(100);
	qoo.printQueue();

	for (int i = 0; i < 6; i++) {
		qoo.delQueue();
		qoo.printQueue();
	}

	qoo.addQueue(100);
	qoo.printQueue();

	return 0;
}

실행결과 콘솔창은 아래와 같다.

위의 실행 결과에서 이상한 점이 있다. 마지막에 queue가 비었다고 하자말자 바로 뒤에 queue가 꽉 찼다고 얘기한다. queue에서 삽입과 삭제를 반복하다보면 front와 rear가 처음 위치에서 벗어나 만나는 순간이 있다. 삽입했던 게 전부 삭제된 경우다. 그런데 최악의 경우 queue에 처음에 할당한 크기 전체를 사용해서 삽입하고 삭제를 하면 front와 rear가 queue의 맨 끝을 가리키면서 더 이상 삽입을 할 수도 없고 삭제를 할 수도 없는 상태가 된다. rear가 더 커질 곳이 없어서 삽입도 못하고 아무 데이터도 없으니 삭제도 안된다. 이렇게 메모리 공간이 낭비된다고 볼 수도 있다. 

위의 main() 함수에서도 전부 삽입하고 삭제한 다음에 

qoo.addQueue(100);
qoo.printQueue();

이 코드를 넣었더니 꽉차서 더이상 삽입하지 못한다고 결과를 내는 것으로 확인할 수 있다.

 

그래서 프로그래머들이 고안한 방법이, 원형 큐다. 

입구과 출구 부분을 연결시켜서 텅 비었지만 rear가 이미 끝에 도달해서 사용하지 못하는 공간을 활용하게끔 한다. 

ref: geeksforgeeks

 

꽉 차지 않았지만 rear의 위치 때문에 꽉 찬 상태가 되면 다시 앞쪽에서 삭제를 하며 비워놓은 공간을 rear의 뒤로 연결시켜서 사용하는거다.

훨씬 메모리 효율 면에서 좋지만 단점이 있다.

rear == front 가 되는 지점이 두 경우에서 발생한다: 1) 진짜로 꽉 찬 경우, 2) 텅 빈 경우

그래서 이 두 경우를 구분할 수 있는 코드를 추가해서 보완하여 써야하니 좀 귀찮을 수 있다.

 

오늘은 여귀꽈쥐~