큐(Queue)와 덱(Deque) - 7장

큐(Queue)

스택이 가장 나중에 저장된 값을 먼저 뽑아오는 후입선출(LIFO)의 구조였다면

큐는 가장 먼저 저장된 값을 먼저 뽑아오는 선입선출(FIFO)의 구조이다.

 

큐를 배열기반으로 구현했을때 선입선출의 구조가 되기 위해서는

 

1. 데이터가 들어갈(enqueue) 인덱스값을 기억할 rear변수.

2. 데이터를 뽑아(dequeue)올 인덱스값을 기억할 front변수.

 

 

실제로 배열에 있는값이 사라지지 않는다는것은 알것이다.

 

처음 FR이 0번째 인덱스를 가리킬때 데이터가 들어오면 R이 가리키는 인덱스에 요소를 집어넣고

한칸 오른쪽으로 옮긴다. 

그리고 데이터를 뽑아올땐 F가 가리키는 인덱스에 요소를 빼오고 한칸 오른쪽으로 옮긴다.

 

이것이 배열기반 큐의 구조.

 

하지만 이렇게 단순히 끝낼수는 없는게 

위의 그림과 같이 분명히 배열에 데이터를 저장할 공간이 남아있지만 다음 데이터를 저장할려고하니 막혀서 삽입이 불가능한 상황인것.

 

이 때 배열기반 큐는 원형(환형)큐로 구현한다.

 

즉 이름에서도 알 수 있듯이 배열을 둥근형태. 원형의 형태라고 생각하고 F와 R을 움직이자는 것.

 

끝은 아니다.

일반적으로 생각했을땐 F와 R을 통해 환형큐의 가득찬(Full)상태와 빈(Empty)상태를 구분하기는 어렵다.

 

이에 대한 해결책으로 배열의 길이가 N이라면 데이터가 N - 1개가 채워졌을 때, 이를 꽉찬 것으로 간주한다.

 

 

환형 큐의 구현은 데이터를 집어넣고 R을 움직이고, 데이터를 반환하고 F를 움직이는게 아니다.

 

"enqueue 연산 시, R이 가리키는 위치를 한 칸 이동시킨 다음, R이 가리키는 위치에 데이터를 저장"

"dequeue 연산 시, F가 가리키는 위치를 한 칸 이동시킨 다음, F가 가리키는 위치에 데이터를 반환"

 

 

이렇게. 우리는 원형 큐의 상태를 이렇게 나타낸다.

 

1. 원형 큐가 텅빈상태 - F와 R이 동일한 위치를 가리킨다

2. 원형 큐가 꽉찬상태 - R이 가리키는 위치의 앞이 F가 가리킨다.

 

이제 배열기반의 큐(환형큐)의 코드를 구현해본다.

template<typename T>
class Queue
{
public:
	Queue();
	~Queue();
	inline int GetSize() const;
	inline bool IsEmpty() const;
	bool Enqueue(const T& item);
	T Dequeue();
	int NextPosIdx(int idx);
private:
	enum { MAX = 100 };
	T*  m_queueArr;
	int m_front;
	int m_rear;
	int m_size;
};

 

 

구현 코드

template<typename T>
Queue<T>::Queue() : m_queueArr(new T[MAX]), m_front(0),m_rear(0),m_size(0)
{

}
template<typename T>
Queue<T>::~Queue()
{
	delete[] m_queueArr;
}
template<typename T>
int Queue<T>::GetSize() const
{
	return m_size;
}

template<typename T>
bool Queue<T>::IsEmpty() const
{
	if (m_front == m_rear)
		return true;
	return false;
}

template<typename T>
int Queue<T>::NextPosIdx(int idx)
{
	if (idx == MAX - 1) // 배열의 끝일경우.
		return 0; 
	return idx + 1;
}
template<typename T>
bool Queue<T>::Enqueue(const T& item)
{
	// 가득찬상태
	int nextPos = NextPosIdx(m_rear);
	if (nextPos == m_front) // 가득찬 상태
	{
		return false;
	}

	m_rear = nextPos; // 한칸 이동후
	m_queueArr[m_rear] = item; // 삽입
	m_size++;
	return true;

}
template<typename T>
T Queue<T>::Dequeue()
{
	// 빈 상태.
	if (IsEmpty())
		return -1;

	m_front = NextPosIdx(m_front);
	m_size--;
	return m_queueArr[m_front];
}

 

 

덱(Deque)

큐가 먼저 들어온 데이터가 먼저나가는 구조(FIFO). 

 

덱의 개념을 쉽게 이해하기 위해

큐가 데이터를 뒤로 넣고 앞으로 빼는 자료구조라고 하면.

 

덱은 앞으로도 뒤로도 넣을 수 있고, 앞으로도 뒤로도 뺄 수 있는 자료구조이다.

 

즉 덱의 기능에서 앞으로 넣기, 뒤로 넣기, 앞에서 빼기, 뒤에서 빼기의 기능이 존재한다.

 

덱은 양방향 연결리스트로 head, tail로 처음과 끝을 가리키게 하면 쉽게 구현이 가능하다.