선형 Queue 파트
https://velog.io/@hallow0312/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Queue

기존의 선형 Queue 를 다루었을때 배열선형 queue 에서 삽입과 삭제를 할경우
앞부분에 빈자리가 있지만 rear= n-1 인 상태이므로 포화 상태로 인식을 하고 더이상 삽입을 수행하지않게 된다.(배열 선형 queue의 잘못된 포화상태 인식)

이러한 잘못된 포화상태 인식의 해결방법으로 저장된 원소들을 배열의 앞부분을 이동시키는 방법 이있지만 순차자료에서의 이동작업은 연산이 복잡하여 효율성이 떨어지는 단점이 있다.

또다른 해결방법으로 이제 다루어볼 원형 큐가 있다.

원형Queue

원형 Queue 는 1차원 배열을 사용하면서 논리적으로 배열의 처음과 끝이 연결되어 있다고 가정하여 사용을 한다.

코드 구현

front 와 rear 의 위치가 배열의 마지막 index 에서 그 다음자리인 index 0번으로 이동을 시키기위해서 나머지연산자를 사용한다.
첫번째 push 과정을 위해 front 와 rear 를 SIZE-1로 하였다.

#include<iostream>
using namespace std;
#define SIZE 5
template <typename T>

class CircleQueue
{
private:
	int front;
	int rear;
	T buffer[SIZE];

public:
	CircleQueue() //초기화
	{
		front = SIZE - 1;
		rear = SIZE - 1;
		for (int i = 0; i < SIZE; i++)
		{
			buffer[i] = NULL;
		}
	}
	void Push(T data) 
	{
		if (IsFull())
		{
			cout << "Queue is Full" << '\n';
			return;
		}
		else
		{
			rear = (rear + 1) % SIZE; //나머지연산자를 통해 (n-1+1 =SIZE) /SIZE 로 0번인덱스로 감 
			buffer[rear] = data;
		}
	}
	void Pop() //맨앞 제거 
	{
		if (Empty())
		{
			cout << "Release Arr" << '\n';
		}
		else
		{
			front = (front + 1) % SIZE; //0번삭제시 1번이 맨앞 
			buffer[front] = NULL;
		}
	}
	bool IsFull() //가득찼는지 확인
	{
		if (front == (rear + 1) % SIZE)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	bool Empty() //비었는지 확인
	{
		if (front == rear)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
	T& Front()
	{
		return buffer[(front + 1) % SIZE];
	}

};

int main()
{
	CircleQueue <int> circlequeue;

	circlequeue.Push(1);
	circlequeue.Push(2);
	circlequeue.Push(3);
	circlequeue.Push(4);
	circlequeue.Push(5); //Full 되는지 확인


	while (!circlequeue.Empty())
	{
		cout << circlequeue.Front() << '\n';
		circlequeue.Pop();

	}
	circlequeue.Push(1);
	circlequeue.Push(2);
	circlequeue.Push(3);

	while (!circlequeue.Empty())
	{
		cout << circlequeue.Front() << '\n';
		circlequeue.Pop();

	}

	return 0;
}

코드를 보면 원형 큐의 max size 가 5임에도 불구하고 queue 에 들어가는 원소의 수는 4개인것을 학인 할수가 있는데 ,
왜 인지를 확인 하기위해서는 Full 과 Empty 부분을 보면 알수가 있다.

원형 큐에서 IsFull과 IsEmpty 함수를 구분할 때, front == rear 조건을 사용하게 되면, 큐가 비어 있는 상태와 큐가 가득 찬 상태를 혼동할 수 있게된다. 그 이유로 초기 상태에서 front와 rear가 같은 값으로 시작하므로, 두 상태를 구분할 수 없기 때문이다.

그래서 IsFull 함수는 front == (rear + 1) % SIZE 조건을 사용하며, 이 조건은 큐가 한 칸을 남기고 가득 찬 상태를 나타낸다.
이 방식을 사용하면 큐가 비어 있는 상태와 가득 찬 상태를 명확하게 구분할 수 있게 된다.