JavaScript Queue, Stack, Tree

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

큐(Queue)

큐(Queue)는 다음과 같은 성질을 갖는 자료형입니다.

• 데이터를 집어넣을 수 있는 선형(linear) 자료형입니다.
• 먼저 집어넣은 데이터가 먼저 나옵니다. 이를 FIFO (First In First Out) 또는 선입선출이라고 합니다.
• 데이터를 집어넣은 euqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있습니다.

큐에서는 가장 앞에 있는 요소를 전단(Front), 가장 뒤에 있는 요소를 후단(Rear)라고 합니다.
큐는 선입선출이라고 말씀드렸듯이 제거는 전단에서 이루어지며, 삽입은 후단에서 이루어집니다.
배열로 쉽게 큐를 구현을 해보자면 다음과 같습니다.

// 큐 정의
class Queue {
  constructor() {
    this._arr = [];
  }
  // 데이터를 넣는 euqueue는 후단에서 삽입됩니다.
  enqueue(item) {
    this._arr.push(item);
  }
  // 데이터를 추출하는 dequeue는 전단에서 이루어집니다.
  dequeue() {
    return this._arr.shift();
  }
}

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

이처럼 큐는 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer)로서 많이 사용됩니다.

[활용예시]

• OS 에서 프로세스 스케줄링엥 우선순위 큐를 활용할 수 있습니다.
  
• 공유 컴퓨터에서 작업 순서를 계획할 때, 최대 우선순위 큐는 실행할 작업과 상대 우선순위를 계속 기억하고 있습니다.
  한 작업이 끝나거나 중단될 때, Extract-max 를 이용하여, 대기중인 작업 중 가장 우선순위가 높은 작업을 선택합니다.
  새로운 작업은 insert 를 사용하여 큐에 새로 들어갈 수 있습니다.
  

스택(Stack)

스택(Stack)은 다음과 같은 성질을 갖는 자료형입니다.

• 데이터를 집어넣을 수 있는 선형(linear) 자료형입니다.
• 나중에 집어넣은 데이터가 먼저 나옵니다. 이 특징을 줄여서 LIFO(Last In First Out) 또는 후입선출이라고 부릅니다.
• 데이터를 집어넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어넣은 데이터를 확인하는 peak 등의 작업을 할 수 있습니다.

스택은 후입선출(LIFO)라는 특징을 가졌다고 말씀드렸다시피 입력과 삭제가 후단에서 모두 이루어집니다.
배열로 쉽게 스택을 구현해보면 다음과 같습니다.

// 스택 정의
class Stack {
  constructor() {
    this._arr = [];
  }
  // 데이터를 넣는 enqueue는 후단에서 삽입됩니다.
  push(item) {
    this._arr.push(item);
  }
  // 후입선출이기에 데이터를 추출하는 dequeue는 후단에서 아루어집됩니다.
  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

이처럼 스택은 서로 관계가 있는 여러 작업을 연달아 수행하면서 이전의 내용 작업을 저장해 둘 필요가 있을 때 널리 사용됩니다.

[활용예시]

• 재귀 프로그램
• 서브루틴(특정 작업을 수행하는 명령어 세트) 호출시 복귀 주소 저장
• 수식 계산(Prefix, Infix, Postfix)
• DFS(깊이 우선 탐색, Depth-First Search), Preorder(전위 순회)
• Quick Sort(퀵 정렬)

트리 (Tree)

트리(tree)는 여러 데이터가 계층 구조 안에서 서로 연결된 형태를 나타낼 때 사용됩니다.

앞서 공부했던 DOM 을 Tree 형식으로 나타낸 것입니다.

트리는 노드로 구성되어 있는데 노드란 무엇일까요?

• 노드(node) - 트리 안에 들어있는 각 항목을 말합니다.

다음은 노드의 종류입니다.

• 문서 노드 (Document Node) - 트리의 최상위에 존재하며 각각 요소,어트리뷰트,텍스트 노드에 접근하려면 문서 노드를 통해야 합니다.
  즉 DOM Tree 에 접근하기 위한 시작점(entry point)입니다.
  

• 요소 노드 (Element Node) - 요소 노드는 HTML 요소를 표현합니다. HTML 요소는 중첩에 의해 부자 관계를 가지며, 이 부자 관계를 통해 정보를 구조화합니다.
  따라서 요소노드는 문서의 구조를 서술한다고 말 할수 있습니다. 어트리뷰트, 텍스트 노드에 접근하려면 먼저 요소 노드를 찾아 접근해야 합니다.
  모든 요소 노드는 요소별 특성을 표현하기 위해 HTMLElement 객체를 상속한 객체로 구성됩니다.
  

  • 자식 노드 (child node) - 노드는 여러 자식 노드를 가질 수 있습니다.
  • 부모 노드 (parent node) - 노드 A 가 노드 B 를 자식으로 갖고 있다면, 노드 A 를 노드 B 의 ‘부모 노드’라고 부릅니다.
  • 뿌리 노드 (root node) - 트리의 가장 상층부에 있는 노드를 말합니다.
  • 잎 노드 (leaf node) - 자식 노드가 없는 노드를 말합니다.
  • 조상 노드 (ancestor node) - 노드 A 의 자식을 따라 내려갔을 때 노드 B 에 도달할 수 있다면, 노드 A 를 노드 B 의 조상 노드라고 부릅니다.
  • 자손 노드 (descendant node) - 노드 A 가 노드 B 의 조상 노드일 때, 노드 B 를 노드 A 의 자손 노드라고 부릅니다.
  • 형제 노드 (sibling node) - 같은 부모 노드를 갖는 다른 노드를 보고 형제 노드라고 부릅니다.

• 어트리뷰트 노드 (Attribute Node) - 어트리뷰트 노드는 HTML 요소의 어트리뷰트를 표현합니다.
  어트리뷰트 노드는 해당 어트리뷰트가 지정된 요소의 자식이 아니라 해당 요소의 일부로 표현됩니다.
  따라서 해댱 요소 노드를 찾아 접근하면 어트리뷰트의 참조, 수정할 수 있습니다.
  

• 텍스트 노드 (Text Node) - 텍스트 노드는 HTML 요소의 텍스트를 표현합니다. 텍스트 노드는 요소 노드의 자식이며 자신의 자식 노드를 가질 수 없습니다.
  즉 텍스트 노드는 DOM tree 의 최종단입니다.
  

다음은 아주 간단한 형태의 Node를 구현한 예입니다.

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!

트리는 계층 구조를 나타내기 위해, 또한 계층 구조를 통해 알고리즘의 효율을 높이고자 할 때 널리 사용됩니다.

2. Today I Found Out

앞서 배웠던 내용이랑 조금씩 교집합이 있어서 학습하기에 훨씬 수월했습니다.
큐와 스택의 차이점을 알아볼 수 있었고, 각각 어떤 특징을 지니고 있는지 알 수 있었습니다.
공부를 하면서 다양한 자료구조를 조금 더 알아보고 싶다는 생각이 들었고,
어떻게 자료구조를 활용할지 좀 더 궁금함을 가지고 보려고 합니다.
또한 수업떄 궁금증을 질문할 예정입니다.

3. refer

https://helloworldjavascript.net/pages/282-data-structures.html

http://blog.eairship.kr/213

http://estenpark.tistory.com/15