큐, 스택, 트리

Table of contents

큐 (Queue)
스택 (Stack)
트리 (Tree)
Set 집합 연산

Table of contents

큐 (Queue)
스택 (Stack)
트리 (Tree)
Set 집합 연산

어떤 데이터의 구체적인 구현 방식은 생략한 채, 데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 합니다. 이 챕터에서는 널리 사용되는 ADT인 큐, 스택, 트리에 대해 배웁니다.

큐 (Queue)

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

데이터를 집어넣을 수 있는 선형(linear) 자료형입니다.
먼저 집어넣은 데이터가 먼저 나옵니다. 이 특징을 줄여서 FIFO(First In First Out)라고 부릅니다.
데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue 등의 작업을 할 수 있습니다.

JavaScript에서는 배열을 이용해서 간단하게 큐를 구현할 수 있습니다.

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

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

스택 (Stack)

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

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

JavaScript에서는 배열을 이용해서 간단하게 스택을 구현할 수 있습니다.

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)

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

트리를 다룰 때 사용되는 몇 가지 용어를 살펴보겠습니다.

노드(node) - 트리 안에 들어있는 각 항목을 말합니다.
자식 노드(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) - 같은 부모 노드를 갖는 다른 노드를 보고 형제 노드라고 부릅니다.

아래는 아주 간단한 형태의 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!

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

Set 집합 연산

Set은 중복되지 않는 값들의 집합을 나타내는 자료구조입니다. ES2024와 ES2025에서는 Set에 집합 이론의 기본 연산들이 추가되어, 수학적인 집합 연산을 쉽게 수행할 수 있게 되었습니다.

집합 연산 메소드

const setA = new Set([1, 2, 3, 4])
const setB = new Set([3, 4, 5, 6])

// 합집합 (Union) - 두 집합의 모든 요소
const union = setA.union(setB)
console.log([...union]) // [1, 2, 3, 4, 5, 6]

// 교집합 (Intersection) - 양쪽 집합 모두에 있는 요소
const intersection = setA.intersection(setB)
console.log([...intersection]) // [3, 4]

// 차집합 (Difference) - setA에는 있지만 setB에는 없는 요소
const difference = setA.difference(setB)
console.log([...difference]) // [1, 2]

// 대칭 차집합 (Symmetric Difference) - 한쪽에만 있는 요소
const symDiff = setA.symmetricDifference(setB)
console.log([...symDiff]) // [1, 2, 5, 6]

집합 비교 메소드

Set 간의 포함 관계를 확인하는 메소드들도 추가되었습니다.

const setA = new Set([1, 2, 3, 4])
const setB = new Set([1, 2])
const setC = new Set([5, 6])

// 부분집합 확인 (Subset) - setB의 모든 요소가 setA에 포함되는가?
setB.isSubsetOf(setA) // true
setA.isSubsetOf(setB) // false

// 상위집합 확인 (Superset) - setA가 setB의 모든 요소를 포함하는가?
setA.isSupersetOf(setB) // true
setB.isSupersetOf(setA) // false

// 서로소 집합 확인 (Disjoint) - 공통 요소가 없는가?
setA.isDisjointFrom(setC) // true (공통 요소 없음)
setA.isDisjointFrom(setB) // false (공통 요소 있음)

실용적인 예시

이러한 Set 연산은 데이터 분석이나 권한 관리 등 다양한 실무 상황에서 유용하게 사용될 수 있습니다.

// 예시: 사용자 권한 관리
const adminPermissions = new Set(['read', 'write', 'delete'])
const userPermissions = new Set(['read', 'write'])

// 사용자에게 없는 권한 찾기
const missingPermissions = adminPermissions.difference(userPermissions)
console.log([...missingPermissions]) // ['delete']

// 공통 권한 찾기
const commonPermissions = adminPermissions.intersection(userPermissions)
console.log([...commonPermissions]) // ['read', 'write']

이러한 Set 메소드들은 코드를 더 간결하고 읽기 쉽게 만들어주며, 집합 관련 로직을 직관적으로 표현할 수 있게 해줍니다.

Edit this page on GitHub