자료구조(data structure)는 효울적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다.
여기서 데이터의 처리를 할때 데이터 사이에 참조 관계에 있어서
선형 구조
,나무 구조
,
정보를 지정하는노드
들이 가장 위에 뿌리 노드를 정점으로 부모,자식,자손 관계를 이루며
나뭇가지처럼 갈라진 구조이다.
가지의 맨 끝에 있는 노드는리프
라고한다.
효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로
사용하면서 연산을 수행하도록 해줍니다.
스택은
제한적
으로 접근할 수 있는나열 구조
입니다.
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는
선형 구조
(LIFO - Last In First Out) -> 입,출구가 일자로된
주차장으로 생각하면 될 것같다.
네모들이 DATA들이 들어오면 최근에 들어왔던 자료부터 나오게 됩니다. 이렇게 나중에 넣은 값이 먼저 나오는
것을 LIFO 구조라고 합니다.
1. object를 새로 만든다.
2. push로 값을 하나씩 넣어준다.
3. pop로 맨 뒤에 값을 빼버린다.
const Stack = function () {
const someInstance = {};
const storage = {};
let count = 0;
someInstance.push = function(value) { // value = 'a'
storage[count] = value; // storage[0] = 'a' => { '0' : 'a' }
count++; // count = 1; 다음에 들어올값의 키가 '1' 로 증가시키기
};
// pop 에서는 '0' 번째 자리 없으면 undefinded 를 하고, 카운트를 이용해 삭제를 이용합니다.
someInstance.pop = function() {
if (!storage['0']) return undefind;
let temp = storage[count - 1];
delete storage[count - 1];
return temp;
}
// size 크기 확인은 카운트로
someInstance.size = function() {
return count;
}
return someInstacne;
stack.push("a");
stack.push("b");
stack.push("c");
stack.pop();
큐는 먼저 집어 넣은 데이터가 먼저 나오는 FIFO (First In first Out)구조로 저장하는 형식입니다.
먼저 줄선사람이 먼저 나가는 것 입니다.
큐는 put (input) 과 get (delete)을 이용하여 구현됩니다.
front(head)와 rear(tail)는 데이터 위치를 가르킵니다.
** front는 데이터를get
할 수 있는 위치,rear
은 데이터를 put 할 수있는 위치를 의미합니다 (한번 다시 읽어보세요~~~!!)
예제
게임 대기열 , 프린터 출력
1. 빈 객체을 만들어 준다.
2. 데이터 값을 하나씩 push 해준다.
3. 데이터의 제일 첫 번재로 들어온 것으 빼려면 shift()로 빼준다.
const Queue = function () {
const someInstance = {};
const storage = {};
let count = 0;
let head = 0;
let tail = 0;
// en('a') => { '0' : 'a' }
// en ('b') => { '0' : 'a', '1' : 'b' }
// de () => {'1' : 'b'}
someInstance.enqueue = function(value){
storage[tail] = value;
count++;
tail++;
};
// 큐에서는 head 를 빼줘야 합니다.
someInstance.dequeue = function() {
if (!storage[head]) return undefined;
let temp = storage[head];
delete storage[head];
head++;
count--;
return temp;
};
someInstance.size = function(){
return count;
};
}
queue.enqueue("a");
queue.enqueue("b");
queue.dequeue();
queue.enqueue("c");
연결 리스트는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결 되어 있는 방식으로 데이터를 저장하는 자료 구조이다.
배열에 비해 데이터의 추가/ 삽입 및 삭제가 용이하나 순차적으로 탐색하지 않으면 특정 위치의 요소에 접근할 수 없어 일반적으로 탐색 속도가 떨어진다.
즉, 탐색 또는 정렬을 자주 하면 배열을, 추가 / 삭제가 많으면 연결 리스트를 사용하는 것이 유리하다.
연결 리스트에서 각 원소는 원소 자신과 다음 원소를 가리키는 포인터가 포함된 노드로 구성된다.
위 그림에서 나누어 져있는데 데이터를 저장할 장소
와 다른 변수를 가리키기 위한 장소
가 구분되어 있다.
둘 이상 일때는 위 그림처럼 된다.
append(데이터): 리스트의 맨 끝에 데이터를 추가한다.
removeAt(위치): 해당 위치에 있는 데이터를 삭제한다.
indexOf(데이터): 해당 데이터의 인덱스를 반환한다. 존재하지 않을 경우 결과 값은 -1이다.
remove(데이터): 데이터를 삭제한다.
insert(위치, 데이터): 해당 위치에 데이터를 삽입한다.
isEmpty(): 데이터가 하나도 없다면 true를, 그 외엔 false를 반환한다.
size(): 데이터 개수를 반환한다. 배열의 length 프로퍼티와 비슷하다.
트리는 여러 데이터가 계층 구조 안에서 서로 연결된 형태를 나타낼 때 사용됩니다.
새로운 Tree {
Tree 생성자 {}
node 생성자 {
data;
child node 리스트;
size; //child node 갯수
}
빈 트리일 경우{
root = data
} 아닐 경우 {
for 현재 노드의 child 갯수 만큼 search{
child node를 현재 node로 변환하여 재귀함수 실행
}
}
}
[위너비] https://takeuu.tistory.com/172
[생코] https://opentutorials.org/module/1335/8821
[코딩팩토리] https://coding-factory.tistory.com/231