TIL Day-23

자료구조

Achievement Goals

• 자료구조가 무엇인지 설명할 수 있다.
• stack, queue, Tree, Graph 자료구조에 대해 이해할 수 있다.
• 트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
• 자료구조를 활용하여 알고리즘 문제에 접근할 수 있다.

자료구조란?

• 자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.
• 문자,숫자,소리,그림,영상 등 실생활을 구성하고 있는 모든 값
• 데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있다.

• 테스트에 걸리는 시간을 단축하고 알고리즘 문제 풀이에 집중하기 위해, JavaScript에서 제공하는 배열(Array)과 같은 데이터 타입을 이용해 자료구조의 형태와 유사하게 구현하여 문제를 해결합니다.

stack

• 데이터(data)를 순서대로 쌓는 자료구조
• FIrst In Last Out = 막다른 골목길에 처음으로 들어가면 나중에 나감
• Last In First Out = 막다른 골목길에 마지막에 들어가면 처음으로 나감

Javascript Array 이용하지 않고 stack 메소드 구현하기

class Node {
  constructor(value){
    this.value = value;
    this.next = null;
  }
}

class Stack {
  constructor(){
    this.top = null;
    this.bottom = null;
    this.length = 0;
  }
  peek() {
    // stack에 쌓인 가장 마지막 녀석을 확인하는 메소드
    return this.top;
  }
  push(value){
    const newNode = new Node(value);
    
    if (this.length === 0) {
      this.top = newNode;
      this.bottom = newNode;
    } else {
      const holdingPointer = this.top;
      this.top = newNode;
      this.top.next = holdingPointer;
    }
    this.length++;
    return this;
  }
  pop(){
    if (!this.top) return null;
    if (this.top === this.bottom) {
      this.bottom = null;
    }
    this.top = this.top.next;
    this.length--;
    return this;
  }
  //isEmpty
}

const myStack = new Stack();
console.log(myStack);
myStack.peek();
myStack.push('google');
myStack.push('facebook');
myStack.push('udemy');
myStack.pop();
myStack.pop();
myStack.pop();

Queue

• 줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가지고 있다.
• 가장 나중에 진입한 자동차는 먼저 도착한 자동차가 모두 빠져나가기 전까지는 톨게이트를 빠져나갈 수 없다.
• First In First Out = 프린트 대기순서에 오면 먼저 프린트 됨
• Last In Last Out = 프린트 대기순서에 나중에 오면 나중에 프린트 됨

Javascript Array 이용하지 않고 queue 메소드 구현하기

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}
class Queue {
  constructor(){
    this.first = null;
    this.last = null;
    this.length = 0;
  }
  peek() {
    return this.first;
  }
  enqueue(value){
    const newNode = new Node(value);
    if (this.length === 0) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    this.length++;
    return this;
  }
  dequeue(){
    if(!this.first) {
      return null;
    }
    if (this.first === this.last) {
      this.last = null;
    }
    const holdingPointer = this.first;
    this.first = this.first.next;
    this.length--;
    return this;
  }
  //isEmpty;
}
const myQueue = new Queue();
myQueue.enqueue('Joy');
myQueue.enqueue('Matt');
myQueue.enqueue('Pavel');
myQueue.enqueue('hyunsol');
//Joy
//Matt
//Pavel
//Samir

queue 실사용 예제

• 톨게이트에서 가장 먼저 들어온 차가 먼저 통과한다.
• 프린트에서 임시저장장소에 들어온 자료가 먼저 프린트 된다.(버퍼링)

자바스크립트 동작원리

Queue에서 작성된 코드들이 비어있는 stack에 코드를 전송하면 이를 하나씩 실행한다.
하지만 함수인 경우 대기실에 대기해두고 queue에서 stack으로 올라온 코드들이 실행된 후 비어있는 stack에서 실행이 된다.