[Node 7기] 알고리즘 강의 - 4일차 링크드 리스트 기반 자료구조 형태

스택(Stack)

• 특징: LIFO(Last In, First Out) 구조. 가장 마지막에 추가된 데이터가 가장 먼저 제거됨.
• 주요 기능:
  1. Push: 데이터 삽입
  2. Pop: 데이터 제거
  3. Peek: 최상단 데이터 확인
• 예제 사용처:
  • 뒤로가기 기능(브라우저, 앱 네비게이션)
  • Undo/Redo 기능
• 구현 코드 (링크드 리스트 기반):

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

class Stack {
  constructor() {
    this.head = null;
  }

  peek() {
    return this.head ? this.head.value : null;
  }

  push(value) {
    const newNode = new Node(value);
    newNode.next = this.head;
    this.head = newNode;
  }

  pop() {
    if (!this.head) return null;
    const removed = this.head;
    this.head = this.head.next;
    return removed.value;
  }
}

 

---

큐(Queue)

• 특징: FIFO(First In, First Out) 구조. 가장 먼저 추가된 데이터가 가장 먼저 제거됨.
• 주요 기능:
  1. Enqueue: 데이터 삽입
  2. Dequeue: 데이터 제거
  3. Peek: 가장 앞의 데이터 확인
• 예제 사용처:
  • 서버 접속 대기열
  • 프린터 인쇄 대기열
• 구현 코드 (링크드 리스트 기반):

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  dequeue() {
    if (!this.head) return null;
    const removed = this.head;
    this.head = this.head.next;
    return removed.value;
  }
}

 

---

정렬 알고리즘

1. 버블 정렬 (Bubble Sort)
   • 방법: 인접한 두 데이터를 비교하며 정렬.
   • 시간 복잡도: O(N²)
   • 코드:

   function bubbleSort(array) {
     const n = array.length;
     for (let i = 0; i < n; i++) {
       for (let j = 0; j < n - i - 1; j++) {
         if (array[j] > array[j + 1]) {
           [array[j], array[j + 1]] = [array[j + 1], array[j]];
         }
       }
     }
     return array;
   }
   

2. 선택 정렬 (Selection Sort)
   • 방법: 가장 작은(또는 큰) 값을 선택해 맨 앞과 교환.
   • 시간 복잡도: O(N²)
   • 코드:

   function selectionSort(array) {
     const n = array.length;
     for (let i = 0; i < n - 1; i++) {
       let minIndex = i;
       for (let j = i + 1; j < n; j++) {
         if (array[j] < array[minIndex]) {
           minIndex = j;
         }
       }
       [array[i], array[minIndex]] = [array[minIndex], array[i]];
     }
     return array;
   }
   

---

※ 요약

• 스택: "가장 마지막 데이터" 우선. Push, Pop, Peek 사용.
• 큐: "가장 먼저 들어온 데이터" 우선. Enqueue, Dequeue, Peek 사용.
• 정렬 알고리즘: 데이터를 순서대로 정렬.
  • 버블 정렬은 단순 비교 후 교환.
  • 선택 정렬은 최소값 선택 후 교환.