99클럽 코테 스터디 5일차 TIL - Implement Stack using Queues (리트코드 225 / JavaScript)

오늘의 문제 링크

 

⭐ intro : 문제를 생각해나간 방식

이전 문제였던 'Implement Queue using Stack와 상당히 비슷하게 생각하게 되었다. 생각 의외로 큐를 구현했던 방식과 비슷한 방식으로 쉽게 풀어나갈 수 있으리라 생각했고, 예상은 적중했었다. 정말 쉽게 풀게되었다.

 이번에도 class 문법으로 구현하는것이 조건이었고, 자료구조 queue와 비슷한 stack 구조를 구현하는것이 목표였다. 큐와는 달리 자료구조 '스택'은 LIFO라는 형태로, Last in First Out, 후입선출이라 부르는 형태로 마지막에 들어온 것이 첫번째로 나가게 된다는 것이다. queue를 설명했을때와 비슷하게 그림으료 표현하면 다음과 같다.

큐와는 다르게 마지막 인덱스 값을 잘 구분해서 쌓아두는것이 포인트다.

 

 

⭐ 풀이과정

큐를 구현했던것과 초기 틀은 똑같이 만들어 둔다. 이 문제 또한 tail의 값은 -1로 초기화 해두었으나 통일성과 직관성을 위하여 0으로 초기화 해 두었다. 그리고 문제제시 요건중에서 함수 하나가 다른데, 큐에서는 선입선출과정으로 첫번째 head의 인덱스값이 중요하여 peek()이라는 함수를 이용하여 현재 바라보고 있는 머리의 인덱스를 구하는것이 중요했지만 스택에서는 후입선출로서 마지막에 들어온 tail의 인덱스값이 중요하고, 그림에서 보는것처럼 가장 위에 있는 요소가 tail값인지라 top()이라는 함수를 이용하여 현재 tail값이자 맨 위의 요소를 바라보도록 하는 함수를 만들어둔다.

 그리고 size(), push(), empty()함수는 큐와 동일하게 꼬리의 인덱스와 머리의 인덱스 값을 이용해서 만드는 함수인지라 큐와 동일한 함수를 만들어 넣는다.

class MyStack {
  constructor() {
    this.storage = [];
    this.head = 0;
    this.tail = 0;
  }
  
  size() {
    return this.tail - this.head;
  }
  
   push(x) {
    this.storage[this.tail] = x;
    this.tail++;
  }
  
  top() {}

  pop() {}
  
  empty() {
  	return this.size() === 0;
  }
}

 

 두번째로는 top() 함수를 구현한다. 큐는 head값의 위치를 파악해야 했기에 peek() 함수를 만들었지만 스택은 꼬리값, 즉 차곡차곡 쌓아올려진 최상위 값의 인덱스를 구해야 하므로 tail값을 반환하되, push로 넣은 상태에서는 tail값이 현재 tail위치보다 1이 더 높은, push() 함수의 후위연산자로 `this.tail++`이 들어가 있으므로 현재 위치를 나타내기 위해서는 tail값에서 -1만큼 빼주어야 한다. 해당 코드를 구현하면 다음과 같다.

top() {
  return this.storage[this.tail -1];
}

/*
예를들어 
1. push(🍓)을 실행했을 경우
스택 : [🍓] / tail : 1 / 🍓의 인덱스를 구하기 위해 필요한 인덱스의 값 : 0 

2. push(🍇)를 실행했을 경우
스택 : [🍓,🍇] / tail : 2 / 🍇의 인덱스를 구하기 위해 필요한 인덱스의 값 : 1 
*/

 

마지막으로는 pop() 함수를 구현해본다. 큐와 마찬가지로 size()가 0일경우 뽑아내야할 스택의 값이 아무것도 없으므로 undefined를 반환하게 하는 조건문을 달고, value 변수를 만들어서 value 값에 현재 스택의 tail-1 인덱스값을 호출하도록 한다. (지금와서 생각해보니 this.top()값을 넣어도 될것같다) 그리고 마찬가지로 head값이 tail값보다 커질때 스택의 index값이 꼬이게 되므로 constructor 값의 초기값처럼 초기화시켜두면 class로 구현하는 stack 완성!

 

  pop() {
    if (this.size() === 0) return undefined // 스택이 비어있으면 undefined 반환
    let value = this.storage[this.tail -1];
    this.tail--;
    
    // 스택이 비어있을경우 초기화
    if (this.head > this.tail) {
      this.storage = [];
      this.head = 0;
      this.tail = 0;
    }
    return value;
  }

 

 

⭐ 제출답안

class MyStack {
  constructor() {
    this.storage = [];
    this.head = 0;
    this.tail = 0;
  }
  
  size() {
    return this.tail - this.head;
  }
  
  push(x) {
    this.storage[this.tail] = x;
    this.tail++;
  }
  
  top() {
    return this.storage[this.tail -1];
  }

  pop() {
    if (this.size() === 0) return undefined // 스택이 비어있으면 undefined 반환
    let value = this.storage[this.tail -1];
    this.tail--;
    
    // 스택이 비어있을경우 초기화
    if (this.head > this.tail) {
      this.storage = [];
      this.head = 0;
      this.tail = 0;
    }
    return value;
  }
  
  empty() {
    return this.size() === 0;
  }
}

 

 

⭐ 공부했던 개념들

99클럽 코테 스터디 4일차 TIL - Implement Queue using Stacks (리트코드 232 / JavaScript)