자료구조

여러 데이터들의 묶음을 저장하고 , 사용하는 방법을 정의한 것.
데이터를 효율적으로 다룰 수 있는 방법

데이터란?

• 문자,숫자,소리,그림,영상 등 실생활을 구성하고 있는 보든 값.
• 데이터는 분석하고 정리하여 활용을 해야 의미를 가지게됨 (단순히 데이터 단독으로는 상세정보가 없기 때문에 의미를 가지기 어려움)

Stack

데이터를 순서대로 쌓는 자료구조

가장 먼저 들어간 데이터는 가장 나중에 나옴(가장 나중에 들어간 데이터는 가장 먼저 나옴)
FILO(First in Last out) , LIFO(Last in First out)

스택의 예시

브라우저의 뒤로가기, 앞으로 가기, 어렸을때 했던 햄버거 게임

Javascript로 스택구현 예시

class Stack {
  constructor() {
    this.storage = {};
    this.top = 0; // 스택의 가장 상단을 가리키는 포인터 변수를 초기화 합니다.
  }

  size() {
    return this.top;
  }



	// 스택에 데이터를 추가 할 수 있어야 합니다.
  push(element) {
    this.storage[this.top] = element;
    this.top += 1;
  }
	
	// 가장 나중에 추가된 데이터가 가장 먼저 추출되어야 합니다.
  pop() {
    // 빈 스택에 pop 연산을 적용해도 에러가 발생하지 않아야 합니다
    //this.size를 하는이유는 메서드 안의 this는 메서드를 호출한 객체에 바인딩 되기 때문.
    //만약 인스턴스가 a라고 하면 a.pop()을하면 pop() {}안에 있는 this는 a라는 객체에 바인딩 됨.
    if (this.size() <= 0) { 
      return;
    }

    const result = this.storage[this.top-1];
    delete this.storage[this.top-1];
    this.top -= 1;
    
    return result;
  }
}

stack의 구성

• push--> 스택에 데이터를 넣는다.
• pop--> 스택에 있는 데이터를 뺀다.
• top--> 제일 상단의 데이터를 단순히 보여주기만 한다.
• size--> 스택에 요소가 얼만큼 쌓였는지 수치를 보여준다.

Queue

Stack과 반대되는 개념으로 먼저 들어간 데이터가 먼저 나오는 구조

FIFO(First in First out), LILO(Last in Last out)

큐의 예시

프린터 출력 , 고속도로 톨게이트

Queue의 구성

• shift --> 큐에 있는 맨앞의 데이터를 뺀다.
• push --> 큐의 맨 뒤에 데이터를 추가한다.
• size --> 큐에 얼마나 요소가 쌓였는지 수치를 보여준다.
• front --> 큐의 가장 앞을 가리키는 포인터
• rear --> 큐의 가장 뒤를 가리키는 포인터

Javascript로 Queue구현 예시.

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

  size() {
    //return Object.keys(this.storage).length
    return this.rear - this.front 
  }
	
	// 큐에 데이터를 추가 할 수 있어야 합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
	// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size()<= 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

큐를 Class로 구현하지 않고 실제로 JS에서 사용하게 된다면 해야하는것

1.큐를 담을 배열과 push(), shift()할 함수를 미리 만들어 놓는다.
2. 큐는 세트로 항상 while을 사용하면 좋다
그 이유는 for문은 증감문에 반드시 어디부터 어디까지를 적어야 되지만
while문 같은경우는 어디부터 어디까지가 아닌 큐의 length가 0이 되면 큐가 끝나는것이기 때문에 while이 조금더 접근하기가좋다.

예를 들어보면 아래와 같다.

function paveBox(boxes) {
  //큐 문제 생성을 해 놓고 시작함
  //push , pop , size ... 등등
  const Q = boxes
  const Qpop = () => Q.shift()
  const Qpush = (e) => Q.push(e)
 
  
  //Q에 가장 첫번째에 있는 요소를 빼서 current라는 변수에 담음
  let current = Qpop() 
  let count = 1; //카운트는 current 5를 하나 뺏기 때문에 1을 넣음. 
  let resultArray = []; //추후 count를 담을 배열 

  //큐 문제는 세트로 무언가가 필요함. <= while이 필요.
  //큐를 종료하는 시점 => 큐에 요소가 없을 때 
  while(Q.length !==0){
    if(current >= Q[0]){
      Qpop()
      count++
    } else {
    //resultArray에다가 지금까지 카운트한 숫자를 넣고 카운터를 초기화 한후 current의 값을 Q[0]번째 인덱스로 바꾼다.
     resultArray.push(count)
     count = 1    
     current = Q[0]
     Qpop() 
     //Qpop() 을 하는 이유는 하지 않으면 자기자신과 한번 비교하기 때문에 카운터가 1더 늘어나게됨.
    }
    
  }

  resultArray.push(count)
  return Math.max(...resultArray)
}