JavaScript 큐(Queue), 스택(Stack), 트리(Tree)

JavaScript

JavaScript 큐(Queue), 스택(Stack), 트리(Tree)

kohi ☕ 2022. 10. 20. 15:27

✨ 자료구조

여러 데이터의 묶음을 저장하고 효율적으로 사용하는 방법을 정의한 것
특정한 상황에 놓인 문제를 해결하는 데 특화

✨ 스택(Stack)과 큐(Queue)

스택과 큐 모두 Linear한(선형) 자료 구조이다. 이 둘은 아주 유사한 구조이나, element가 제거되는 방식에 차이가 있다.
- 스택은 마지막으로 삽입된 element가 가장 먼저 제거되는 방식인 LIFO(Last In First Out, 후입선출) 자료구조이다. 스택의 예시로는 브라우저 히스토리(이전 페이지, 다음 페이지) 또는 ctrl + z로 이전 작업을 취소하는 동작 등을 들 수 있다.
- 큐는 FIFO(First In First Out, 선입선출) 자료구조이다. 줄 서기를 생각하면 된다. 큐의 예시로는 예매 앱, 레스토랑 예약 등을 들 수 있을 것이다.

✨ 큐(Queue)

큐는 다음과 같은 성질을 가진다.

데이터를 집어 넣을 수 있는 선형 자료 구조이다.
먼저 집어 넣은 데이터가 먼저 나온다. 데이터를 집어 넣는 enqueue, 데이터를 추출하는 dequeue 작업을 할 수 있다.
순서대로 처리해야 하는 작업을 임시로 저장하는 버퍼로 많이 사용된다.
배열 활용 시, unshift() - pop() 메서드 혹은 push() - shift() 메서드 조합을 사용하는 것이 큐의 작동 방식과 같다. unshift() 메서드를 사용해 데이터를 추가하는 경우 전체 배열에 인덱스를 다시 부여해야 하므로 성능이 좋지는 않다.

class Queue {
  constructor() {
    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.dequeue(); // 1

메서드를 사용하지 않고 큐를 구현하는 방식은 다음과 같다.

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

class Queue {
  constructor() {
    this.first = null;
    this.last = null;
    this.size = 0;
  }
}

Enqueue 구현
- push() 메서드처럼 노드를 제일 뒤에 추가한다.

enqueue(val) {
    const newNode = new Node(val);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    return ++this.size;
  }

Dequeue 구현
- shift() 메서드처럼 제일 앞 노드를 제거하고 반환한다.

dequeue() {
    if (!this.first) return null;

    const temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }

✨ 스택(Stack)

스택은 다음과 같은 성질을 가진다.

데이터를 집어 넣을 수 있는 선형 자료 구조이다.
나중에 집어 넣은 데이터가 먼저 나온다. 데이터를 집어 넣는 push, 데이터를 추출하는 pop, 맨 나중에 집어 넣은 데이터를 확인하는 peek 등의 작업을 할 수 있다.
스택은 서로 관계가 있는 여러 작업들을 연달아 수행하면서 이전의 작업 내용을 저장할 필요가 있을 경우 사용된다.
배열을 이용해 스택 구조를 구현하면 다음과 같다.

class Stack {
  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

✨ 트리(Tree)

트리를 다룰 때 사용되는 용어 정리

노드(Node) - 트리 안에 들어 있는 각 항목
자식 노드(Child Node) - 노드는 여러 자식 노드를 가질 수 있다.
부모 노드(Parent Node) - 노드 A가 노드 B를 자식으로 갖고 있다면 노드 A는 노드 B의 부모 노드
뿌리 노드(Root Node) - 트리의 가장 상층부에 있는 노드
잎 노드(Reaf Node) - 자식 노드가 없는 노드
조상 노드(Ancestor Node) - 노드 A의 자식을 따라 내려갔을 때 노드 B에 도달할 수 있는 경우 노드 A는 노드 B의 조상 노드
자손 노드(Descendant Node) - 노드 A가 노드 B의 조상 노드일 때 노드 B는 노드 A의 자손 노드
형제 노드(Sibling Node) - 같은 부모 노드를 가진 다른 노드
노드의 크기(Size) - 자신을 포함한 모든 자손 노드의 개수
노드의 깊이(Depth) - 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(Level) - 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(Degree) - 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수(Degree of Tree) - 트리의 최대 차수
트리의 높이(Height) - 루트 노드에서 가장 깊숙이 있는 노드의 깊이

트리는 다음과 같은 성질을 가진다.

트리는 하나의 뿌리 노드를 갖는다.
뿌리 노드는 하나 이상의 자식 노드를 갖는다.
그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.
트리는 노드와 노드를 연결하는 간선(Edge)으로 구성되어 있다.
노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
트리에는 사이클이 존재할 수 없다.
그래프의 한 종류로, 계층적 관계를 표현하는 비선형적 자료 구조이다.
순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS / BFS 안에 있다.
트리는 이진 트리, 이진 탐색 트리, 균형 트리(AVL 트리, Red-Black 트리), 이진 힙(최대 힙, 최소 힙) 등이 있다.
다음은 간단하게 트리 구조를 구현한 예시이다.

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!

이진 트리

이진 트리 - 각 노드가 최대 두 개의 자식을 갖는 트리

이진 트리 순회

전위 순회 - 현재 노드 ⇒ 왼쪽 가지 ⇒ 오른쪽 가지

preorder(callback) {
    callback(this.value);
    if (this.left) {
      this.left.preorder(callback);
    }
    if (this.right) {
      this.right.preorder(callback);
    }
  }

중위 순회 - 왼쪽 가지 ⇒ 현재 노드 ⇒ 오른쪽 가지

inorder(callback) {
    if (this.left) {
      this.left.inorder(callback);
    }
    callback(this.value);
    if (this.right) {
      this.right.inorder(callback);
    }

후위 순회 - 왼쪽 가지 ⇒ 오른쪽 가지 ⇒ 현재 노드

postorder(callback) {
    if (this.left) {
      this.left.postorder(callback);
    }
    if (this.right) 
      this.right.postorder(callback);
    }
    callback(this.value);
  }