2021년 12월

2021-12-07#

덱(Deque)#

덱(Deque)이란 Double-Ended Queue의 줄임말이다. 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조의 한 형태이다.

두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다. 큐와 스택을 합친 형태로 생각할 수 있다.

양 끝에서만 데이터를 넣고 양 끝에서 뺄 수 있는 자료구조

입력이 한쪽 끝으로만 가능하도록 설정한 덱인 입력 제한 덱(Scroll), 출력이 한쪽 끝으로만 가능하도록 설정한 덱인 출력 제한 덱(Shelf)가 있다.

deque

덱의 주요 기능#

push_front: 덱의 앞에 데이터를 삽입
push_back: 덱의 뒤에 데이터를 삽입
pop_front: 덱의 앞에서 데이터를 뺌
pop_back: 덱의 뒤에서 데이터를 뺌
front: 덱의 가장 앞에 있는 데이터
back: 덱의 가장 뒤에 있는 데이터

덱의 장점#

펠린드롬 예시#

# 예시 1
def isPalindrome(self, s: str) -> bool:
    strs=[]
    for char in s :
        if char.isalnum():
            strs.append(char.lower())
# 펠린드롬 여부 판별
while len(strs)>1 :
    if str.pop(0) != str.pop():
        return False
    return True

예시1의 실행 결과⏲ : 304밀리초

# 예시 2
def isPalindrome(self, s: str) -> bool:
    strs: Deue = collection.deque() # 자료형을 데크로 선언
    for char in s :
        if char.isalnum():
            strs.append(char.lower())
# 펠린드롬 여부 판별
while len(strs)>1 :
    if str.popleft() != str.pop():
        return False
    return True

예시2의 실행 결과⏲ : 64밀리초

예시2가 예시1의 리스트 풀이 대비 거의 5배 가까이 더 속도를 높일 수 있었던 이유는?
리스트의 pop(0)은 O(n)인데 반해, 데크의 popleft()는 O(1)이기 때문이며, 각각 n번씩 반복하면 리스트 구현은 O(n2), 데크 구현은 O(n)으로 성능 차이가 크다. 최적화된 내부 기능을 잘 활용해 성능을 좀 더 높일 수 있는것이다 !!
일례로 백준 7576번 “토마토” 문제에서 익은 토마토를 리스트에 담도록 코드를 짜면 시간초과로 통과에 실패하지만, 데크를 사용하면 무난히 통과한다

덱의 구현#

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;
})();

출처: jjudrgn's note, takeU, guma.log