자료구조 스택 알아보기 TIL

스택 자료구조 특징

• LIFO (Last In First Out)
• 스택 자료구조에 마지막으로 추가된 값이 제일 먼저 제거가 된다.

위 자료구조는 언제 사용될까

• 함수 호출 관리
• 작업 중 원상태로 돌리거나(undo) 다시 할 때(redo)
• 라우팅 히스토리 역시 스택으로 처리된다.

스택 자료구조의 빅 오 표기법

• 삽입 (Insertion) O(1)
• 제거 (Removal) O(1)
• 탐색 (Searching) O(N)
• 접근 (Access) O(N)

스택 구현 중 내가 헷갈렸던 부분(linked-list 활용)

push(3)

1) 값을 3으로 갖는 노드를 만들어준다.

2) stack의 top을 추가되는 노드를 가리키게 한다.

push(4)

1) 값을 4로 갖는 노드를 만들어준다

2) 추가되는 노드의 next에 스택 top이 가리키는 node를 부여한다.

3) stack의 top을 추가되는 노드를 가리키게 한다.

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

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

  push(value) {
    //1
    const 추가되는노드 = new Node(value);
    //2
    추가되는노드.next = this.top;
    //3
    this.top = 추가되는노드;
  }

  pop() {
    if (this.isEmpty()) throw new Error("this is empty");
    const temp = this.top;
    this.top = temp.next;
    return temp.value;
  }

  peek() {
    if (this.isEmpty()) throw new Error("this is empty");
    return this.top.value;
  }

  isEmpty() {
    return this.top === null;
  }
}

변수에는 변수를 부여하는 게 아니라 "그 변수의 값"을 부여한다.