4. 덱 ( Deque, JavaScript 구현 )

덱 ( Deque )

덱이란?

double-ended queue은 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생 시킬 수 있다.

큐와 스택을 합친 형태로 생각할 수 있다.

 

구조

덱은 앞, 뒤에서 각각 put, get을 할 수 있는 구조이다.

put는 큐에 자료를 넣는 것을, get은 큐에서 자료를 꺼내는 것을 의미한다.

front와 rear는 데이터의 앞과, 뒤를 가리키며 각각의 노드는 next와 prev로 연결돼있다.

 

언제 사용하는가?

1. 저장할 데이터 개수가 가변적일 때
2. 검색을 할 일이 거의 없을 때
3. 데이터 접근을 랜덤하게 하고 싶을 때

 

구현

기본적인 덱의 구현

const Deque = (() => {
    class Deque {
        constructor() {
            this.count = 0;
            this.front = null;
            this.rear = null;
        }
      class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
              this.prev = null;
        }
    }
    return Deque;
})()

1. put_front()

put_front(value) {
  const node = new Node(value);
  if ( !this.front ) {
    this.front = node;
    this.rear = node;
  } else {
    const next = this.front
    this.front = node
    this.front.next = next;
    next.prev = node
  }
  return ++this.count;
}

데이터 있는지 확인 후에, 없다면 front, rear 모두 새로운 노드를 넣어주고

데이터가 있다면 front를 한칸 밀고 그 자리에 새로운 노드를 넣어 prev, next 연결을 해준다. 그 후에 덱의 크기를 리턴

2. get_front()

get_front() {
  if ( !this.front ) {
    return false;
  }
  const data = this.front.data;
  this.front.prev = null;
  this.front = this.front.next;
  this.count--;
  return data;
}

데이터가 없으면 false를 리턴.

있다면 현재 front의 노드를 변수에 담고, prev연결을 끊어준 뒤

next로 이동시켜주고 덱의 크기 1 감소 후 삭제한 노드 리턴

3. put_rear()

put_rear(value) {
  const node = new Node(value);
  if ( !this.front ) {
    this.front = node;
    this.rear = node;
  } else {
    node.prev = this.rear
    this.rear.next = node;
  }
  this.rear = node;
  return ++this.count;
}

데이터 있는지 확인 후에, 없다면 front, rear 모두 새로운 노드를 넣어주고

데이터가 있다면 새로운 노드의 prev에 rear를, rear의 next에 새로운 노드를 넣어주고 크기를 1 증가시킨다.

4. get_rear()

get_rear() {
  if ( !this.front ) {
    return false;
  }
  let temp = this.rear;
  temp.prev.next = null;
  this.rear = temp.prev;
  temp = null;
  this.count--;
}

데이터가 없으면 false를 리턴.

있다면 현재 rear의 노드를 변수에 담고, next연결을 끊어준 뒤

prev로 이동시켜주고 덱의 크기 1 감소 후 삭제한 노드 리턴

5. front(), rear()

front() {
  return this.head && this.head.data;
}

rear() {
  return this.rear && this.rear.data;
}

front와 rear의 존재를 확인 후 있으면 해당 노드의 데이터를 리턴

 

전체 코드

const Deque = (() => {
    class Deque {
        constructor() {
            this.count = 0;
            this.front = null;
            this.rear = null;
        }

          put_front(value) {
          const node = new Node(value);
            if ( !this.front ) {
                this.front = node;
                  this.rear = node;
            } else {
                  const next = this.front
                this.front = node
                this.front.next = next;
                  next.prev = node
            }
            return ++this.count;
        }

          get_front() {
              if ( !this.front ) {
                return false;
            }
            const data = this.front.data;
              this.front.prev = null;
            this.front = this.front.next;
            this.count--;
            return data;
        }

          put_rear(value) {
              const node = new Node(value);
            if ( !this.front ) {
                this.front = node;
                  this.rear = node;
            } else {
                  node.prev = this.rear
                this.rear.next = node;
            }
            this.rear = node;
            return ++this.count;
        }

          get_rear() {
                        if ( !this.front ) {
                return false;
            }
              let temp = this.rear;
            temp.prev.next = null;
            this.rear = temp.prev;
            temp = null;
            this.count--;
        }

                front() {
              return this.head && this.head.data;
        }

          rear() {
              return this.rear && this.rear.data;
        }
    }
    class Node {
        constructor(data) {
            this.data = data;
            this.next = null;
              this.prev = null;
        }
    }
    return Deque;
})()