[자료구조] Deque구현 (Javascript)

August 1, 2022

Deque

Double-ended Queue 의 약자로 스택과 큐를 합친 자료구조이다.

스택(stack): LIFO(Last in First Out)로 마지막에 입력된 자료가 제일 먼저 삭제
큐(queue): FIFO(Fist in First Out)로 마지막에 입력된 자료가 제일 마지막에 삭제

Deque는 데이터 입력 방향을 앞, 뒤 지정할 수 있고 삭제 방향도 지정할 수 있다.

그렇기에 덱의 ADT를 구성하는 핵심 함수는 아래와 같다.

append (오른쪽 / 뒤에 데이터 입력)
addFirst (왼쪽 / 앞에 데이터 입력)
poll (오른쪽 / 뒤에 데이터 삭제)
pollLast (왼쪽 / 앞에 데이터 삭제)

함수의 이름은 임의로 작성

구현하기 전

구현하기 전에 Linked List에 대해 간단히 알아보자

배열같은 경우 인접한 값은 주소역시 인접하다.

그렇기에 index로 접근이 가능한것이다.(Javascript의 경우 좀 다르지만…)

왜냐하면, 배열은 0번째의 인덱스의 주소값을 가지고 있어 다른 인덱스로 접근할때 (인덱스 X 한 인덱스당 메모리크기)를 해주면 바로 접근이 가능하기 때문이다.

하지만 Linked List의 경우 주소값이 인접하지 않다.

그렇기에 배열과 다르게 값만을 갖고 있는 것이 아닌 다음 값의 주소를 갖고 있다.

그래서 Linked List의 중앙 값을 접근하고자 할때 배열보다 느릴 수 있으나, 중앙에 값을 삽입할 때는 배열보다 속도가 빠르다.

중앙에 값을 삽입할때 배열의 경우 삽입한 위치 다음의 값들은 전부 오르쪽으로 한칸씩 옮겨야하기 때문이다.

Linked List 로 구현

Node

class NodeDeque {
  constructor(value) {
    this.pre = null;
    this.next = null;
    this.value = value;
  }
}

노드는 가지고 값과 다음 노드를 가리킬 next, 이전 노드를 가리킬 pre을 갖고 있다.
처음 노드가 생성될땐 무슨 값을 가리킬지 모르니 null로 초기화한다.

Deque - constructor

class Deque {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
}

deque를 처음 생성할때 아직 노드가 없으니 head, tail은 null로 초기화한다.
크기 역시 아무것도 없으니 0으로 초기화한다.

Deque - append

  append(value) {
    const node = new NodeDeque(value);
    if (this.isEmpty()) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    node.pre = this.tail;
    this.tail = node;
    this.size++;
  }

우선 Node를 생성한다.
만일 deque가 비어있으면 head를 생성한 Node로 설정해준다.
만일 deque가 비어있지 않으면 deque의 tail의 next값을 생성한 Node로 변경해준다.
생성한 Node의 이전 Node를 deque의 tail로 설정해주고, deque의 tail을 Node로 설정해주고,
size를 증가시켜준다.

deque_append

Deque - addFirst

  addFirst(value) {
    const node = new NodeDeque(value);
    if (this.isEmpty()) {
      this.tail = node;
      this.head = node;
    } else {
      const nextNode = this.head;
      this.head = node;
      this.head.next = nextNode;
      nextNode.pre = this.head;
    }
    this.size++;
  }

우선 Node를 생성한다.
만일, deque가 비어있으면 tail과 head를 생성한 Node로 설정한다.
만일, deque가 비어있지 않으면 현재 deque의 head를 임시 저장해둔다.
그 후 deque의 head를 생성한 Node로 설정하고, head의 next를 원래 임시저장한 head로 설정한다.
그리고 임시저장한 head의 이전 노드를 현재 head로 설정한다.
deque의 size를 증가시켜준다.

deque_addFirst

Deque - poll

  poll() {
    if (this.isEmpty()) {
      return null;
    }
    if (this.getSize() === 1) {
      this.initDeque();
      return;
    }
    const value = this.head.value;
    this.head = this.head.next;
    this.head.pre = null;
    this.size--;
    return value;
  }

deque가 비어있으면 null을 반환해서 비어있음을 알린다.
반환하기 위한 value을 value변수에 저장한다.
deque의 haed를 현재 head가 가리키고 있는 값으로 변경시킨다.
head의 이전값은 없어야하므로 head의 pre를 null로 변경시킨다.
deque의 size를 감소시킨다.
기존 head를 참조하고 있던 것이 이제는 없으므로 javascript의 카비지 컬렉션이 자동으로 메모리를 해제할 것이다.
javascript처럼 자동으로 메모리 해제해 주지 않는 경우 메모리 관리를 위해 수동으로 메모리 해제를 해야한다.

deque_poll

Deque - pollLast

  pollLast() {
    if (this.isEmpty()) {
      return null;
    }
    if (this.getSize() === 1) {
      this.initDeque();
      return;
    }
    const value = this.tail.value;
    const preLast = this.tail.pre;
    preLast.next = null;
    this.tail = preLast;
    this.size--;
    return value;
  }

deque가 비어있으면 null을 반환해서 비어있음을 알린다.
반환하기 위한 value을 value변수에 저장한다.
deque의 tail 바로 앞의 값(preLast)을 tail로 변경해주기 위해 preLast의 next를 null로 변경시켜준다.
tail을 preLast로 변경시킨다.
deque의 size를 감소시킨다.
앞서 말했듯이 기존 tail을 참조하고 있는 값이 없으므로 가비지 컬렉션에 의해 자동으로 메모리를 해제할 것이다.

deque_pollLast

전체코드

class NodeDeque {
  constructor(value) {
    this.pre = null;
    this.next = null;
    this.value = value;
  }
}

class Deque {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  initDeque() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
  append(value) {
    const node = new NodeDeque(value);
    if (this.isEmpty()) {
      this.head = node;
    } else {
      this.tail.next = node;
    }
    node.pre = this.tail;
    this.tail = node;
    this.size++;
  }
  addFirst(value) {
    const node = new NodeDeque(value);
    if (this.isEmpty()) {
      this.tail = node;
      this.head = node;
    } else {
      const nextNode = this.head;
      this.head = node;
      this.head.next = nextNode;
      nextNode.pre = this.head;
    }
    this.size++;
  }
  poll() {
    if (this.isEmpty()) {
      return null;
    }
    if (this.getSize() === 1) {
      this.initDeque();
      return;
    }
    const value = this.head.value;
    this.head = this.head.next;
    this.head.pre = null;
    this.size--;
    return value;
  }
  pollLast() {
    if (this.isEmpty()) {
      return null;
    }
    if (this.getSize() === 1) {
      this.initDeque();
      return;
    }
    const value = this.tail.value;
    const preLast = this.tail.pre;
    preLast.next = null;
    this.tail = preLast;
    this.size--;
    return value;
  }
  isEmpty() {
    return this.size === 0;
  }
  getSize() {
    return this.size;
  }
  print() {
    if (this.isEmpty()) {
      console.log("비어있음");
      return;
    }
    let node = this.head;
    for (let i = 0; i < this.size; i++) {
      console.log(node.value);
      node = node.next;
    }
  }
}

코테를 풀면서

코테를 풀면서 데이터를 오른쪽, 왼쪽 모두 삽입/삭제을 해야하는 경우가 종종있다.
이런 경우 단순히 배열로 구현하게 되면 대부분 시간초과가 난다.
배열과 덱에서 앞에 값을 추가할때 성능 차이를 보면 아래와 같다.

< 1부터 100000까지 데이터 삽입 >
deque addFirst :  26ms
arr shift :  1735ms

앞에 값을 삭제할때도 마찬가지다

< 1부터 100000까지 데이터 삽입된 데이터 삭제 >
deque poll : 10ms
arr shift : 1230ms

하지만 push, pop은 배열이 더 빠르다.

deque append : 26ms
arr push : 6ms

deque pollLast : 10ms
arr pop : 4ms

그렇기에 단순히 덱을 사용해서 푼다고 모든 경우에서 속도가 빠른것이 아니다.

YUN SEO