코플릿[자료구조] Stack & Queue [BEB 6th]013일차

💃문제를 해결하는데는 다양한 방법이 있다.

 

01_[Stack]구현 

//내장객체Array.prototype메서드로 되는것을... 구현해보자!
class Stack {
  constructor() {
    this.storage = {}; //데이터를 저장할 Object 타입의 storage
    this.top = 0;  //포인터일뿐.
  }

  size() { //스택에 추가된 데이터의 크기를 리턴
    return this.top;
  }

  push(element) { //스택에 데이터를 추가할 수 있어야 합니다.
    this.storage[this.top] = element;
    this.top += 1;
  }
	
  pop() { //가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴
    if (this.size() <= 0) { 
      return;
    }

    const result = this.storage[this.top -1]; //배열내 엘리먼트의 인덱스를 가리켜야하기때문에 -1
    delete this.storage[this.top -1];
    this.top -= 1;
    
    return result;
  }
}​

 

 

 

02_[Queue]구현

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0; //1️⃣전체 사이즈확인하고 엘리먼트들어가야할 위치를 파악해야해서 
  }
// [ 0, 1, 2, 3, 4, 5 ] //size: 6 (인덱스5까지)
  size() {
    return this.rear - this.front //4️⃣이미 맨끝 뒤(인덱스6)빈칸을 가리키고있음.
  }                                 //사이즈 업데이트 계산
	
	// 큐에 데이터를 "제일끝에" 추가 할 수 있어야 합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1; //2️⃣인덱스추가
  }
	
	// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
    if (this.size() === 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1; //
//     v
// [0, 1, 2, 3, 4, 5 ] //3️⃣이문제에서만; 삭제되는것이 아닌 인덱스가 옮겨갈뿐;
    return result;
  }
}​

 

 

 

03_[Stack]브라우저 뒤로가기 앞으로가기
😱새로운 페이지를 접속하게 되면 "앞으로 가기" 버튼이 비활성화돼서 다시 보고 싶던 페이지로 갈 수 없었 ㅋ
string, -1, 1 이렇게 3가지 타입으로 들어올예정.
🤖있을 경우 !== 0

function browserStack(actions, start) {
  // TODO: 여기에 코드를 작성합니다.
  let prev = [];
  let now = start; 
  let next = []; //(const아닌; 선언헀다면 pop으로 하나하나빼줘야함;) let으로 선언했기때문에 next = [];가능한것.
//["B", "C", -1, "D", "A", -1, 1, -1, -1];
  if (typeof start !== "string") { //처음부터 앞으로가기1 또는 뒤로가기-1들어오면 반칙이쥐
    return false;
  }
  for(let i=0; i<actions.length; i++){
    if (typeof actions[i] === "string") {
      prev.push(now) //원래있던 A페이지 뒤로가기스택에 넣어줌
      now = actions[i] //새로받은 B페이지
      next = []; //새로운페이지가면 다버려버림😱
    }
    else if (actions[i] === -1 && prev.length !== 0) {//뒤로가기 && prev가있을경우
      next.push(now) //원래 있던 페이지를 next 스택에 넣고
      now = prev.pop()//prev 스택의 맨뒤값을가져와서 'top에 있는 페이지'로 이동 now //prev 스택의 값을 pop..이미된거 ㅋㅋ
    }
    else if (actions[i] === 1 && next.length !== 0) { //앞으로 가기
       prev.push(now)//now 원래 있던 페이지를 prev 스택에 넣고 
       now = next.pop()//next 스택의 top에 있는 페이지로 이동한 뒤 //next 스택의 값을 pop 이미했음
    }
    //여기서 리턴하면 안됨. 🥵엘리먼트 하나뿐!
  }
  return [prev, now, next];
}​

 

 

 

04_[Queue] 박스포장
🤖findIndex() 

findIndex	판별 함수를 만족하는 첫 식별자 반환 arr.findIndex(callback)	반환타입: number 없다면 -1	원하는 요소의 식별자 찾기 원하는 요소를 찾자마자 메서드를 종료
find	판별 함수를 만족하는 첫 요소를 반환 arr.find(callback) callback(element, index, array)	반환타입: 찾은 요소의 타입 없다면 undefined	원하는 요소 찾기 원하는 요소를 찾자마자 메서드 종료(뒤에있는건 나몰라라)
indexOf	인자로 받은 값을 찾아 맞는 식별자 반환 arr.indexOf(search, fromIndex)	반환타입: number 없다면 -1	원하는 요소의 식별자 찾기 원하는 요소를 찾자마자 메서드를 종료

🤖화살표함수 표현방식

//방법1
boxes.findIndex(fn => boxes[0] < fn);​

//방법2
boxes.findIndex((el)=>{return boxes[0] < el } )

🤖splice()배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경

🤖[팁팁팁]큐가나왔다면!! while 또는 isEmpty가 필요할것이다! (심지어 isEmpty가 존재하는줄알았다구)

function isEmpty(arr) {
  for (let i=0; i<arr.length; i++) {
    if (arr[i] !== undefind){
      return false;
    }
  } 
  return true;
}

코드

function paveBox(boxes) {
  //들어올케이스 [1, [9, 5, 7] 또는 [95, 90, 99, 99, 80, 99]
  let max = 0;
  while (boxes.length > 0) {
    let maxIndex = boxes.findIndex((el)=>{return boxes[0] < el } ) //첫번째1보다 큰 제일 첫번째 큰수 9의 인덱스[1] 1명나간다
    //findIndex() 만족하면 maxIndex에들어가고, 불만족이면 -1이 maxIndex에들어간다.
    if (maxIndex === -1 ) { //찾지못한경우 -1반환
      if (max < boxes.length){/////2<4
        max = boxes.length ////4
      } 
      boxes.splice(0, boxes.length) ////다날아감
    } else {
      if (max < maxIndex) {  ////0<2
        max = maxIndex //[1] -1 ////2
      }
      boxes.splice(0, maxIndex) //맨앞부터 지우기 (1이 날아감) ///[99, 99, 80, 99]
    }
  }
  return max
}​

 

REFERENCE
🤖Math.max() 가장큰숫자반환
🤖...전개연산자

function paveBox(boxes) {
    let answer = [];
    
    // boxes 배열이 0보다 클 때까지 반복합니다.
    while(boxes.length > 0){
        let finishIndex = boxes.findIndex(fn => boxes[0] < fn);
        
        if(finishIndex === -1){
            // 만약 찾지 못했다면 answer에 boxes 배열의 길이를 넣은 후, boxes 내부의 요소를 전부 삭제합니다.
            answer.push(boxes.length);
            boxes.splice(0, boxes.length);

        } else {
            // 만약 찾았다면, 해당 인덱스를 answer에 넣고, boxes에서 그만큼 제외합니다.
            answer.push(finishIndex);
            boxes.splice(0, finishIndex);
        }
    }

    // 결과물을 반환합니다.
    return Math.max(...answer);
}​

 

REFERENCE 마이엕 reduce활용

function paveBox(boxes) {
    let numArr = [];
    let count = 1;
    boxes.reduce((pre, cur) => {
        if (pre >= cur) {
            count++
            return pre
        } else if (pre < cur) {
            numArr.push(count)
            count = 1;
            return cur
        }    
    })
    numArr.push(count)
    return Math.max(...numArr);
}​

[Javascript/Array] find, findIndex, indexOf (배열 검색)

 

 

 

05_(Advanced)[Queue]프린터
🤖안비어있는ㅋ(채워진) 빈배열생성 방법 fill(뭘로, 어디서부터, 어디까지) 

//방법1
for(let i=0; i<bufferSize; i++){
  queue.push(0); //0으로채워줌[0,0]
}​
//방법2
let arr = Array(bufferSize).fill(0) //0으로 채운 []생성

function queuePrinter(bufferSize, capacities, documents) {
  let queue = [];
  let time = 0;

  for(let i=0; i<bufferSize; i++){
      queue.push(0); //0으로채워줌[0,0]
  }
  let nowDocu = documents.shift()
  queue.push(nowDocu)
  queue.shift()

  let bufferCapa = nowDocu //bufferCapa = 7
  time++

  while(bufferCapa) {  //bufferCapa=7
    bufferCapa -= queue.shift()  //7-0 bufferCapa-queue.shift() =bufferCapa
    nowDocu = documents.shift()
    if (bufferCapa+nowDocu <= capacities) {
      queue.push(nowDocu)
      bufferCapa+=nowDocu //bufferCapa + nowDocu = bufferCapa
    } else {
      queue.push(0)
      documents.unshift(nowDocu)//못넣은거 다시 documents 원복
    }
    time++
  }
  return time
}​

REFERENCE 

function queuePrinter(bufferSize, capacities, documents) {
    let count = 0;
    let queue = [];
    let totalBufferVolume = 0;

    // queue에 bufferSize만큼 0을 삽입합니다. (queue에 들어갈 요소의 고정 갯수를 만들어 주는 과정입니다.)
    for(let i = 0; i < bufferSize; i++){
        queue.push(0);
    }
    
    // ~23번째 줄까지의 코드는 프린터를 처음 실행했을 때를 다룹니다.
    // documents 배열에서 제일 앞의 있는 요소를 하나 빼내 currentDocument에 할당합니다.
    let currentDocument = documents.shift();
    
    // queue의 제일 앞에 currentDocument를 삽입하고, 제일 마지막 요소를 없앱니다.
    queue.unshift(currentDocument);
    queue.pop();
    
    // totalBufferVolume(총 용량)에 currentDocument의 크기를 합칩니다.
    totalBufferVolume = totalBufferVolume + currentDocument;

    // 1 초가 지났다는 것을 count를 증가하며 나타냅니다.
    count++;
    
    // totalBufferVolume(총 용량)가 0이 될 때까지 반복합니다.🤗 documents가비었다고끝내면안된다!
    while(totalBufferVolume){
        
        // totalBufferVolume(총 용량)에 queue에 있는 마지막 요소의 용량을 제거합니다.
        totalBufferVolume = totalBufferVolume - queue.pop();
        
        // documents 배열에서 제일 앞의 있는 요소를 하나 빼내 currentDocument에 할당합니다.
        currentDocument = documents.shift();
        
        // 만약 현재 문서와 총 용량을 더했을 때, 최대 용량(capacities)보다 작거나 같다면
        if(currentDocument + totalBufferVolume <= capacities){

            // queue에 currentDocument를 삽입하고 totalBufferVolume(총 용량)에 currentDocument 용량을 추가합니다.
            queue.unshift(currentDocument);
            totalBufferVolume = totalBufferVolume + currentDocument;

            // 만약 현재 문서와 총 용량을 더했을 때, 최대 용량(capacities)보다 크다면
        }else{

            // 다시😗 documents에 currentDocument를 집어넣고 queue에는 0을 삽입합니다.
            documents.unshift(currentDocument);
            queue.unshift(0);
        }

        // 한 번 반복할 때마다 count(초)를 올립니다.
        count++;
    }
    
    // count를 반환합니다.
    return count;
}

REFERENCE 마이엕 

function queuePrinter(bufferSize, capacities, documents) {
    let pre = documents.shift()
    let size = 0;
    let time = 0;
    let arr = Array(bufferSize).fill(0) //0으로 채운 []생성

    size += pre
    arr.push(pre)
    arr.shift();
    time++

    while (size) {
        size -= arr.shift();
        pre = documents.shift()
        if ((size+pre) <= capacities) { //🙃capacities들어가기전에 계산
            arr.push(pre)
            size += pre //이제진짜더해줌
        } else {
            arr.push(0)
            documents.unshift(pre); //😁documents에 다시되돌려드림
        }
        time++
    }
    return time
}