[JavaScript] Data Structure - Stack, Queue

Reference - 코드 스테이츠 이머시브 코스 - Data Structure 강의 

 

 

 

 

자료구조 (Data Structure) 란?

데이터 자료구조는 컴퓨터 저장공간의 효율성과 실행의 신속성을 높이기 위해 일정한 규칙에 따라 데이터를 구조화한 것이다. 

 

배우면 좋은 이유?

자료구조를 짜는 법을 이해하게 되면 앞으로 더욱 실용적인 코드를 짤 수 있게 된다. 각각의 자료구조는 저마다 탄생된 배경이 있고 각각의 장단점이 모두 다르다. 완벽한 자료구조란 존재하지 않는다. 그래서 자료구조를 배운다면 내가 무언가를 구현할 때 필요한 자료구조가 무엇인지 파악할 수 있게 된다. 

 

또한 면접에서도 자주 나오는 단골 주제이니 배워두면 좋다. 자료구조에 대해 찾아보던 중 아래 영상을 보게 되었는데, 유튜버가 자료구조가 많은 곳에서 실용적으로 쓰인다며 그 예로 자신이 마이크로소프트에서 일할 때 실행이 7-10시간 걸리는 코드를 자기가 5-10분 만에 돌아가는 코드로 바꿨다고 언급하는 부분이 인상적이었다. 

 

 

스택 (Stack)

 

초밥 먹고싶다아

 

스택은 LIFO (last in, first out)의 규칙을 갖고 있다.

 

스택을 실제상황에 빗대어 설명하자면, 회전초밥집에 쌓인 그릇들을 예로 들고 싶다. 내가 초밥 한 접시를 먹고 접시를 놓으면 그 위로 최근에 먹은 접시가 점점 쌓이게 된다.(last in) 그 접시 탑을 설거지한다면 가장 나중에 먹은 접시부터 (first out)  처음에 놓았던 접시를 마지막으로 설거지할 것이다.

 

스택의 구현

스택을 자바스크립트로 구현할 때, 다음과 같은 메소드들을 구현하였다.

 

• push(element) - 요소를 스택의 최상단에 추가.
• pop() - 스택의 최상단에서 요소를 제거하고 반환.
• size() - 스택의 현재 요소 개수를 반환.

class Stack {
  constructor() {
    this.storage = {}; 
    this.top = 0; // 스택에 쌓인 자료갯수
  }

  size() {
    return this.top;
  }

  push(element) {
    this.storage[this.top] = element; // 값이 추가될때 마다 스택의 length를 인덱스로 가짐. 
    this.top ++ 
  }

  pop() {
    if (this.top > 0) {
      let result = this.storage[this.top - 1]; // 삭제할 키값을 변수에 담아줌.
      delete this.storage[this.top - 1]; // 가장 위의 데이터를 삭제
      this.top -- // 사이즈도 축소
      return result; // 삭제된 자료를 미리 담아준 변수를 통해 반환.
    }
  }
}

 

큐 (Queue)

 

최근에 난리났던 스벅 써머레디백...

 

큐는 FIFO (first in, first out)의 규칙을 갖고 있다.

 

큐는 대기줄을 생각하면 된다. 데이터들이 먼저 들어온 순서대로 줄을 선다면, 가장 먼저 추가된 데이터 (first in)가 가장 먼저 실행되고 (first out) 가장 마지막에 추가된 데이터가 가장 마지막에 실행된다. 

 

큐의 구현

큐를 자바스크립트로 구현할 때, 다음과 같은 메소드들을 구현하였다.

 

• enqueue(element) - 요소를 스택의 최상단에 추가.
• dequeue() - 큐의 가장 앞의 요소를 제거하고 반환.
• size() - 큐의 현재 요소 개수를 반환.

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear - this.front;
  }

  enqueue(element) {
    this.storage[this.rear] = element // 가장 처음의 요소는 0이란 키를 가짐. 
    this.rear++ // 요소가 추가될 때마다 키숫자 증가됨.
  }
  
  dequeue() {
    if (this.size() > 0) {   // 큐가 비어있지 않다면
      let result = this.storage[this.front]; // 삭제될 요소를 변수에 미리 할당.

      delete this.storage[this.front] // 맨 앞의 요소를 삭제
      this.front++ // 그 다음 요소가 가장 처음이 되도록 front 증가시킴.

      return result; // 미리 할당되었던 삭제된 요소를 반환함.
    }
  }
}