TIL [자료 구조 - Stack]

dlrbwls0302·2021년 1월 19일
0

Stack의 개념

Stack은 선형의 데이터 구조로 어떠한 계산이나 실행이 특정한 방식으로 진행되게 하는데, 그 특정한 방식을 우리는 LIFO(Last In First Out)나 FILO(First In Last Out) 라고 부른다.

Stack은 보통 이렇게 탑처럼 생긴 구조로 생겼는데 주요 기능에는 데이터를 추가하는 push와 데이터를 제거하는 pop이 있다. 실제로 우리가 흔히 쓰는 배열의 메서드로 pop과 push가 있는데 바로 배열의 요소를 추가하거나 제거하는 역할을 한다.

Stack은 실생활에서도 많이 볼 수 있다. 하노이의 탑 같은 게임이나 박스안에 물건을 담을 때에도 Stack이 쓰인다. 먼저 추가된 데이터나 아이템은 가장 밑에 깔리고 그 위에 차곡차곡 쌓이기 때문에 우리는 위에 서 부터 하나하나 접근할 수 밖에 없다.


Stack의 push, pop 메서드 논리 구조

1. push

Step 1 - Stack이 꽉 차있는지 확인
Step 2 - Stack이 꽉 차있으면 에러 생성 및 종료
Step 3 - Stack이 꽉 차있지 않으면 top에 1을 더해줌
Step 4 - Stack에 top이 가리키는 곳으로 데이터를 넣어줌
Step 5 - 성공!

2. pop

Step 1 - Stack이 비어있는지 확인
Step 2 - Stack이 비어있으면 에러 생성 및 종료
Step 3 - Stack이 꽉 차있지 않으면 top에 1을 더해줌
Step 4 - Stack에 top이 가리키는 곳으로 데이터를 넣어줌
Step 5 - 성공!


Stack 구현

class Stack {
  constructor() {
    this.storage = {};
    this.top = -1;
  }

  size() {
    return this.top + 1
  }

  push(element) {
    this.top += 1 // 맨 위의 데이터의 index
    this.storage[this.top] = element
  }

  pop() {
    if(this.top === -1) return undefined;
    let result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;
    return result; // 제거된 데이터를 리턴
  }
  
  isEmpty(){
    if(this.top === -1) return true;
    else return false;
  }
  
  peek(){
    if(this.top === -1) return undefined;
    else {
      return this.storage[this.top];
    }
  
}
profile
오늘의 공부가 쌓여서 내일의 나를 만들어낸다.

관심 있을 만한 포스트

0개의 댓글