JS에서 deque는 구현되어있지않다

python에선 from collections import deque로 사용할 수 있지만, js에선 없다.

그냥 shift쓰면 되지않나?

deque의 장점은 왼쪽에서 아이템을 꺼내도 O(1)이 걸리도로 설계되어있다.(by 더블링크드리스트) 그런데 shift를 써버리면 O(리스트 길이)가 되어버린다.

구현

방향

1. 시간이 촉박한 코테에서 바로 구현할 수 있도록 쉽게
2. 기존 파이썬의 명령어 append, popleft를 사용하도록

코드

class deque{
    constructor(){
        this.storage = {};
        this.front = 0;
        this.rear = 0;
    }
    size(){
        return this.rear - this.front;
    }
    append(element){
        this.storage[this.rear++] = element;
    }
    popleft(){
        if(this.front === this.rear){
            this.front = this.rear = 0;
            return null;
        }
        let popped_element = this.storage[this.front];
        delete this.storage[this.front];
        this.front++;
      	
      	if(this.front === this.rear){
        	this.front = this.rear = 0;
        }
        return popped_element;
    }
}