55일차. Queue_by_linkedlist, Tree

Queue_by_LinkedList

큐는 선형 데이터 저장방식 중 하나로, FIFO구조를 따르며, 선입선출 방식으로 데이터를 기입하고 호출하게 된다.

이러한 큐 구조를 리스트 방식으로 제작할 수 있다.

 

이러한 큐의 저장방식은 연결리스트 를 통하여 구현하고, Queue라는 Class를 만들어서, 전체 큐의 사이즈, 연결된 부위, 삭제, 기입, 추출 등의 작업을 수행한다.

---

#include <iostream>

using namespace std;

template<typename T>
class Queue
{
public:
	struct Node
	{
		T Data;
		// 단일연결 리스트 를 통해 구현
		Node* Next;
		//큐 에서는 넣고 빼고 지우고 가능하다. 구현한다.
	};

private:
	int count = 0;
	// 보관 개수

	Node* front = NULL;// 가장 앞 변수 만들고 NULL로 초기화
	//Q 는 FIFO 구조 이기 때문에 front는 빼낼 값.
	Node* rear = NULL;

public:
	Queue() {}

	~Queue()
	{

	}

	void Enqueue(Node* node)
	{
		if (front == NULL)
		{
			// 비어있는 경우 에는,
			front = node;
			rear = node;
			// 처음과 끝을 한개의노드로 정해준다.
			count++; // count 에 1을 해서 1개라고 표시

			return;
		}

		rear->Next = node; // 한개 추가하면, 뒤의 다음값은, node가 되어야 한다.
		rear = node;// 뒤를 node로 설정해준다.

		count++;
	}

	Node* Dequeue()
	{
		// 노드를 제거하고 반환하는 형식을 만든다.
		Node* node = front;// 큐에서 제거해서 반환될 노드
		if (front->Next == NULL) // 큐에 남은 값이 없을 경우.
		{
			front = rear = NULL;
		}
		else
		{
			front = front->Next; // 큐가 한개초과 일 경우, Next를 front로 넣어준다.
		}

		count--;

		return node;
	}

	int Size() { return count; }

	bool IsEmpty() {
		return front == NULL; // 비어있는지 확인
	}
public:
	static Node* CreateNode(T data)
	{
		Node* node = new Node();
		node->Data = data;
		node->Next = NULL;

		return node;
	}

	static void DestroyNode(Node** node)
	{
		delete* node;
		*node = NULL;
	}
};

int main()
{
	Queue<int> queue;
	queue.Enqueue(Queue<int>::CreateNode(10));
	queue.Enqueue(Queue<int>::CreateNode(20));
	queue.Enqueue(Queue<int>::CreateNode(30));

	cout << "Size : " << queue.Size() << endl;

	while (queue.IsEmpty() == false)
	{
		Queue<int>::Node* node = queue.Dequeue();
		cout << "Dequeue : " << node->Data << endl;

		Queue<int>::DestroyNode(&node);
	}
	return 0;
}

위 방식으로 Queue를 직접 구현해줄 수 있다.

---

Tree

트리구조는, 기본적인 비선형 데이터 저장방식으로써, 계층적인 데이터를 표현하기 위해 사용된다.

노드들이 부모 - 자식 관계로 연결되어 있으며, 최상위 노드로부터 파생되어 내려온다.

 

트리구조의 장점

• 데이터의 구조와 관계를 직관적으로 이해할 수 있다.
• 데이터의 삽입, 삭제 검색이 매우 빠르게 이루어진다.
• 정렬, 탐색, 필터링 등의 작업에 유용하다.

 

트리구조의 단점

• 데이터의 삽입, 삭제 시에 트리구조의 재정렬이 필요하기 때문에 추가작업이 필요할 수 있다.
• 트리구조를 메모리에 저장하기 위해 포인터 구조를 사용할 경우, 추가적인 메모리공간을 사용한다.
• 트리구조가 변경될 경우, 전체 트리구조를 변경해야하는 번거로움이 있다.

---

#include <iostream>
#include <stack>
#include <queue>
// 기본적인 트리구조 구축
using namespace std;

template<typename T>
class Tree
{
public:
	struct Node
	{
		T Data;

		Node* LeftChild;
		Node* RightSibling;
		~Node()
		{
			Data = 0;

			LeftChild = NULL;
			RightSibling = NULL;
		}
	};
public:
	stack<Node*>* Stack() { return &stack; }
	queue<T>* Queue() { return &queue; }
private:
	queue<T> queue;
	// 출력하는데 활용
	stack<Node*> stack;
	// 트리노드 순회, 노드 삭제하는데 활용
public:
	static Node* CreateNode(T data)
	{
		Node* node = new Node();
		node->Data = data;
		node->LeftChild = node->RightSibling = NULL;

		return node;
	}

	static void DestoryNode(Node** node)
	{
		delete* node;
		*node = NULL;
	}
public:
	void Addchild(Node* parent, Node* child)
	{
		if (parent->LeftChild == NULL)
		{
			parent->LeftChild = child;
			
			return;
		}

		Node* node = parent->LeftChild;
		
		while (node->RightSibling != NULL)
		{
			node = node->RightSibling;
			// 노드의 오른쪽으로 계속 이동
		}

		node->RightSibling = child;
		// 계속 이동한 노드의 최우측끝 에 값을 삽입한다.
	}

	void PrintNode(Node* node, int depth)
	{
		for (int i = 0; i < depth; i++)
			cout << "-";

		cout << node->Data << endl;
		queue.push(node->Data);
		stack.push(node);

		if (node->LeftChild != NULL) // leftChild가 있는지 확인 있다면, 제귀
			PrintNode(node->LeftChild, depth + 1);

		if (node->RightSibling != NULL) // 오른쪽이 존재하는지 확인, 있다면 제귀
			PrintNode(node->RightSibling, depth);
	}
};

int main()
{
	Tree<char> tree;

	Tree<char>::Node* A = Tree<char>::CreateNode('A');
	Tree<char>::Node* B = Tree<char>::CreateNode('B');
	Tree<char>::Node* C = Tree<char>::CreateNode('C');
	Tree<char>::Node* D = Tree<char>::CreateNode('D');
	Tree<char>::Node* E = Tree<char>::CreateNode('E');
	Tree<char>::Node* F = Tree<char>::CreateNode('F');
	Tree<char>::Node* G = Tree<char>::CreateNode('G');
	Tree<char>::Node* H = Tree<char>::CreateNode('H');
	Tree<char>::Node* I = Tree<char>::CreateNode('I');
	Tree<char>::Node* J = Tree<char>::CreateNode('J');
	Tree<char>::Node* K = Tree<char>::CreateNode('K');

	tree.Addchild(A, B);
	tree.Addchild(B, C);
	tree.Addchild(B, D);
	tree.Addchild(D, E);
	tree.Addchild(D, F);

	tree.Addchild(A, G);
	tree.Addchild(G, H);

	tree.Addchild(A, I);
	tree.Addchild(I, J);
	tree.Addchild(I, K);

	tree.PrintNode(A, 0);

	while (tree.Queue()->empty() == false)
	{
		cout << tree.Queue()->front() << endl;
		tree.Queue()->pop();
	}
	cout << endl << endl;

	while (tree.Stack()->empty() == false)
	{
		Tree<char>::Node* node = tree.Stack()->top();
		tree.Stack()->pop();

		Tree<char>::DestoryNode(&node);
	}

	return 0;
}

위 방식대로 트리구조를 직접 제작하여 사용할 수 있다.