Stack, Queue, Tree

어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것

ADT(Abstract Data Type) 혹은 추상 자료형이라고 함

[ Stack ] 

• 데이터를 집어넣을 수 있는 선형(linear) 자료형
• LIFO(Last In First Out) 즉 나중에 집어넣은 데이터가 먼저 나옴. 
• JS에서는 배열을 이용해 스택을 구현할 수 있음

용어

• push: 데이터를 집어넣음
• pop: 데이터를 추출
• peek: 맨 위에 있는 요소를 확인
• lefts: 모든 요소 문자열로 반환
• clear: 모든 요소를 삭제
• empty: 남은 요소가 있는지 없는지 확인
• contains: 해당 아이템이 스텍에 존재하는지 확인
• size: 스택에 있는 아이템의 총 개수를 반환

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

재귀 알고리즘, 실행 취소 (undo), 웹 브라우저 방문기록 (뒤로가기) 등

 

export default class Stack {
  constructor() {
    // item들을 받을 배열 생성
    this.items = [];
  }

  push(item) {
  //stack에 item을 집어넣음
    this.items.push(item);
  }

  pop() {
    //stack에 item을 뺌
    return this.items.pop();
  }

  peek() {
      //stack에 맨 위에 item 얻어옴
    if (this.items.length === 0) {
      return null;
    }
    return this.items[this.items.length - 1];
  }

  getSize() {
  //stack에 크기 확인
    return this.items.length;
  }

  isEmpty() {
  //stack에 비었는지 확인
    return this.getSize() === 0;
  }

 

[ Queue ]

• 데이터를 집어넣을 수 있는 선형(linear) 자료형
• FIFO(First In First Out) 즉 먼저 집어넣은 데이터가 먼저 나옴
• JS에서는 배열을 이용하여 큐를 구현할 수 있음 

용어

• enqueue: 데이터를 집어넣음
• dequeue: 데이터를 추출
• contains : 해당 아이템이 큐에 존재하는지 확
• size : 현재 큐에 있는 아이템의 총 개수를 반환한다
• peek: 맨 왼쪽에 있는 요소를 확인

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

너비 우선 탐색(BFS, Breadth-First Search) 구현, 캐시(Cache) 구현, 선입선출이 필요한 대기열 (티켓 카운터)

 

export default class Queue {
  constructor() {
    // item들을 받을 배열 생성
    this.items = [];
  }

  enqueue(item) {
   // Queue에 아이템을 넣음
    this.items.push(item);
  }

  dequeue() {
  	//Queue에 아이템을 뺌
    return this.items.shift();
  }

  peek() {
  	//Queue 제일 왼쪽의 item을 확인
    return this.items[0];
  }

  getSize() {
  	//Queue 크기 확인
    return this.items.length;
  }

  isEmpty() {
  	//Queue가 비었는지 확인
    return this.getSize() === 0;
  }
}

 

 

[ 트리 ]

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

용어

• 노드(node): 트리 안에 들어있는 각 항목
• 자식 노드: 노드는 여러 자식 노드를 가질 수 있음
• 부모 노드: A가 B를 자식으로 갖고 있다면, A를 B의 '부모 노드'라고 부름
• 뿌리 노드(root node): 트리의 가장 상층부(제일 위, 꼭대기)에 있는 노드
• 잎 노드: 자식 노드가 없는 노드
• 조상 노드: A의 자식을 따라 내려갔을 때 B에 도달할 수 있다면, A를 B의 '조상 노드'라고 부름
• 자손 노드: A가 B의 조상 노드일 때, B를 A의 '자손 노드'라고 부름
• 형제 노드: 같은 부모 노드를 갖는 다른 노드를 보고 '형제 노드'라고 부름
•  레벨
  • 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현
  • 같은 레벨에 나란히 있는 노드를 형제노드라고 부름
• 깊이: 루트로부터 하위 계층의 특정 노드까지의 깊이를 표현 

트리의 종류

• binary tree(이진트리): 노드의 자식수가 최대 2개를 넘지 않는 트리. 어떠한 값을 찾는것에 특화된 자료구조
  • full(정): 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
  • perfect(포화): 모든 노드가 0개 혹은 2개의 자식노드를 가지며 모든 리프노드가 똑같은 레벨에 있는 경우의 트리
  • complete(완전): 왼쪽자식노드부터 채워지며 마지막 레벨을 제외하고는 모든 자식 노드가 채워져있는 트리
  • balanced(균형): 모든 노드의 왼쪽과 오른쪽의 하위 트리와의 높이가 1 이상 차이가 나지 않는 이진 트리 구조
• nonbinary tree

이진트리 탐색

• in-order(중위 순회) : 왼쪽 자식 노드(L), 내 노드(P), 오른쪽 자식노드(R) 순서로 방문.
• pre-order(전위 순회) : 내 노드(P), 왼쪽 자식노드(L), 오른쪽 자식노드(R) 순서로 방문.
• post-order(후위 순회) : 왼쪽 자식노드(L), 오른쪽 자식 노드(R), 내 노드(P) 순서로 방문.
• level-order(레벨 순회) : 내 노드(P), 내 노드로부터 깊이 1인 노드들 내 노드로부터 깊이 2인 노드들,... , 내 노드로부터 깊이 N인 노드들 (N: 나(트리)의 깊이)

 

class BSTNode {
    constructor(data, left = null, right = null) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

class BinarySearchTree {
    //BST의 constructor를 구현
    constructor(value) {
      this.value = value;
      this.left = null;
      this.right = null;
    }
    // tree에 value 추가
    insert(value) {
      // 인자의 value가 this.value보다 작을 경우, 왼쪽 노드에서 진행
      if (value < this.value) {
        // this.left에 아무것도 없을 경우, 새로운 자식 노드를 추가.
        if (this.left === null) {
          this.left = new BinarySearchTree(value);
        }
        // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용
        else {
          this.left.insert(value);
        }
      }
      // 인자의 value가 this.value보다 클 경우, 오른쪽 노드에서 진행
      else if (value > this.value) {
        // this.right에 아무것도 없을 경우, 새로운 자식 노드를 추가
        if (this.right === null) {
          this.right = new BinarySearchTree(value);
        }
        // this.left의 자식 노드가 있을 경우, 자식 노드에서 insert 재귀를 사용
        else {
          this.right.insert(value);
        }
      } else {
        // 이미 value값을 포함하고 있음
      }
    }
    // tree의 value값을 탐색
    contains(value) {
      // 찾는 value값이 노드의 value와 일치한다면, true를 리턴
      if (value === this.value) {
        return true;
      }
      // 찾는 value값이 노드의 value 보다 작다면, 왼쪽에서 contains의 재귀를 진행.
      if (value < this.value) {
        return !!(this.left && this.left.contains(value));
      }
      // 찾는 value값이 노드의 value 보다 크다면, 오른쪽에서 contains의 재귀를 진행
      if (value > this.value) {
        return !!(this.right && this.right.contains(value));
      }
    }
    //tree를 전위 순회
    preorder(callback) {
      callback(this.value);
      if (this.left) {
        this.left.preorder(callback);
      }
      if (this.right) {
        this.right.preorder(callback);
      }
    }
    // tree를 중위 순회
    inorder(callback) {
      if (this.left) {
        this.left.inorder(callback);
      }
      callback(this.value);
      if (this.right) {
        this.right.inorder(callback);
      }
    }
    //tree를 후위 순회
    postorder(callback) {
      if (this.left) {
        this.left.postorder(callback);
      }
      if (this.right) {
        this.right.postorder(callback);
      }
      callback(this.value);
    }
  }