2016/03/23

1. 순환 큐.

1. 순환 큐 클래스.

#include "20160324.h"

void CreateQueue(CircularQueue** _Queue, int _Capacity)
{
#ifdef CPP
	(*_Queue) = new CircularQueue;
	(*_Queue)->tNode = new Node[_Capacity + 1];
#else
	(*_Queue) = (CircularQueue*)malloc(sizeof(CircularQueue));
	(*_Queue)->tNode = (Node*)malloc(sizeof(Node) * (_Capacity + 1);
#endif
	(*_Queue)->nCapacity = _Capacity;
	(*_Queue)->nFront = 0;
	(*_Queue)->nRear = 0;

}

void DestroyQueue(CircularQueue* _Queue)
{
#ifdef CPP
	delete _Queue->tNode;
	_Queue->tNode = NULL;
	delete _Queue;
	_Queue = NULL;
#else
	free(_Queue->tNode);
	_Queue->tNode = NULL;
	free(_Queue);
	_Queue = NULL;
#endif

}

void Enqueue(CircularQueue* _Queue, ElementType _Data)
{
	int nPosition = 0;

	if (_Queue->nRear == _Queue->nCapacity + 1)
	{
		_Queue->nRear = 0;
		nPosition = 0;
	}
	else
		nPosition = _Queue->nRear++;
	_Queue->tNode[nPosition].Data = _Data;

}

ElementType Dequeue(CircularQueue* _Queue)
{
	int nPosition = _Queue->nFront;

	if (_Queue->nFront == _Queue->nCapacity)
		_Queue->nFront = 0;
	else
		_Queue->nFront++;
	return _Queue->tNode[nPosition].Data;

}

int GetSize(CircularQueue* _Queue)
{
	if (_Queue->nFront <= _Queue->nRear)
		return _Queue->nRear - _Queue->nFront;
	else
		return _Queue->nRear + (_Queue->nCapacity - _Queue->nFront) + 1;

}

int IsEmpty(CircularQueue* _Queue)
{
	return (_Queue->nFront == _Queue->nRear);
}

int IsFull(CircularQueue* _Queue)
{
	if (_Queue->nFront < _Queue->nRear)
		return ((_Queue->nRear - _Queue->nFront) == _Queue->nCapacity);
	else
		return ((_Queue->nRear + 1) == _Queue->nFront);

}

2. 메인 클래스.

#include "20160324.h"

#ifdef CPP
using namespace std;
#endif

void main(void)
{
	CircularQueue* Queue;

	CreateQueue(&Queue, 10);

	Enqueue(Queue, 1);
	Enqueue(Queue, 2);
	Enqueue(Queue, 3);
	Enqueue(Queue, 4);

	for (int i = 0; i < 3; ++i)
	{
#ifdef CPP
		cout << "Dequeue : " << Dequeue(Queue) << ", ";
		cout << "Front : " << Queue->nFront << ", Rear : " << Queue->nRear << endl;
#else
		printf("Dequeue : %d, ", Dequeue(Queue));
		printf("Front : %d, Rear : %d\n", Queue->nFront, Queue->nRear);
#endif
	}

	int i = 100;

	while (0 == IsFull(Queue))
		Enqueue(Queue, i++);

#ifdef CPP
		cout << "Capacity : " << Queue->nCapacity << ", Size : " << GetSize(Queue) << endl;
#else
		printf("Capacity : %d, Size : %d\n", Queue->nCapacity, GetSize(Queue));
#endif
	while(0 == IsEmpty(Queue))
	{
#ifdef CPP
		cout << "Dequeue : " << Dequeue(Queue) << ", ";
		cout << "Front : " << Queue->nFront << ", Rear : " << Queue->nRear << endl;
#else
		printf("Dequeue : %d, ", Dequeue(Queue));
		printf("Front : %d, Rear : %d\n", Queue->nFront, Queue->nRear);
#endif
	}
	DestroyQueue(Queue);

}

 

2. 링크드 큐.

1. 링크드 큐 클래스.

#include "20160325.h"

void CreateQueue(LinkedQueue** _Queue)
{
#ifdef CPP
	(*_Queue) = new LinkedQueue;
#else
	(*_Queue) = (LinkedQueue*)malloc(sizeof(LinkedQueue));
#endif
	(*_Queue)->Front = NULL;
	(*_Queue)->Rear = NULL;
	(*_Queue)->nCount = 0;

}

void DestroyQueue(LinkedQueue* _Queue)
{
	while(!IsEmpty(_Queue))
	{
		Node* Pop = Dequeue(_Queue);
		DestroyNode(Pop);
	}

#ifdef CPP
	delete _Queue;
#else
	free(_Queue);
#endif

}

Node* CreateNode(ElementType NewData)
{
#ifdef CPP
	Node* NewNode = new Node;
	NewNode->Data = NewData;
#else
	Node* NewNode = (Node*)malloc(sizeof(Node));
	NewNode->Data = (ElementType)malloc(sizeof(strlen(NewData) + 1);

	strcpy_s(NewNode->Data, sizeof(strlen(NewData) + 1), NewData);
#endif

	NewNode->NextNode = NULL;

	return NewNode;
}

void DestroyNode(Node* _Node)
{
#ifdef CPP
	delete _Node;
	_Node = NULL;
#else
	free(_Node->Data);
	_Node->Data = NULL;
	free(_Node);
	_Node = NULL;
#endif

}

void Enqueue(LinkedQueue* _Queue, Node* _NewNode)
{
	if (NULL == _Queue->Front)
	{
		_Queue->Front = _NewNode;
		_Queue->Rear = _NewNode;
		_Queue->nCount++;
	}
	else
	{
		_Queue->Rear->NextNode = _NewNode;
		_Queue->Rear = _NewNode;
		_Queue->nCount++;
	}

}

Node* Dequeue(LinkedQueue* _Queue)
{
	Node* Front = _Queue->Front;

	if (NULL == _Queue->Front->NextNode)
	{
		_Queue->Front = NULL;
		_Queue->Rear = NULL;
	}
	else
		_Queue->Front = _Queue->Front->NextNode;
	_Queue->nCount--;

	return Front;

}

int IsEmpty(LinkedQueue* _Queue)
{
	return (NULL == _Queue->Front);

}

2. 메인 클래스.

#include "20160325.h"

#ifdef CPP
using namespace std;
#endif

void main(void)
{
	LinkedQueue* Queue;

	CreateQueue(&Queue);

	Enqueue(Queue, CreateNode("aaa"));
	Enqueue(Queue, CreateNode("bbb"));
	Enqueue(Queue, CreateNode("ccc"));
	Enqueue(Queue, CreateNode("ddd"));

#ifdef CPP
	cout << "Queue Size : " << Queue->nCount << endl;
#else
	printf("Queue Size : %d\n", Queue->nCount);
#endif
	Node* Pop;

	while(0 == IsEmpty(Queue))
	{
		Pop = Dequeue(Queue);

#ifdef CPP
		cout << "Dequeue : " << Pop->Data << endl;
#else
		printf("Dequeue : %s\n", Pop->Data);
#endif
		DestroyNode(Pop);
	}
	DestroyQueue(Queue);

}