JavaScript에서 큐, 스택, 노드

** 어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type)혹은 추상 자료형이라고 한다. **



[큐]

1. 데이터를 집어 넣을 수 있는 선형(linear) 자료형이다.
2. 먼저 넣은 데이터가 먼저 나온다 FIFO(First In First Out) : 선입선출
3. 데이터를 넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있다.

- code

      

      

      

    
    

      <javascript />
    
class Queue {
	construtor(){
		this._arr = [];
	}
	enqueue(item){
		this._arr.push(item);
	}
	dequeue(){
		return this._arr.shift();
	}
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(); //1

** 정리 **
Queue는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용된다.

[스택]

1. 데이터를 넣을 수 있는 선형(linear) 자료형
2. 나중에 넣은 데이터가 먼저 나온다 LIFO(Last In First Out) : 후입선출
3. 데이터를 넣는 push, 추출하는 pop, 맨 나중에 넣은 데이터를 확인하는 peek 등의 작업을 할 수 있다.

- code

      

      

      

    
    

      <javascript />
    
class StackI{
	constructor(){
		this._arr = [];
	}
	push(item){
		this._arr.push(item);
	}
	pop(){
		return this._arr.pop();
	}
	peek(){
		return this._arr[this._arr.length - 1];
	}
}

const stack = new Stack();
stack.push(1);
stack.push(2);
stack.push(3);
stack.pop(); //3

** 정리 **
서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해 둘 필요가 있을떄 사용된다.

[트리]

@ 여러 데이터가 계층 구조 안에서 서로 연결된 형태를 나타낼 때 사용 @

1. 노드    (node)      - 트리 안에 들어있는 각 항목
2. 자식 노드(child node)      - 노드는 여러 잣ㄱ 노드를 가질 수 있다.
3. 부모 노드(parent node)     - 노드 A가 노드 B를 자식으로 갖고 있다면 노드 A를 노드 B의 부모 노드라고 부른다.
4. 뿌리 노드(root node)       - 트리의 가장 상층부에 있는 노드를 말한다.
5. 잎  노드(leaf node)     - 자식 노드가 없는 노드를 말한다.
6. 조상 노드(ancestor node)   - 노드 A자식을 따라 내려갔을 때 노드 B에 도달할 수 있다면, 노드 A를 노드 B의 조상 노드라고 부른다.
7. 자손 노드(descendant node) - 노드 A가 노드 B의 조상 노드일 때 노드 B를 노드 A의 자손 노드라고 부른다.
8. 형제 노드(sibling node)    - 같은 부모 노드를 갖는 다른 노드를 보고 형제 노드라고 부른다. 

- code

      

      

      

    
    

      <javascript />
    
class Node {
  constructor(content, children = []) {
    this.content = content;
    this.children = children;
  }
}

const tree = new Node('hello', [
  new Node('world'),
  new Node('and'),
  new Node('fun', [
    new Node('javascript!')
  ])
]);

function traverse(node) {
  console.log(node.content);
  for (let child of node.children) {
    traverse(child);
  }
}

traverse(tree);
// hello world and fun javascript!

** 정리 **
트리는 게층 구조를 나타내기 위해, 또한 계층 구조를 통해 알고리즘의 효율으ㅜㄹ 높이고자 할때 널리 사용된다.