자료 알고리즘 - 덱(Deque) 이해와 효율적인 구현 방법

덱 개요

• 양쪽 끝에서 삽입과 삭제가 모두 가능합니다.
• 큐와 스택의 특징을 모두 가지고 있습니다.

덱 동작 원리

• addFirst(el) : 덱의 앞쪽에 데이터를 추가합니다.
• addLast(el) : 덱의 뒤쪽에 데이터를 추가합니다.
• removeFirst() : 덱의 앞쪽 데이터를 제거 후 반환합니다.
• removeLast() : 덱의 뒤쪽 데이터를 제거 후 반환합니다.
• peekFirst() : 덱의 앞쪽 데이터를 반환합니다.
• peekLast() : 덱의 뒤쪽 데이터를 반환합니다.
• isEmpty() : 덱이 비어있는지 확인합니다.

덱 배열 코드 예시

class Deque {
 constructor() {
  this.deque = []
 }
 
 isEmpty() {
  return this.deque.length === 0
 }
 
 addFirst(el) {
  this.deque.unshift(el)
 }
 
 addLast(el) {
  this.deque.push(el)
 }
 
 peekFirst() {
  if(this.isEmpty()) throw new Error('empty deque')
  return this.deque[0]
 }
 
 peekLast() {
  if(this.isEmpty()) throw new Error('empty deque')
  return this.deque[this.deque.length - 1]
 }
 
 removeFirst() {
  if(this.isEmpty()) throw new Error('empty deque')
  return this.deque.shift()
 }
 
 removeLast() {
  if(this.isEmpty()) throw new Error('empty deque')
  return this.deque.pop()
 }
}

위와 같이 배열로 덱 클래스를 작성하면 shift와 unshift일때 시간 복잡도가 O(n)이 됩니다.

이중 링크드 리스트로 구성해야 O(1)을 가집니다.

덱 이중 링크드 리스트 코드 예시

class Node {
 constructor(el) {
  this.item = el
  this.next = null
  this.prev = null
 }
}

class Deque {
 toggleDirection = {
  'next': 'prev',
  'prev': 'next
 }
 
 toggleDeque = {
  'front': 'rear',
  'rear': 'front'
 }
 
 constructor() {
  this.front = null
  this.rear = null
  this.size = 0
 }
 
 isEmpty() {
  return this.size === 0
 }
 
 addItem(el, deque, direction) {
  const node = new Node(el)
  if(this.isEmpty()) this.front = this.rear = node
  else {
   node[direction] = this[deque]
   this[deque][this.toggleDirection[direction]] = node
   this[deque] = node
  }
  this.size++
 }
 
 addFirst(el) {
  this.addItem(el, 'front', 'next')
 }
 
 addLast(el) {
  this.addItem(el, 'rear', 'prev')
 }
 
 peekFirst() {
  if(this.isEmpty()) throw new Error('empty deque')
  return this.front.item
 }
 
 peekLast() {
  if(this.isEmpty()) throw new Error('empty deque')
  return this.rear.item
 }
 
 removeItem(deque, direction) {
  const item = deque === 'front' ? this.peekFirst() : this.peekLast()
  this[deque] = this[deque][direction]
  if(this[deque]) this[deque][this.toggleDirection[direction]] = null
  else this[this.toggleDeque[deque]] = null
  this.length--
  return item
 }
 
 removeFirst() {
  return this.removeItem('front', 'next')
 }
 
 removeLast() {
  return this.removeItem('rear', 'prev')
 }
}

 

덱 시간 복잡도

• 덱의 모든 연산은 시간 복잡도가 O(1)입니다.
• 배열로 코드를 구성하였을 경우 front관련 연산은 O(n)입니다.

덱 장점

• 양쪽 끝에서 삽입, 삭제 연산이 모두 가능합니다.

덱 단점

• 큐나 스택보다 구현이 복잡합니다.
• 데이터 중간 삽입, 삭제 연산이 힘듭니다.

덱 활용

• 동일한 단어가 되는지 회문(팰린드롬)을 체크할 수 있습니다.