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

오늘의 문제 링크

 

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

 처음에 봤을때 이 'leetcode', 리트코드라는 코딩테스트 사이트를 드디어 만져보는구나 싶었다. 회고스터디에서 이 사이트 괜찮다길래 자자한 명성은 얼추 주워들어서 알고있었다. 아니 그런데 모두 영어라서, 갑자기 급 언어이슈가 생길뻔했으나 아니 애초에 영어는... 모든 프로그래밍 언어인데 이건 무슨소리인가 싶기도....하하.

 이번 과제는 stack을 이용해서 자료구조인 'queue', 큐를 구현하는 문제였다. length같이 간단한 배열의 길이를 조회하는 메서드 외에는 배열 메서드를 쓰지 않고 구현해보는것이 핵심이다. 그런데...'class' 문법으로 구현하는것이 조건이었다. 내가 자바스크립트를 공부하면서 가장 어려웠던 부분이 2가지가 있었는데, 첫번째가 이 class였고 두번째는 this였다. 어쩌다보니 두가지 문법이 다 class안에 들어있어서 결과적으로는? class를 잘 모르는 사람인것으로... 이번 queue 자료구조를 공부하면서 겸사겸사 class문법도 확실...하게 잘 배워나갔다.

 자료구조 '큐'는 FIFO라는 형태로서 First In First Out, 선입선출이라고도 부르는 형태이다. 첫번째로 들어온것이 첫번째로 나가게 된다라는 것으로 간단히 그림으로 표현하면 다음과 같다

첫번째 인덱스 번호와 마지막 인덱스 번호값만 잘 구분해서 쌓아둘 수 있으면 오케이~! 이 구조를 머릿속에 넣어두고 구현해보자.

 

 

⭐ 풀이과정

 class문법같은 경우는 여기서 다루면 배보다 배꼽이 커질듯 하여, 클래스 문법 정리는 추후 다시 정리해보도록 해보겠다. 일단 MyQueue라는 class를 생성하고(왜 MyQueue라면...리트코드에서 그리 하라고 정했으니....별수있나...), class 안쪽에서 공통으로 가져갈 요소인 constructor 안에 현재 스택을 표기하는 storage, 스택의 첫번째 값의 위치를 표시하는 head, 마지막 값의 위치를 표시하는 tail값을 설정해두고 head, tail값은 0로 초기화해둔다. (사실 본인은 직관적인 값 이해가 좋아서 tail값을 -1로 초기화 해둔뒤 pop실행할때마다 직관적인 위치에 넣을 수 있도록 해두었지만... 이렇게 짜면 코드가 너무 더러워서, tail값도 0인 상태로 시작하도록 수정해보았다)

 또한 해당 함수에 필요한 기능들인 push(), pop(), peek(), empty()를 구현해두고, head값이 항상 0일수는 없는지라 size()함수도 구현해둔다. size()의 경우엔 항상 tail값에서 head값을 뺀 값이 고정적이니 해당 값을 return값으로 설정해둔다.

// 기본 BASE
class MyQueue {
  constructor() {
    this.storage = [];
    this.head = 0;
    this.tail = 0;
  }

   size() {
    return this.tail - this.head;
  }
  
  push() {]
  
  pop() {}
  
  peek() {}
  
  empty() {}
  
}

 

 

 두번째로는 push() 함수를 구현해봤다. 기본 배열 메서드 array.prototype.push()는 배열의 마지막 값에 해당 값을 추가하는 것이다. 해당 stack의 마지막 값에 해당 값을 넣을 수 있도록 해두었고, tail값은 stack이 변동된 뒤 보이지 않는, 그렇지만 다음 값이 stack에 추가될 경우의 index를 미리 저장해두도록 tail값을 1씩 증가시키도록 만들었다. (여기서 만약 tail값을 -1로 초기화해두고 시작하면 보이지 않는이고 뭐고 바로 마지막 index값에 딱딱 집어넣을 수 있게 됌) 그리고 매개변수 x값이 주어지므로 push(x)를 실행하면 x값이 해당되는 마지막 stack 위치에 값이 만들어지도록 만들었다.

push(x) {
  this.storage[this.tail] = x;
  this.tail++;
}

 

 

세번째로는 pop() 함수를 구현해보았다. 이 함수가 해당 class의 핵심로직이지 않을까 싶다. 먼저 size()값이 0일경우는 아무것도 존재하지 않는다는 의미이므로 pop()을 실행할 수가 없다. 따라서 기본 조건으로 해당 size()값에 따른 에러처리를 먼저 진행해주었다. 다음으로는 value라는 변수를 만들어서 현재 stack의 첫번째로 들어온 index인 head값을 저장해두고, pop()이 실행되면 head값을 한칸 증가시키도록 만들었다. 실질적으로는 배열이 줄어드는 변화는 없다. 왜냐하면 배열의 길이를 n이라 칭했을 경우, n이 길어지는 만큼 인덱스 번호가 처음부터 바뀌는 queue의 경우 모든 배열값의 index가 바뀌기 때문에, 시간복잡도가 O(n)만큼 증가되서 시간이 엄청 소모되는 단점이 생긴다.

 그리고 head값이 tail값보다 커질 경우는 stack의 index가 꼬여버리는, 그야말로 size()가 0이 되는 순간이기 때문에 이때 constructor값의 초기값처럼 해당값으로 똑같이 초기화 시켜두고, 이 일련의 사태를 전부 지난 후 value에 저장되어있는 '최초로'들어온 stack값을 return하도록 만들어준다

pop() {
  if (this.size() === 0) return undefined; // 큐가 비어있으면 undefined 반환
  let value = this.storage[this.head];
  this.head++;

  // 큐가 비었을 경우 초기화
  if (this.head > this.tail) {
    this.storage = [];
    this.head = 0;
    this.tail = 0;
  }
  return value;
}

 

 

마지막으로는 peek()과 empty()함수를 구현한다. peek은 현재 처음으로 들어온 값의 위치를 뱉어주는 함수고 empty()는 해당 stack이 비어있는지 true, false로 알려주는, boolean을 내뱉는 함수이다. 간단하게 다음과 같이 구현해볼 수 있다. 이렇게 모든 함수를 만들고 나면 class로 구현하는 queue 완성!

peek() {
  return this.storage[this.head];
}

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

 

 

⭐ 제출답안

class MyQueue {
  constructor() {
    this.storage = [];
    this.head = 0;
    this.tail = 0;
  }

  size() {
    return this.tail - this.head;
  }

  push(x) {
    this.storage[this.tail] = x;
    this.tail++;
  }
  
  peek() {
    return this.storage[this.head];
  }
  
  pop() {
    if (this.size() === 0) return undefined; // 큐가 비어있으면 undefined 반환
    let value = this.storage[this.head];
    this.head++;

    // 큐가 비었을 경우 초기화
    if (this.head > this.tail) {
      this.storage = [];
      this.head = 0;
      this.tail = 0;
    }
    return value;
  }
  

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

 

 

⭐ 공부했던 개념들

• class
• queue 자료구조