CS[DataStructure].push('Stack')

Stack이란?

FILO (First In Last Out) 방식의 자료구조

Stack은 카드 뭉치라고 생각하면 된다. 먼저 들어온 것이 깊숙히 쌓이게 되고 마지막으로 들어온 것이 먼저 나오게 된다. JS에서 동작 원리 중 호출 스택이 이 스택 형식을 갖고 있다.

탐색의 최악의 경우는 모든 수를 본 O(n)이라고 할 수 있고 최선의 경우는 맨 위에 값이 있는
O(1), 1번이다.

추가는 무조건 위에 놓기 때문에 O(1)로 할 수 있다.

제거도 무조건 위를 제거하기 때문에 O(1)이다.

JS로 구현해보자.

class Stack {
  toppest = null;

  push(value) {
    if (this.toppest === null) {
      this.toppest = new Node(value);
    } else {
      let current = new Node(value);
      current.next = this.toppest;
      this.toppest = current;
    }
  }

  pop() {
    let value = this.toppest;
    this.toppest = this.toppest?.next;
    return value?.value;
  }

  top() {
    return this.toppest?.value;
  }
}

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

const stack = new Stack();
stack.push(2);
stack.push(4);
stack.pop();
stack.top();

Reference

인프런 - 비전공자의 전공자 따라잡기 (제로초)
C언어로 쉽게 풀어쓴 자료구조 - 천인국,공용해,하상호