[C++] 자료구조 종합 정리

 

// 자료구조 //
// 대규모 데이터들을 체계적으로 관리하고 활용에 용이하게 하는것이 목적
// 즉, 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.
// 기본적인 7가지 자료구조 : 배열(Array), 큐(Queue), 스택(Stack), 링크드리스트(LinkedList), 해시 테이블(Hash Tables), 그래프(Graph), 트리(Tree)
// 추가적으로 동적배열의 대표로 벡터(vector)가 있다.

// 배열(정적배열) //
// 배열은 생성시 설정된 셀의 수가 고정되고 각 셀에는 인덱스 번호가 부여된다. 
// 배열을 활용 시 부여된 인덱스를 통해 해당 셀 안의 데이터에 접근한다.
// 장점 : 원하는 데이터를 효율적으로 탐색 및 활용, 정렬에 용이하다 / 단점 : 데이터를 저장 할 수 있는 메모리 크기가 고정.

// 벡터(동적배열) //
// 동적배열은 배열의 크기를 미리 정하지 않고 자료의 개수가 변함에 따라 배열의 크기가 변경된다.
// 배열과 벡터의 차이점은 '배열은 크기가 고정, 벡터는 크기가 동적으로 변한다'는 것이다. 만약 저장할 데이터 개수를 미리 알수없다면 벡터가 낫다.

// 스택 //
// 스택은 순서가 보존되는 선형 데이터 구조유형이다. 
// 가장 마지막 요소(=가장 최근 요소)부터 처리하는 LIFO매커니즘이다.
// 장점 : 빠른 런타임 / 단점 : 가장 최신 요소부터 처리한다. 한번에 하나의 데이터만 처리
// 사용예시) 웹 브라우저의 뒤로가기 버튼, 계산기같은 수식계산, 수식 괄호 검사

// 큐 //
// 가장 먼저 입력된 요소부터 처리하는 FIFO매커니즘이다.
// 직관적으로 줄서기를 떠올리면 된다.
// 장점 : 빠른 런타임 / 단점 : 가장 오래된 요소만 가져온다. 한번에 하나의 데이터만 처리
// 사용예시) 최근사용문서, 은행업무, 인쇄작업 대기목록, 버퍼(Buffer)

// 연결 리스트 //
// 앞의 세 구조와 달리 메모리에 있는 데이터의 물리적배치를 사용하지 않는 데이터구조다.
// index나 위치보다 '참조 시스템'을 사용한다.
// 각 요소는 '노드'라는 것에 저장되며, 다음 노드연결에 대한 포인터 또는 주소가 포함된 또 다른 노드에 저장한다.
// 모든 노드가 연결된 때까지 반복이 돼서 노드의 연결로 이루어진 자료구조다.
// 장점 : 새로운 요소의 추가와 삭제가 용이하다. 메모리를 더 효율적으로 쓸 수 있어 대용량 데이터 처리에 적합하다.
// 단점 : 배열보다 메모리를 더 사용한다. 처음부터 끝까지 순회하기 때문에 원하는 값을 비효율적으로 처리한다.
// 사용예시) 음악 플레이어, 이미지 뷰어, 갤러리, 데이터를 연속적으로 빠르게 삽입 및 제거가 필요할 때

// ****벡터외 연결리스트의 차이점은 '백터는 중간삽입시 원소를 밀어내지만, 리스트는 노드를 연결만 하기때문에 삽입 및 삭제 부분에서 시간복잡도의 우위를 가진다'입니다.
// 벡터는 동적배열이므로 새 공간이 할당되고 데이터를 추가할때 추가하고 싶은 값 다음의 데이터들이 한칸씩 뒤로 옮겨지므로 연산이 많아져서 비효율적이다

// ****추가나 삭제가 빈번히 이루어질 대용량의 자료구조를 갖을때는 배열(arrayed list)보다 링크드리스트(Linked list)를 사용해야한다. 
// 예시로 인벤토리를 구현할때는 인벤토리 내 개수가 한정적으로 딱 정해져있을땐 배열을 쓰는게 낫지만, 일반적인 경우의 인벤토리를 구현할때는 링크드리스트를 쓰는게 낫다.

* 아래 각 구조들의 코드에 대한 자세한 부연설명은 개념편과 응용편에 세부적으로 쪼개어 잘 설명해 두었으니 참고바람!

class Node
{
public:
	int value;
	Node* next = nullptr;
	Node* prev = nullptr;

};

1. 큐

class Queue
{
private:
	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;
public:
	void Enqueue(int value);	// 넣는거
	int Dequeue();				// 빼는거
	int GetSize();				// size 게터
	bool IsEmpty();				// 비어있는지 확인
	void Show();				// 전체 출력
};

void Queue::Enqueue(int value)
{
	Node* newNode = new Node();
	newNode->value = value;
	size++;

	if (IsEmpty())
	{
		head = newNode;
		tail = newNode;
	}
	else
	{
		tail->next = newNode;
		newNode->prev = tail;
		tail = newNode;
	}
}
int Queue::Dequeue()
{
	Node* temp = head;
	int result = head->value;

	if (head == tail)
	{
		head = nullptr;
		tail = nullptr;
	}
	else
	{
		head = head->next;
	}
	size--;
	delete temp;
	return result;
}
int Queue::GetSize()
{
	return size;
}
bool Queue::IsEmpty()
{
	if (head == nullptr)
		return true;
	else
		return false;
}
void Queue::Show()
{
	Node* current = head;
	while (current != nullptr)
	{
		cout << current->value << endl;
		current = current->next;
	}
}

2. 스택

class Stack
{
private:
	Node* head = nullptr;
	Node* tail = nullptr;
	int size = 0;
public:
	void Push(int value);	// 넣는거
	int Pop();				// 빼는거
	int GetSize();			// size게터
	bool IsEmpty();			// 비어있는지 확인
	void Show();			// 전체 출력
};

void Stack::Push(int value)
{
	Node* newNode = new Node();
	newNode->value = value;
	size++;

	if (IsEmpty())
	{
		head = newNode;
		tail = newNode;
	}
	else
	{
		tail->next = newNode;
		newNode->prev = tail;
		tail = newNode;
	}
}
int Stack::Pop()
{
	int result = tail->value;

	if (head == tail)
	{
		delete head;
		head = nullptr;
		tail = nullptr;
	}
	else
	{
		tail = tail->prev;
		delete tail->next;
	}
	size--;
	return result;
}
int Stack::GetSize()
{
	return size;
}
bool Stack::IsEmpty()
{
	if (head == nullptr)
		return true;
	else
		return false;
}
void Stack::Show()
{
	Node* prevTail;
	Node* tempTail = tail;

	while (tempTail != head)
	{
		prevTail = head;
		cout << tempTail->value << endl;
		while (prevTail->next != tempTail)
		{
			prevTail = prevTail->next;
		}
		tempTail = prevTail;
	}
	cout << tempTail->value << endl;
}

3. 연결리스트

class LinkedList
{
	Node* head = nullptr;
	Node* tail = nullptr;
	Node* prev = nullptr;
	int size = 0;
public:
	void AddNode(int value);				// 맨뒤에 추가
	void AddNode(int value, int position);	// position위치에 추가
	void RemoveNode(int position);		    // position위치에 삭제
	int SerchValue(int value);				// value를 찾아 position반환
	void Show();							// 전체 출력
	int GetSize();							// size게터
	bool IsEmpty();							// 비어있는지 확인
	~LinkedList();							// 클래스소멸자
	Node* At(int position);					// 해당 위치의 노드를 반환
};

void LinkedList::AddNode(int _value)
{
	Node* newNode = new Node();
	newNode->value = _value;
	size++;

	if (IsEmpty())
	{
		head = newNode;
		tail = newNode;
	}
	else
	{
		tail->next = newNode;
		tail = newNode;
	}
};
void LinkedList::AddNode(int _value, int position)
{
	if (position > size)
	{
		AddNode(_value);
		return;
	}
	Node* newNode = new Node();
	newNode->value = _value;

	size++;
	Node* prevlnsertPos = At(position - 1);

	newNode->next = prevlnsertPos->next;
	prevlnsertPos->next = newNode;
};
void LinkedList::RemoveNode(int position)
{
	Node* prevRemovePtr;
	Node* removePtr;

	prevRemovePtr = At(position - 1);
	removePtr = prevRemovePtr->next;

	prevRemovePtr->next = removePtr->next;
	delete removePtr;
};
int LinkedList::SerchValue(int value)
{
	int position = 0;
	Node* current = head;
	for (int i = 0; i < size; i++)
	{
		if (value == current->value) { position = i; break; }
		else { position = -2147483647; }
		current = current->next;
	}
	return position;
};
void LinkedList::Show()
{
	Node* current = head;
	while (current != nullptr)
	{
		cout << current->value << endl;
		current = current->next;
	}
};
int LinkedList::GetSize()
{
	return size;
};
bool LinkedList::IsEmpty()
{
	if (head == nullptr)
	{
		return true;
	}
	else
	{
		return false;
	}

};
LinkedList::~LinkedList()
{
	Node* current = head;
	Node* temp;
	while (current != nullptr)
	{
		temp = current;
		current = current->next;
		delete temp;
	}
	delete current;
}
Node* LinkedList::At(int position)	// 해당 위치의 노드를 반환
{
	if (position <= 0)
	{
		return head;
	}
	else if (position >= size)
	{
		return tail;
	}
	else
	{
		Node* current = head;
		for (int i = 0; i < position; i++)
		{
			current = current->next;
		}
		return current;
	}
}

4. main()

- 배열, 벡터, 큐, 스택, 연결리스트를 선언하고 정의할 수 있다

- 서로 다른 특징을 가지고 있는 자료구조로서 어떤 상황에서 쓰이는것이 유리한지 이번시간에 공부할 수 있었다. 

void main()
{
	// 배열 //
	int scores[] = { 70, 20, 90, 0, 80 };
	int maxValue = 0;
	int maxIndex = 0;

	// sizeof
	cout << "배열의 타입 크기 : " << sizeof(int) << endl;
	cout << "배열의 전체 크기 : " << sizeof(scores) << endl;
	cout << "첫번째 원소 크기 : " << sizeof(scores[0]) << endl;
	cout << "배열 원소의 개수 : " << sizeof(scores) / sizeof(scores[0]) << endl;
	for (int i = 0; i < 5; i++)
	{
		if (scores[i] > maxValue)
		{
			maxValue = scores[i];
			maxIndex = i + 1;
		}
	}
	cout << "최고 값 : " << maxValue << endl;
	cout << "최고 값의 위치 : " << maxIndex << "번째" << endl;
	cout << "========================" << endl;

	// 벡터 //
	// push_back(), insert(), erase(), size() 등이 자주 쓰인다.
	// vector<데이터타입> 변수명;
	vector<int> intVec;
	// vector<int> intVec(10);	생성자가 있을경우 값(10)만큼 10개의 공간을 미리 확보한다
	// push_back(값) : 가변배열 vector에 요소를 추가해준다 따라서 총 13개의 공간확보
	// 많이 쓸수록 과부화가 발생하기 때문에 유의하자~~
	intVec.push_back(1);
	intVec.push_back(2);
	intVec.push_back(3);
	intVec.push_back(4);
	// begin()은 반복자의 첫번째를 가져온다. begin() + i 하면 i번째의 위치를 말한다.
	// insert(추가하고싶은 위치, 추가할 값) : 반복자 위치에 값을 추가한다.
	intVec.insert(intVec.begin() + 1, 5);
	// erase(삭제하고 싶은 위치) : 반복자위치에 요소를 제거한다.
	intVec.erase(intVec.begin() + 0);
	cout << "intVec벡터 속 원소의 개수 : " << intVec.size() << endl;
	for (int i = 0; i < intVec.size(); i++)
	{
		cout << intVec[i] << endl;	// 벡터는 동적배열이기때문에 인덱스로 접근이 가능함
	}
	cout << "========================" << endl;

	// 큐 //
	Queue intQueue;

	intQueue.Enqueue(10);
	intQueue.Enqueue(20);
	intQueue.Enqueue(30);
	intQueue.Enqueue(40);
	while (intQueue.IsEmpty() != true)
	{
		cout << intQueue.Dequeue() << endl;
	}
	cout << "====위 큐, 아래 스택====" << endl;
	// 스택 //
	Stack intStack;

	intStack.Push(10);
	intStack.Push(20);
	intStack.Push(30);
	intStack.Push(40);
	intStack.Show();
	cout << "====위 스택, 아래 링크드리스트====" << endl;
	// 링크드리스트 //
	LinkedList link;

	link.AddNode(10);
	link.AddNode(20);
	link.AddNode(30);
	link.AddNode(40);
	cout << "총 길이 : " << link.GetSize() << endl;
	link.AddNode(50, 3);
	link.RemoveNode(100);
	link.Show();
}

출력 결과