데이터를 처리하고 저장하기 위한 수단, 데이터에 효율적인 접근 처리를 가능하게 해주는 방법
자료구조는 그 방식에 따라 혹은 구조에 따라 분류할 수 있다.
선형 구조
스택 (stack) - 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다.
반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다.
만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.
큐 (queue) - 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다.
반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
비선형 구조
그래프 - 노드와 노드를 잇는 간선으로 구성된다. 두 개 이상의 노드가 있는 자료 구조이다.
트리 - 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 간선(edge)으로 표현된다.
이진 트리 - 자식이 최대 두 개인 트리.
힙 - 완전 이진트리의 일종으로 노드의 값의 대소관계가 존재한다.
들어온 순서에 반대로 나가는 순서가 정해진다. 먼저 들어온 자료가 가장 마지막에 나가게 된다.
웹페이지의 History를 예로 들 수 있다. 새로운 페이지에 들어오면 기존의 페이지는 이전 페이지 스택(stack)에 들어가고
뒤로가기 버튼을 누르게 되면 이전 페이지 스택의 최상단에 기록된 데이터가 나오게 된다.
class Stack {
constructor() {
this.length = 0
this.storage = {}
}
add (value) {
this.storage[this.length] = value
this.length++
}
pop() {
if(this.length === 0) return;
let value = this.storage[this.length - 1] // 현재 나갈 값
delete this.storage[this.length - 1] // 저장공간에서 데이터 지우기
this.length-- // 가장 위의 데이터 표시 지우기
return value
}
}
스택을 js로 구현하면 위와 같다.
들어온 순서데로 나가는 데이터 구조이다.
나가는 곳과 들어오는 곳이 정해져 있다.
지하철 개찰구와 같은 모습이라고 생각할 수 있다. 한명씩 순서데로 지나간다!
큐는 put(insert)와 get(delete)을 이용하여 구현된다.
put는 큐에 자료를 넣는 것을, get은 큐에서 자료를 꺼내는 것을 의미한다. front(head)와 rear(tail)는 데이터의 위치를 가리킨다! front는 데이터를 get할 수 있는 위치를, rear은 데이터를 put할 수 있는 위치를 의미한다.
또, 큐가 꽉 차서 더 이상 자료를 넣을 수 없는 경우(put 할 수 없는 경우)를 오버플로우(Overflow), 큐가 비어 있어 자료를 꺼낼 수 없는 경우(get 할 수 없는 경우)를 언더플로우(Underflow)라고 한다.
class Queue {
constructor() {
this.front = 0;
this.tail = 0;
this.storage = {}
}
insert (value) {
this.storage[this.tail] = value
this.tail++
}
get() {
if(this.front === this.tail) return; // 언더 플로우
let value = this.storage[this.front] //
delete this.storage[this.front] // 저장공간에서 데이터 지우기
this.front++ // 가장 위의 데이터 표시 지우기
return value
}
} // 오버플로우가 없는 큐 (크기의 제한이 없는 큐)
노드와 노드를 연결하여 구현한 자료구조
네비게이션, 검색엔진의 데이터 구조를 그래프 구조라고 할 수 있다.
일정 노드에서 연결된 노드로 이동하고 또 다음 노드로 이동하고 하는 것이 가능한 데이터 구조
그래프는 vertex(node)와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.
class Graph {
constructor() {
this.storage = {}
}
insert (node) {
if(!this.storage[node]) this.storage[node] = {}
}
addEdge(from, to) {
if(!this.storage[from] || !this.storage[to]) return ;
this.storage[from][to] = true;
this.storage[to][from] = true;
}
} // 무향그래프
그래프 구조의 일종으로, root로 부터 자식 node(vertax)가 추가되어 있는 형태이다.
모든 자식 노드를 기준으로 새로운 트리구조라고 할 수 있다.
뿌리에서 나무가 자라는 모습의 데이터 구조와 같은 모양을 가지고 있다.
class Tree {
constructor(value) {
this.value = value;
this.children = [];
}
addChild (value) {
const node = new Tree(value);
this.children.push(node);
}
contain(value) {
if (this.value === value) {
return true;
}
for(let i = 0; i < this.children.length; i ++) {
if(this.children[i].contain(value)) {
return true
}
}
return false;
}
}
가장 많이 사용되는 자료구조 4가지에 대해 간단하게 살펴보았다.
각각의 자료구조가 어떤식으로 사용되는지 추후에 확인 해본다.
요점만 잘 정리해주셨네요~ 잘 보고 갑니닷!! :)