TIL Day-23

hyeongirlife·2021년 10월 10일

목록 보기

24/90

자료구조

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