[Data Structure] Queue

큐(Queue)

• 먼저 들어간 데이터가 먼저 반환되는 FIFO(First-In First-Out) 구조.
• 큐의 구현은 배열, 연결 리스트 등을 이용해 구현 가능하다.
• 일반적인 큐와 circuler queue 등이 존재한다.

Queue 구조

 

큐의 구현은 3가지 형식으로 구현을 해봤다. 

 

1. 연결 리스트를 이용한 큐

 

데이터 구조

struct Queue
{
	int iData;
	Queue* next;
};

 

 

함수

• EnQueue

bool CQueue::EnQueue(int _iData)
{
	bool bRet = false;
	Queue* newNode;

	newNode = (Queue*)malloc(sizeof(Queue));
	if (NULL == newNode)
		return false;
	
	newNode->iData = _iData;

	if (NULL == m_Front)
	{
		m_Front = newNode;
		m_Tail = newNode;
	}
	else
	{
		m_Tail->next = newNode;
		m_Tail = m_Tail->next;
	}
	
	m_iQueueSize++;

	return bRet;
}

• DeQueue

int CQueue::DeQueue()
{
	Queue* node;
	int iData;
	
	if (IsEmpty())
		return -1;

	iData = m_Front->iData;

	if (m_Front == m_Tail)
	{
		free(m_Front);
		free(m_Tail);
		m_Front = m_Tail = NULL;
	}
	else
	{
		node = m_Front;
		m_Front = m_Front->next;
		free(node);
		node = NULL;
	}

	m_iQueueSize--;

	return iData;
}

• IsEmpty

bool CQueue::IsEmpty()
{
	if (NULL == m_Tail)
		return true;
	else
		return false;
}

 

 

2. template 를 이용한 큐

• 함수나 구조는 거의 유사하기 때문에 추가적인 설명은 하지 않겠다.

#pragma once

#include <stdio.h>
#include <malloc.h>

template<typename T>
struct QueueT
{
	T data;
	QueueT<T> *next;
};

template<typename T>
class CQueueT
{
public:
	CQueueT(): m_Front(NULL), m_Tail(NULL), m_iQueueSize(0) {};
	~CQueueT() {};

public:
	bool EnQueueT(T _data)
	{
		bool bRet = false;
		QueueT<T>* newNode;
		
		for (;;)
		{
			newNode = (QueueT<T>*)malloc(sizeof(QueueT<T>));
			if (NULL == newNode)
				break;

			newNode->data = _data;

			if (NULL == m_Front)
			{
				m_Front = newNode;
				m_Tail = newNode;
			}
			else
			{
				m_Tail->next = newNode;
				m_Tail = m_Tail->next;
			}

			m_iQueueSize++;
			bRet = true;

			break;

		}
		
		return bRet;
	}
	T DeQueueT()
	{
		T data;
		QueueT<T>* node;
		
		if (IsEmpty())
			return -1;

		if (m_Front == m_Tail)
		{
			free(m_Front);
			free(m_Tail);
			m_Front = m_Tail = NULL;
		}
		else
		{
			node = m_Front;
			data = m_Front->data;
			m_Front = m_Front->next;
			free(node);
			node = NULL;
		}
		
		m_iQueueSize--;

		return data;
	}
	bool IsEmpty()
	{
		if (NULL == m_Tail)
			return true;
		else
			return false;
	}

private:
	QueueT<T>* m_Front;
	QueueT<T>* m_Tail;
	int m_iQueueSize;
};

 

3. 배열을 이용한 큐 (Circular Queue)

• 역시 큰 틀은 동일하다.
• 배열을 이용하면 리스트를 이용하는 것 보다 속도는 빠를 수 있다.
• 크기 제한이 있다는 것에 있어서 약간의 아쉬움은 있다...
• 보통 Circular Queue를 만들 때, 배열의 마지막 공간을 사용하지 않는다.(상태 구분을 위해) 하지만, 그 공간이 낭비되는 것이 싫어서 모든 공간을 사용할 수 있도록 구현하였다.

함수

• EnQueue

bool CQueueA::EnQueueA(int iData)
{
	bool bRet = false;
	
	if (IsFull())
		return bRet;

	if (IsEmpty())
	{
		m_Front = m_rear = 0;
		m_Queue[m_rear] = iData;
	}
	else 
	{
		if (0 != m_Front && MAX_QUEUE_SIZE == m_rear + 1)
		{
			m_rear = 0;
			m_Queue[m_rear] = iData;
		}
		else
		{
			m_rear++;
			m_Queue[m_rear] = iData;
		}
	}

	return bRet;
}

• DeQueue

int CQueueA::DeQueueA()
{
	int iData;
	
	if (IsEmpty())
		return -1;

	iData = m_Queue[m_Front];

	if (m_Front == m_rear)
		m_Front = m_rear = -1;
	else if (MAX_QUEUE_SIZE - 1 == m_Front)
		m_Front = 0;
	else
		m_Front++;

	return iData;
}

• IsEmpty

bool CQueueA::IsEmpty()
{
	if (-1 == m_Front)
		return true;
	else
		return false;
}

• IsFull

bool CQueueA::IsFull()
{
	if ((0 == m_Front && MAX_QUEUE_SIZE - 1 == m_rear) 
		|| m_rear == (m_Front - 1) % (MAX_QUEUE_SIZE - 1))
		return true;
	else
		return false;
}