읽고 나면 진짜 쉬워지는 자료 구조 - 4. 스택과 큐

데이터가 저장된 순서에 따라 데이터를 읽을 수 있는 자료 구조

🔖 4.1 스택

배열로 스택 구현

• 데이터를 추가할 때 스택을 확장할 수는 있지만, 배열의 크기를 확장해야 하는 경우 추가 비용이 발생할 수 있다.

• 자바스크립트 배열은 동적 크기를 가지므로 push() 연산은 배열의 크기가 충분하면 빠르게 수행되지만, 배열 크기를 확장해야 할 때는 메모리 재할당 비용이 발생한다.

• 스택에서 항목을 pop()할 때는 push()보다 내부 동작이 간단하다.

• push()는 배열의 끝에 데이터를 삽입하고, 배열 크기를 고려하여 메모리를 확장해야 할 수도 있지만, pop()은 배열의 마지막 요소를 제거하는 단순한 작업이다.

const stack = [];

stack.push(10); // 추가 (push)
stack.push(20);
console.log(stack); // [10, 20]

stack.pop(); // 제거 (pop)
console.log(stack); // [10]

연결 리스트로 스택 구현

• 연결 리스트를 사용하면 크기에 제한이 없고, 메모리 재할당을 걱정할 필요가 없다.

• 스택에 항목을 push()할 때는 연결 리스트의 앞쪽에 새로운 노드를 추가한다.

• 새로운 노드를 생성하고, 새 노드의 next 포인터와 스택의 head 포인터를 갱신해 새 노드를 리스트 맨 앞에 삽입한다.

• pop()할 때는 head 노드의 값을 반환하고, head 포인터를 다음 노드로 이동시킨다.

function createNode(value) {
  return { value, next: null };
}

function createStack() {
  let head = null;

  return {
    push(value) {
      const newNode = createNode(value);
      newNode.next = head;
      head = newNode;
    },
    pop() {
      if (!head) return null;
      const poppedValue = head.value;
      head = head.next;
      return poppedValue;
    },
    peek() {
      return head ? head.value : null;
    },
  };
}

const stack = createStack();
stack.push(10);
stack.push(20);
console.log(stack.peek()); // 20
console.log(stack.pop()); // 20
console.log(stack.pop()); // 10

🔖 4.2 큐

배열로 큐 구현

• 큐는 배열의 push()와 shift()를 사용해 구현할 수 있다.

• 그러나 shift()는 배열의 모든 요소를 앞으로 이동시키므로 비용이 크다.

• 이러한 단점을 해결하기 위해 순환 큐를 사용하면 배열의 끝에서 맨 앞으로 이동하는 추가 작업 없이 효율적으로 작동할 수 있다.

const queue = [];

queue.push(10); // 추가 (enqueue)
queue.push(20);
console.log(queue); // [10, 20]

queue.shift(); // 제거 (dequeue)
console.log(queue); // [20]

연결 리스트로 큐 구현

• 연결 리스트를 사용하면 큐의 크기를 동적으로 관리할 수 있다.

• 리스트의 머리(head)를 가리키는 포인터와 꼬리(tail)를 가리키는 포인터를 유지한다.

• enqueue()는 꼬리에 새로운 노드를 추가하고, dequeue()는 머리에서 노드를 제거한다.

• 큐 크기와 상관없이 연산은 항상 일정한 시간(O(1)) 내에 수행된다.

function createQueue() {
  let head = null;
  let tail = null;

  return {
    enqueue(value) {
      const newNode = createNode(value);
      if (!tail) {
        head = tail = newNode;
      } else {
        tail.next = newNode;
        tail = newNode;
      }
    },
    dequeue() {
      if (!head) return null;
      const dequeuedValue = head.value;
      head = head.next;
      if (!head) tail = null;
      return dequeuedValue;
    },
    peek() {
      return head ? head.value : null;
    },
  };
}

const queue = createQueue();
queue.enqueue(10);
queue.enqueue(20);
console.log(queue.peek()); // 10
console.log(queue.dequeue()); // 10
console.log(queue.dequeue()); // 20

🔖 4.3 순서의 중요성

깊이 우선 탐색 (DFS)

• 더 깊이 탐색하면서 막다른 골목에 도달할 때까지 한 가지 경로를 진행하는 방식

• 막다른 골목에 도달하면 마지막으로 방문했던 분기로 돌아가 다음 루트를 확인한다.

• 스택을 사용해 앞으로 탐색할 목록을 유지하며, 가장 최근에 삽입한 가능성을 가장 먼저 탐색한다.

function dfs(graph, start) {
  const visited = new Set();
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();

    if (!visited.has(node)) {
      visited.add(node);
      console.log(node);
      for (const neighbor of graph[node]) {
        stack.push(neighbor);
      }
    }
  }
}

const graph = {
  A: ['B', 'C'],
  B: ['D', 'E'],
  C: ['F'],
  D: [],
  E: [],
  F: [],
};

dfs(graph, 'A'); // A, C, F, B, E, D

너비 우선 탐색 (BFS)

• 깊이 우선 탐색과 유사한 방식으로 탐색하나, 큐를 사용해 미래의 가능성을 저장한다.

• 각 단계에서 탐색은 가장 오래 기다린 가능성을 탐색하며, 더 깊은 단계를 탐색하기 전에 같은 깊이의 여러 다른 방향으로 뻗어 나간다.

function bfs(graph, start) {
  const visited = new Set();
  const queue = [start];

  while (queue.length > 0) {
    const node = queue.shift();
    
    if (!visited.has(node)) {
      visited.add(node);
      console.log(node);
      for (const neighbor of graph[node]) {
        queue.push(neighbor);
      }
    }
  }
}

bfs(graph, 'A'); // A, B, C, D, E, F

정리

• DFS와 BFS는 모두 한 번에 하나의 가능성을 탐색한다는 점에서 동일한 속도로 작동한다.

• DFS는 '스페셜리스트'처럼 특정 경로를 깊이 탐색하고, BFS는 '제너럴리스트'처럼 여러 경로를 얕게 탐색한다.