[C++]원형큐 구현, 줄서기 예시

큐는 가장 먼저 입력한 자료를 가장 먼저 출력하고 싶을 때 사용한다.

 

정류장에서, 사람들이 줄지어 서서 기다리다가

버스가 오면 순서대로 타는 예의범절을 생각하면 된다.

 

큐를 구현하는 기본 idea는

배열 내 head(처음 선 사람)와 tail(마지막에 선 사람) 인덱스을 잡고

enqueue(줄이 길어지는 상태) 할 때마다 tail++;

dequeue(앞사람부터 버스에 타서 줄이 짧아지는 상태) 할 때마다 head++;을 하는 것이다.

하지만 배열을 아주 크게 잡지 않는 경우, 큐의 배열 크기 마지막까지 head가 도달하여

앞쪽의 빈 배열(head가 거쳐지나간)들을 재활용할 수 없어 메모리낭비가 심한 편이다.

 

그러므로 원형큐를 쓴다면 선형 큐에 비하여

동일한 배열이지만 꾸준하게 head가 거쳐지나간 인덱스들을 재활용할 수 있어 메모리 활용 측면에서 더 좋다.

원형큐의 idea는 선형큐의 처음과 끝이 이어져 있다고 생각하는 것이다.

그럼 한 줄이었던 큐가 강강술래를 하듯 원을 이루게 된다.

enqueue를 하든 dequeue를 하든

잡아놓은 배열 크기, 상상 속 원 안에서 인덱스를 옮기면서 계속 빙글빙글 돌아가게끔 만들어주면 된다.

enqueue를 할 때 tail++;대신에 tail = (tail + 1) % Queue_capacity;

dequeue를 할 때 head++;대신에 head = (head + 1) % Queue_capacity;

로직을 쓰는 것이 핵심이다.

 

 

#include <iostream>

using namespace std;

#define Queue_capacity 10

int queueLine[Queue_capacity];
int head = 0;
int tail = -1;
int queue_size = 0;

void enqueue(int n)
{
	if (queue_size == Queue_capacity)
	{
		cout << "Queue_full" << '\n';
		return;
	}
	tail = (tail + 1) % Queue_capacity;
	queue_size++;
	queueLine[tail] = n;
}

int dequeue()
{
	int r;
	if (queue_size == 0)
	{
		cout << "Queue_empty" << '\n';
		return 0;
	}
	r = queueLine[head]; 
	head = (head + 1) % Queue_capacity;
	queue_size--;
	return r;
}

int main() {
	int number, r;
	do {
		cout << "input number: ";
		cin >> number;
		if (number > 0)enqueue(number);
		else if (number == 0)
		{
			r = dequeue();
			cout << r;
		}
	} while (number >= 0);
	return 0;
}