스택이란?

어떠한 데이터의 구체적인 구현 방식은 생략하고 데이터의 추상적인 형태와 그 데이터를 다루는 방법만 정해놓은 것을 가지고 ADT (Abstract Data Type) 또는 추상 자료형이라고 한다. 그 중 스택이란 고전적인 자료구조 중 하나이다. 스택은 자바스크립트에 내장되어 있진 않지만 배열과 내장함수들을 이용하여 스택을 흉내낼 수 있다.

LIFO (Last In First out) 원칙 (나중에 들어온 데이터가 먼저 나감, 드럼통 안에 물건을 담는 느낌)
함수 실행 콘텍스들이 쌓이는 Call Stack, 브라우저 방문 기록이 쌓이는 History Stack이 대표적
여러 작업을 연달아 수행하면서 이전의 작업 내용을 저장해야 할 때 자주 사용
스택이 비어있을 때 pop 을 시도 -> stack underflow, stack의 최대 크기를 초과하면 stack overflow (무한 재귀, 깊은 재귀, 비효율적 재귀)

속성

top: 스택에 쌓여있는 맨 위의 아이템

메소드

push: 스택의 맨위에 데이터 삽입
pop: 스택의 맨위에 데이터를 제거하고 데이터 return
contains: 해당 데이터가 스택안에 존재하는지 확인
size: 스택의 개수

사용 사례

재귀 알고리즘
괄호 검사 (수식이나 코드에서 괄호의 짝이 맞는지)
수식 계산 (후위 표기법)
실행 취소
브라우저 뒤로가기

스택의 시간복잡도

Insertion(삽입): 스택의 맨위에 추가하기 때문 O(1)
delete(삭제): 최상위 데이터 삭제 O(1)
Access(접근): 최상위 데이터부터 순회 O(n)
Search(검색): 최상위 데이터 제외 O(n)

배열로 스택 구현

export default class Stack {
  constructor() {
    this.items = [];
  }

  push(item) {
    this.items.push(item);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    if (this.items.length === 0) {
      return null;
    }
    return this.items[this.items.length - 1];
  }

  getSize() {
    return this.items.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }
}

배열을 이용하지 않는 스택 구현 (Linked List)

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

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

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

  push(data) {
    // 새로운 데이터를 받은 노드생성,
    const newNode = new Node(data);
    // 현재 최상위 노트(현재의 this.top노드) 기 새로 노드의 next가됨
    newNode.next = this.top;
    // 그리고 최상위 노드는 새로 들어온 newNode가 된다.
    this.top = newNode;
  }

  pop() {
    if (this.isEmpty()) return;
    // 최상단 노드가 pop()되면서 최상단 밑에있던 노드가 최상단 노드(this.top)가 된다.
    this.top = this.top.next;
  }

  peek() {
    if (this.isEmpty()) return;
    return this.top.data;
  }

  display() {
    if (this.isEmpty()) return;
    let curr = this.top;

    while (curr.next) {
      console.log(`${curr.data} ---> `);
      curr = curr.next;
    }
  }
}

재귀 함수

let company = {
  sales: [
   {name: 'John', salary: 1000},
   {name: 'Alice', salary: 1600}
  ],
  development: {
    sites: [
      {name: 'Peter', salary: 2000},
      {name: 'Alex', salary: 1800 }
    ],
    internals: [
      {name: 'Jack', salary: 1300}
    ]
  }
};

// 급여 합계를 구해주는 함수
function sumSalaries(department) {
  // array 형태일 경우
  if (Array.isArray(department)) {
    return department.reduce((prev, current) => prev + current.salary, 0); // 배열의 요소를 합함
  } else {
    let sum = 0;
    for (let subdep of Object.values(department)) {
      sum += sumSalaries(subdep); // 재귀 호출로 각 하위 부서 임직원의 급여 총합을 구함
    }
    return sum;
  }
}

alert(sumSalaries(company)); // 7700