스택(Stack)이란?

책상에 쌓아둔 책더미처럼 데이터를 쌓듯 추가하는 자료구조이다.

쌓여진 책을 집을때 맨 위의 책부터 꺼내는 것처럼
스택의 자료는 마지막에 입력된 데이터가 먼저 출력(&삭제)되는 LIFO(Last In, First Out) 또는 FILO(First In, Last Out) 방식으로 관리된다.

인터페이스

items - 데이터 목록
push(data) - 스택 꼭대기에 데이터를 추가한다.
pop() - 스택 꼭대기에서 데이터를 반환하고, 해당 데이터는 스택에서 삭제한다.
peek() - 스택 꼭대기에 있는 데이터를 반환하되 스택은 변경하지 않는다.
isEmpty(): 스택이 비었는지 확인한다.
clear(): 스택의 데이터를 모두 삭제한다.
size(): 스택에 있는 데이터의 갯수를 반환한다.

구현 - JavaScript에서의 스택

스택은 데이터의 삽입/삭제 작업이 많으므로 일반적인 언어라면 삽입/삭제가 효율적인 리스트로 구현하는게 좋지만,
JavaScript의 배열은 연관배열로 구현되어있으므로 배열로 구현해도 괜찮다.

class Stack {
  constructor() {
    this._items = [];
  }

  get items() {
    return this._items;
  }

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

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

  peek() {
    return this._items[this._items.length - 1];
  }

  isEmpty() {
    return this._items.length <= 0;
  }

  clear() {
    this._items = [];
  }

  size() {
    return this._items.length;
  }
}

// Test
it("Stack 클래스는 잘 동작한다.", () => {
  const stack = new Stack();

  stack.push("Qus");
  stack.push("Tom");
  stack.push("Jackson");

  expect(stack.items).toEqual(["Qus", "Tom", "Jackson"]);

  stack.pop();
  expect(stack.items).toEqual(["Qus", "Tom"]);

  const peekResult = stack.peek();
  expect(peekResult).toEqual("Tom");
  expect(stack.items).toEqual(["Qus", "Tom"]);

  expect(stack.isEmpty()).toEqual(false);
  expect(stack.size()).toEqual(2);

  stack.clear();
  expect(stack.isEmpty()).toEqual(true);
  expect(stack.size()).toEqual(0);
});

활용 사례

운영체제 Process의 스택 영역, 함수의 콜스택(Call Stack) 등

아디트야 바르가바, 『Hello Coding 그림으로 개념을 이해하는 알고리즘』, 김도형, 한빛미디어(2017)
스기우라 켄, 『그림으로 배우는 알고리즘』, 서재원, 영진(2016)
이소 히로시, 『모던 자바스크립트 입문』, 서재원, 길벗(2018)
Martin Erwig, 『그들은 알고리즘을 알았을까?』, 송원형, 영진(2017)
Loiane Groner, 『자바스크립트 자료 구조와 알고리즘』, 이일웅, PACKT-에이콘(2015)

스택(Stack)이란 무엇인가

스택(Stack)이란?

인터페이스

구현 - JavaScript에서의 스택

활용 사례

배열(Array)이란 무엇인가

큐(Queue)란 무엇인가