스택이란

하나의 진입점에서만 자료를 넣고 뺄 수 있는 LIFO(Last In First Out) 형식의 자료구조.

스택의 구현

스택은 연결리스트(linked list) 로 구현할 수 있다.

프로퍼티

1. size = 0
2. top = null

Push(value)

스택의 맨 위에 value를 삽입한다.

1. 현재 top을 next로 받아온다.
2. 생성된 노드를 top으로 지정.
3. size를 늘린다.

pop()

가장 나중에 들어간(맨 위) 요소를 삭제 후 반환한다.

1. 삭제할 노드가 없다면 삭제하지 않는다. (top === null)
2. 삭제할 노드를 임시로 저장해둔다.
3. top이 가리키는 노드를 top의 next 노드로 바꾼다.
4. 자바스크립트 가비지컬렉터에 의해 자동으로 예전 top 노드가 사라진다.
5. size를 줄인다.
6. 임시로 저장해 두었던 노드를 return 한다.

getSize()

return this.size
스택의 크기를 반환한다.

peek()

return this.top
스택의 맨 위 요소를 반환한다.

isEmpty()

return this.top === null
스택이 비었는지 확인한다.

스택의 용도

• 재귀 알고리즘
• 웹 브라우저 방문 기록
• undo

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

class Stack {
  constructor() {
    this.top = null;
    this.size = 0;
  }
  getSize(){
    return this.size;
  }
  push(data){
    const node = new Node(data);
    node.next = this.top;
    this.top = node;
    this.size++;
  }
  pop(){
    if(this.size === 0) return null;
    const temp = this.top.data;
    this.top = this.top.next;
    this.size--;
    return temp;
  }
}