[자바스크립트] 스택(Stack) 구현하기

iberis2·2023년 3월 14일
0

알고리즘 문제

목록 보기
9/27
post-thumbnail

스택(Stack) 구현하기

멤버 변수

  • 데이터를 저장할 Object 타입의 storage
    마지막에 들어온 데이터를 가리키는 Number 타입의 포인터 top
  • 데이터를 저장할 Object 타입의 storage
    마지막에 들어온 데이터를 가리키는 Number 타입의 포인터 top

구현 메서드

  • size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다.
  • push(): 스택에 데이터를 추가할 수 있어야 합니다.
  • pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다.

주의사항

  • 내장 객체 Array.prototype에 정의된 메서드는 사용하면 안 됩니다.
  • 포인터 변수 top의 초기값은 -1, 0, 1등 임의로 지정할 수 있지만,
  • 여기서는 빈 스택을 나타내는 -1으로 초기화되며 이후 push, pop에 따라 1씩 증감해주어 데이터가 추가될 인덱스의 위치를 가리키도록 합니다.

사용 예시

const stack = new Stack();

stack.size(); // 0
for(let i = 1; i < 10; i++) {
  	stack.push(i);
}
stack.pop(); // 9
stack.pop(); // 8
stack.size(); // 7
stack.push(8);
stack.size(); // 8

나의 풀이

  • Array.prototype에 대한 제한만 있고, Object.prototype에 대한 제한이 없어서,
    this.size() 메서드를 Object.keys()를 이용해서 풀었다.

  • 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다.
    문항에 대해서,
    this.size <= 0으로 했는데 안풀려서,
    this.top === -1로 바꿨더니 통과가 됐다.
    알고 보니 this.size() <= 0 으로 했어야 했다.

☑️ 함수 선언함수 호출(리턴값)이 필요한 부분을 잘 구분하자!

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

  size() {
    return Object.keys[this.storage].length;
  }

  // 스택에 데이터를 추가 할 수 있어야 합니다.
  push(element) {
    this.top += 1;
    this.storage[this.top] = element;
  }

  // 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
  pop() {
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.top === -1) {
      return;
    }

    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;

    return result;
  }
}

레퍼런스

class Stack {
  // stack constructor를 생성합니다.
  constructor() {
    this.storage = {};
    this.top = -1;
  }
  // stack의 사이즈를 구합니다.
  // this.top은 스택이 쌓일 때마다 하나씩 증가하기 때문에 top으로부터 size를 구할 수 있습니다.
  // this.top은 스택에 새롭게 추가될 요소의 인덱스를 나타냅니다. 빈 스택을 표현하는 -1부터 1씩 증감하며 표현하며 전체 요소의 개수를 추정할 수 있습니다
  size() {
    return this.top + 1;
  }
  // stack에 element를 추가합니다.
  // 현재 추가하는 element의 인덱스인 this.top을 키로, 요소를 값으로 하여 storage에 할당합니다.
  push(element) {
    this.top += 1;
    this.storage[this.top] = element;
  }
  // 만약 size가 0보다 작거나 같다면 이는 비어있는 스택을 의미하므로 아무 일도 일어나지 않습니다.
  // stack에서 현재 stack의 최상단에 있는 element를 변수에 저장합니다.
  // storage에서 해당 element를 제거합니다.
  // 하나를 제거했으니 방금 제거한 element의 인덱스를 나타내는 top 또한 감소시켜 업데이트 해줍니다.
  // 최상단에 있던 element가 저장된 변수 result를 반환합니다.
  pop() {
    if (this.size() <= 0) {
      return;
    }
    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;
    return result;
  }
}
profile
React, Next.js, TypeScript 로 개발 중인 프론트엔드 개발자

0개의 댓글