알고리즘 실습: 대기열

대기열에 대해 배우기 시작할 때까지 내가 연습했던 대부분의 알고리즘 문제는 배열, 문자열 및 객체와 관련되었습니다. 즉, 대기열에 도입되면서 면접 문제와 알고리즘에 필요한 다양한 데이터 구조에 대한 이해가 확장되었습니다. 대기열의 초기 구현에서 배열을 사용하여 대기열에 대한 클래스를 만드는 방법을 배웠기 때문에 도움이 됩니다. 배열에 익숙해지면 배열과 대기열 간의 관계를 그리면 대기열을 훨씬 쉽게 이해할 수 있습니다.

대기줄

큐는 데이터를 순서대로 보유하며 큐에 들어가는 데이터의 첫 번째 인스턴스는 큐에서 나가는 데이터의 첫 번째 인스턴스이기도 합니다. Stephen Grider의 Udemy 과정에서 그는 프로세스를 쉽게 기억할 수 있는 방법으로 "FIFO"또는 "선입선출"이라는 약어를 사용합니다. 생각나는 예는 샌드위치 가게에서 주문하는 것입니다. 들어가서 티켓을 뽑으면 이전 티켓을 호출한 후 주문을 하기 위해 티켓을 호출합니다. 더 일찍 대기열에 들어선 다른 고객보다 먼저 샌드위치를 ​​​​얻을 수 있다면 불공평 할 것입니다. 대기열에는 건너뛰기가 없습니다. 다른 예로는 음악 재생 목록(셔플 제외) 또는 영화 스트리밍 서비스 대기열이 있습니다. 현재 프로그램이나 영화가 끝나면 스트리밍 서비스가 이미 대기 중이거나 다음 에피소드나 영화가 자동 재생되도록 준비하고 있습니다.

대기열 데이터 구조 구현

대기열에서 개별 데이터 조각을 추가 및 제거하는 기능을 사용하여 대기열 데이터 구조를 생성하라는 요청을 받았습니다.

배열 데이터 구조와 일부 배열 메서드를 사용하여 대기열의 기능을 구축하는 것으로 시작할 수 있습니다.

class Queue {
//create an empty array
}

class Queue {
  constructor() {
    this.data = [];
  }
/* data will be an array that is a property of each instance of a queue that is created. 
The "this" keyword refers to the queue instance.
*/
}

다음 단계는 Queue 클래스에 대한 add 메서드를 만드는 것입니다.

class Queue {
  constructor() {
    this.data = [];
  }

  add() {
  /* add will take in an argument of some data, which we can call record. add will take the record and place it into the queue. 
*/
  }
}

class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }
}

unshift 배열 방법은 배열 앞에 데이터의 새 인스턴스를 배치합니다. 따라서 이제 대기열 인스턴스에 대한 인수로 add를 호출할 때마다 대기열에 새 레코드가 추가됩니다.

우리는 제거 방법으로 넘어갑니다.

class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }

  remove() {
  // Use the array method pop to remove the last record in the array, which will allow us to remove the next record in the queue. 
  }
}

class Queue {
  constructor() {
    this.data = [];
  }

  add(record) {
    this.data.unshift(record);
  }

  remove() {
    return this.data.pop(); 
  }
  //remember to include the return keyword so it returns the queue record we just removed. 
}

자원

Stephen Grider's Algorithms and Data Structures Udemy Course

Interview Cake