10회차 스터디 공부 내용 - JS 큐(Queue) 구현하기, 사용 예제, shift메서드

잔잔바리디자이너·2022년 4월 30일
0

Study

목록 보기
15/19
post-thumbnail

shift 메서드

shift 메서드와 push 메서드를 사용하면 큐를 쉽게 구현할 수 있다.
하지만 큐 구현 연습에 앞서 먼저 shift 메서드의 동작 원리를 생각해보자.

  • shift 메서드는 첫 요소를 삭제하고 그 값을 반환한다.
const arr = [10,1,2,3]
console.log(arr.shift()) // 10
console.log(arr) // [1,2,3]
console.log(arr.length) // 3
  • delete 연산자로 배열의 첫 요소를 삭제해보자.
    삭제된 요소의 인덱스에는 empty 값이 남게되고, 배열의 길이는 그대로이다.
const arr2 = [10,20,30]
delete arr2[0] // true
console.log(arr2) // [ <1 empty item>, 20, 30 ]
console.log(arr2.length) // 3

배열 메서드인 shift, unshift가 마법처럼 요소를 삭제하는것은 아닐테고 배열의 요소를 전부 돌면서 인덱스를 한칸씩 앞당겨줄것이다. 시간복잡도는 O(n)이겠죠 뭐.

delete 연산자를 활용해서 배열 메서드를 사용하지 않고 같은 동작 구현해보자.

function newArray(array){
	this.array = array
  	this.length = array.length
	
  	this.shift = function(){
    if(this.length !==0){
       const deleteElement = array[0]
       delete array[0]
      // 인덱스 1번의 요소 부터 배열의 length -1 요소 까지 돌면서 모든 요소의 순서를 한칸씩 앞당겨준다.
      for(let i = 1; i < this.length; i++){
        this.array[i-1] = this.array[i]
      }
		
      // 할당 전에 length 줄여주기
      this.length = --this.array.length;
      return deleteElement
    }
  }

	// 배열 복사해서 반환
  this.getArray = function get(){
    return [...this.array]
  }
}
const array = new newArray([1,2,3,4,5,6,7,8])
array.shift()
array.length
array.getArray()

1. Queue?

First-In First-Out 먼저 들어간 요소가 먼저 빠져나오는 선입선출 방식의 자료 구조이다. 줄을 서서 선착순으로 서비스를 받는 것을 생각해보면 된다.

2. 자바스크립트로 큐 구현하기

  • 배열 메서드로 구현
    배열과 배열 메서드 shift, push를 이용해 큐 데이터 구조를 만들어 낼 수 있다. 하지만 위에서 증명해봤듯이 shift 메서드를 이용하여 큐 구조를 구현했을때 시간복잡도의 문제가 생긴다.
  • 해쉬, 링크드 리스트로 구현
    자바스크립트에서 객체(Object)는 key-value의 구조로 사용할 수 있으며, key 값을 통해 O(1) 시간으로 접근할 수 있다. 즉 일종의 해시(Hash)로 활용이 가능한데 이를 통해 큐를 구현해보자.
    1. 큐 초기화
    2. 크기 구하기
    3. 데이터 추가
    4. 데이터 추출

3. 성능 테스트?

4. 그래서 어떻게 활용해볼까?

사실 프론트에서 큐나 스택 자료구조를 직접 구현 할 필요는 없는것같다. 예제를 봐도 주로 알고리즘 문제나 코딩 테스트를 위해 함수를 만드는데 사용됐다. 어차피 백에서 처리한 데이터를 뿌려주면 프론트에서 넘겨받아서 렌더 해주는 형식의 일일테다. 그럼 DB에 접근하지 않고 브라우저에서 처리할수있는 예제는 뭐가 있을까?🤔

❌ 흠 적절한 예제가 아닌것같다. 일단 보류 ❌

생방송중에 선착순으로 생방송에 들어온 10명의 시청자에게 선물을 준다고 가정해보자. 그리고 선물을 거절한 시청자는 큐에서 제외시켜 총 10명에게만 선물을 준다.

settimeout 같은 함수를 사용하거나 유저의 행동에 따라 alert 발생시.. 이럴때 활용할 예제를 생각해보자

참조:

  1. 자바스크립트 큐 구현방법, 배열, 객체
  2. 자바스크립트 큐 구현
  3. 자바스크립트 링크드리스트 구현
  4. 데이터 스트럭쳐
  5. 알고리즘 구현, 성능 테스트
  6. 콜스택, 메세지큐

0개의 댓글