7. 원형큐(CircularQueue) -b. 배열 기반

원형큐

  # 일반적인 큐가 시작과 끝이 있는 선분의 형태라면 원형큐는 시작과 끝을 이어 고리형태를 이루게 한 구조이다.

배열 기반 큐의 문제점

  # 배열 기반의 큐를 선형큐로 만들면 문제가 되는 것이 두가지 있다.

  # 첫째는 front를 항상 0번 인덱스로 유지하기 위해서는 Remove때마다 데이터를 이동시켜야 한다는 것이다. 

  # 이를 해결하기 위해서는 Remove시에 front의 인덱스를 다음 인덱스로 이동시켜야만 한다.

  # 두번째 문제는 Add와 Remove를 반복할 시 Front와 Rear의 위치가 배열의 뒷부분으로 이동되어 앞부분에 공간이 있음에도 오버플로우가 발생한다는 것이다.

 배열 기반 큐의 문제 해결 방법

  # 배열 기반의 큐에서 이를 해결하는 방법은 두가지다.

  # 하나는 오버플로우가 발생했을 때 배열 앞쪽에 공간이 있는지 확인하고 즉, front가 0번 인덱스에 있는지 확인하고 아니라면 데이터를 앞으로 이동시켜 주는 것이다.

  # 다른 하나는 큐를 원형으로 만드는 것이다. 이러면 배열의 앞 뒤 구분을 없애므로 앞부분의 빈공간이 남은 빈공간으로 활용될 수 있다.

  # 원형큐를 만드는 것이 데이터를 이동시키는 것보다 훨씬 효율적이므로 여기서는 배열기반의 큐는 원형큐로 제작한다.

배열 기반 원형큐의 ADT

  1. 큐 생성시 큐의 크기를 정해야한다. 

  2. 큐에 데이터를 넣는다. (Add)

     (큐가 가득차 있을때 데이터를 넣으려고 하면 큐 사이즈를 리턴하며 실패한다.)

  3. 큐에서 데이터를 뺀다. (Remove)

     (큐가 비어있을때 데이터를 빼려고 하면 0을 리턴하며 실패한다.)

  4. 큐 맨 앞의 데이터를 확인한다. (Peek)

     (큐가 비어있을 때 데이터를 확인하려고 하면 쓰레기값을 반환하니 주의할 것)

  5. 큐에 들어있는 데이터의 개수를 확인한다. (Count)

 

C++로 기반한 배열 기반 원형큐

#pragma once

template <typename T>
class CircularQueue
{
	T* capacity;
	int iSize;

	int iCount;

	int iFront;
	int iRear;

public:
	int Add(T data);
	int Remove();
	T   Peek();
	int Count();
	int CapacitySize();

public:
	CircularQueue(int size);
	virtual ~CircularQueue();
};


template <typename T>
CircularQueue<T>::CircularQueue(int size)
{
	capacity = new T[size];
	
	iSize = size;
	iCount = 0;

	iFront = 0;
	iRear  = 0;
}

template <typename T>
int CircularQueue<T>::Add(T data)
{
	if (iCount == iSize) {
		return iSize;
	}

	if (iRear == iSize) {
		iRear = 0;
	}

	capacity[iRear++] = data;
	
	return ++iCount;
}

template <typename T>
int CircularQueue<T>::Remove()
{
	if (iCount == 0) {
		return 0;
	}

	if (iFront == iSize) {
		iFront = 0;
	}

	iFront++;

	return --iCount;

}

template <typename T>
T CircularQueue<T>::Peek()
{
	return capacity[iFront];
}

template <typename T>
int CircularQueue<T>::Count()
{
	return iCount;
}

template <typename T>
int CircularQueue<T>::CapacitySize()
{
	return iSIze;
}

template <typename T>
CircularQueue<T>::~CircularQueue()
{
	delete[] capacity;
}