자료구조 덱(deque) 구현하기 (JS)

REASON·2022년 10월 14일
0

자료구조

목록 보기
15/15

덱(Double Ended Queue)은 양쪽 끝에서 삽입, 삭제가 가능한 자료구조이다.

  • 데이터 추가 O(1)
  • 데이터 삭제 O(1)
  • 맨 앞, 맨 뒤 데이터 확인 O(1)

배열로 구현했기 때문에 배열 내장 메서드를 사용할 수도 있으나,
unshift나 shift를 사용하면 데이터가 많을 때 시간복잡도 O(1)에 데이터를 추가, 삭제할 수 없을 것이므로 다른 방법으로 구현했다.
배열 대신 연결 리스트로 구현할 수도 있다.

이전에 큐를 구현했던 것처럼 원형으로 구현한다면
선형으로 구현한 것보다 공간을 아껴서 사용할 수도 있을 것이다.

구현한 메서드

  • pushFront : 맨 앞에 요소 추가
  • pushBack : 맨 뒤에 요소 추가
  • popBack : 맨 뒤 요소 제거
  • popFront : 맨 앞 요소 제거
  • size : 현재 존재하는 요소 개수
  • isEmpty : 덱이 비어있는지 확인
  • front : 맨 앞 요소 확인
  • back : 맨 뒤 요소 확인
function Deque(max = 100) {
  this.dq = Array(max);
  this.head = Math.floor(max / 2);
  this.tail = Math.floor(max / 2);
}

Deque 생성자 함수를 만들어 주었다. 인스턴스를 만들 때 배열의 길이를 받도록 하였다.
head와 tail은 받은 max 값에서 2를 나눈 후 소수점 제거를 위해 Math.floor를 사용했다.
시작 지점을 2로 나눈 이유는 덱의 경우 앞에 데이터를 추가할 수도 있고, 뒤에 추가할 수도 있기 때문이다.

pushFront

맨 앞에 요소를 추가하는 메서드이다.

Deque.prototype.pushFront = function (num) {
  if (0 >= this.head) return console.error(`덱 크기 초과`);
  this.dq[--this.head] = num;
};

현재 head값을 1 감소 시킨 상태에서 추가할 요소를 넣어주면 된다.
배열의 크기를 고정시켜놨기 때문에 범위를 초과했을 때 에러를 반환하도록 했다.

pushBack

맨 뒤에 요소를 추가하는 메서드이다.
pushFront와 마찬가지로 배열의 크기를 벗어났을 때 예외처리를 해주었다.

Deque.prototype.pushBack = function (num) {
  if (this.dq.length <= this.tail) return console.error(`덱 크기 초과`);
  this.dq[this.tail++] = num;
};

popBack

맨 뒤 요소를 제거하는 메서드이다.
굳이 다른 데이터로 덮어쓸 필요 없이 tail 값만 감소시켜주기만하면 된다.

Deque.prototype.popBack = function () {
  this.tail--;
};

popFront

popBack과 마찬가지로 구현!
head는 ++ 해주면 된다.

Deque.prototype.popFront = function () {
  this.head++;
};

size

tail에서 head를 빼면 현재 요소의 개수를 확인할 수 있다.

Deque.prototype.size = function () {
  return this.tail - this.head;
};

isEmpty

head와 tail이 같을 때는 비어있는 것으로 간주한다.

Deque.prototype.isEmpty = function () {
  return this.head === this.tail;
};

front

맨 앞의 요소를 반환하는 메서드


Deque.prototype.front = function () {
  return this.dq[this.head];
};

back

맨 뒤의 요소를 반환하는 메서드

Deque.prototype.back = function () {
  return this.dq[this.tail - 1];
};

예전에 연결 리스트 구현할 때에 비하면 완전 천사같던 스택, 큐, 덱 구현을 마쳤다.
이렇게 구현해도 되는진 잘 모르겠지만 테스트 했을 때 문제 없으면 괜찮지 않을까...!

profile
블로그 티스토리로 이전했어요! ⇒ https://reasonz.tistory.com/

0개의 댓글