[PS] 자료구조

Problem Solving에서는 자주 사용되는 자료 구조가 있다.
자료 구조에는 형태와 규칙으로 나뉘어진다.

형태

1. 배열
2. 링크드리스트
3. 트리(이진트리 / 힙트리)
4. 그래프

규칙

1. 스택 / 큐
2. Priority Queue
3. Hash Table
4. Union-Find

자료구조란 어떻게 저장하는지에 따라 달라지게 되는데, 우선 자료구조 규칙 중 기본적인 스택과 큐에 대해 간단히 알아보자.

스택은 데이터 추가/읽기/지우기 모두 윗부분에서 가능하다는 특징이 있다.
큐는 데이터 읽기/지우기는 앞부분에서 가능하고 추가는 뒷부분에서 가능하다는 특징이 있다.

다음과 같은 규칙들은 중간에 존재하는 데이터를 읽을 수가 없고, 중간에 자료를 추가 혹은 삭제할수 없다는 특징들을 공통적으로 가지고있다.

---

다음으로, 자료구조 형태 중 링크드리스트와 그래프에 대해 간단히 알아보자.

링크드리스트는 중간에 노드(자료를 저장하는 최소단위)를 추가 및 삭제가 가능케 하는 형태이다.
그래프는 값 뿐 만 아니라 데이터와 데이터 간의 관계 또한 저장가능한 형태이다.

---

간단한 이론들을 알아봤으면, PS에서는 스택을 어떻게 사용할 수 있는지 알아보겠습니다.
PS에서의 스택은 보통 라이브러리(Lib)를 추가하여 사용하지만, 어떻게 동작되는지를 알아보기 위해서는 라이브러리 사용없이 코드를 우선 작성해보겠습니다.

라이브러리 없이 스택

#include <iostream>
using namespace std;

// 자료구조 범위 지정
int stack[10];
int node = 0;

// 데이터 저장/삭제/읽기 함수 작성
void push(int a) {
	stack[node++] = a;
}

void pop() {
	stack[--node] = 0;
}

int top() {
	return stack[node - 1];
}

int main() {
	
	push(1); // 1
	push(2); // 1 2
	push(3); // 1 2 3
	push(5); // 1 2 3 5
	push(7); // 1 2 3 5 7

	cout << top(); //  7
	pop(); // 7 삭제
	cout << top(); // 5
	pop(); // 5 삭제
	push(4); // 1 2 3 4
	cout << top(); // 4
	
	
	
	return 0;
}

출력

Stack Lib를 이용하여 동일한 값을 출력해보겠습니다.
stack Lib 사용 코드

#include <iostream>
#include <stack>
using namespace std;


int main() {
	
	stack<int> stack;
	
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(5);
	stack.push(7);

	cout << stack.top();
	stack.pop();
	cout << stack.top();
	stack.pop();
	stack.push(4);
	cout << stack.top();
	
	
	
	return 0;
}