목차

• Dequeue이란?
• Dequeue은 언제 사용할까?
• Dequeue 시간복잡도
• JS로 Dequeue 구현하기
• Ref

Dequeue이란?

• Dequeue란 double-ended queue의 약자입니다.
• 스택과 큐를 합친 자료구조로서 양쪽 모두에서 삽입과 삭제가 가능합니다.
  

Dequeue은 언제 사용할까?

• 주로 스케줄링에 많이 사용됩니다. 스케줄링의 넓은 의미는 자원을 효율적으로 사용하기 위해 자원을 사용하는 순서를 결정짓는 작업입니다

• 스택으로 구현했는데, 먼저 있던 데이터에 우선순위를 두고싶을때

• 큐로 구현했는데, 최근에 들어온 데이터에 우선순위를 두고싶을때

Dequeue 시간복잡도

• Data를 삽입하는 경우 O(1)
• Data를 삭제하는 경우 O(1)
• Data를 찾는 경우 최악의 경우 O(n)

JS로 Dequeue 구현하기

• Dequeue의 ADT : ADT란 추상 자료형이라고도 하며, 데이터를 구체적으로 구현하는 방식은 생략하고 데이터의 추상적인 형태와 데이터를 이루는 방법만을 정해놓은 것입니다.

  ADT	설명
  init()	덱을 초기화한다.
  is_empty()	덱이 공백상태인지를 검사한다.
  add_front(item)	덱의 앞에 요소를 추가한다.
  add_rear(item)	덱의 뒤에 요소를 추가한다.
  delete_front()	덱의 앞에 있는 요소를 반환한 다음 삭제한다
  delete_rear()	덱의 뒤에 있는 요소를 반환한 다음 삭제한다.
  get_front()	덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다.
  get_rear()	덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다
  print()	덱을 출력한다

배열을 이용해 Dequeue구현

class DequeueByArray {
  constructor() {
    this.arr = [];
  }

  init() {
    this.arr = [];
  }

  isEmpty() {
    return this.arr.length === 0;
  }

  add_front(item) {
    this.arr.unshift(item);
  }

  add_rear(item) {
    this.arr.push(item);
  }

  delete_front() {
    return this.arr.shift();
  }

  delete_rear() {
    return this.arr.pop();
  }

  get_front() {
    console.log(this.arr[0]);
  }

  get_rear() {
    console.log(this.arr[this.arr.length - 1]);
  }

  print() {
    if (this.isEmpty()) console.log('Dequeue is empty');
    console.log(this.arr.reduce((acc, cur) => (acc += `${cur} `), ''));
  }
}
let deque = new DequeueByArray();

deque.add_front(1); // front에 1 추가 => 1
deque.add_rear(2); //  rear에 2추가  => 1 2
deque.print(); //   1 2  출력

deque.add_front(3); // front에 3추가 => 3 1 2
deque.add_rear(4); // rear에 4 추가 => 3 1 2 4
deque.print(); // 3 1 2 4 출력

deque.delete_front(); // front 제거 => 1 2 4
deque.print(); // 1 2 4 출력

deque.delete_rear(); // rear 제거  => 1 2
deque.print(); // 1 2 출력

deque.get_front(); //  front 확인 => 1 출력
deque.get_rear(); // rear 확인 =>  2 출력
deque.print(); // 확인만 하고 값을 제거하지 않았기 때문에 1 2 출력

deque.init(); // 초기화
console.log(deque.isEmpty()); // 초기화 했으므로 비어있기 때문에 true 출력
deque.print(); // Dequeue is Empty출력

이중연결 리스트를 이용해 Dequeue 구현

• shift, unshift , push, pop 을 사용하여 배열로 구현할 수 있지만, 이 경우 삽입과 삭제이후 재정렬을 해야되기 때문에 시간복잡도가 O(n)이 걸릴 수 있다. 따라서 이중연결리스트를 사용해서 구현을 했습니다.

  class Node {
    constructor(data) {
      this.data = data;
      this.prev = null;
      this.next = null;
    }
  }
  
  class Dequeue {
    constructor() {
      this.head = null;
      this.tail = null;
      this.size = 0;
    }
    
    //  Dequeue 초기화  
    init() {
      this.head = null;  // head 초기화
      this.tail = null;  // tail 초기화
      this.size = 0;     // 크기 초기화
    }
  
    // Dequeue이 비어있는가? 
    isEmpty() {   
      return this.size == 0;   
    }
  
    // front값 삭제 
    add_front(item) {
      //if list is empty
      if (this.isEmpty()) {
        this.head = new Node(item);
        this.tail = this.head;
      } else {
        let newNode = new Node(item);
        newNode.next = this.head;
        this.head.prev = newNode;
        this.head = newNode;
      }
      this.size++;
    }
  	
    // rear값 삭제 
    add_rear(item) {
      //if list is empty
      if (this.isEmpty()) {
        this.tail = new Node(item);
        this.head = this.tail;
      } else {
        let newNode = new Node(item);
        newNode.prev = this.tail;
        this.tail.next = newNode;
        this.tail = newNode;
      }
      this.size++;
    }
  
    // front 삭제
    delete_front() {
      if (this.isEmpty()) return null;
  
      let data = this.head.data;
  
      //if head(=tail) is target
      if (this.head == this.tail) {
        this.head = null;
        this.tail = null;
      } else {
        this.head = this.head.next;
        this.head.prev = null;
      }
      this.size--;
      return data;
    }
  
    // rear 삭제
    delete_rear() {
      if (this.isEmpty()) return null;
  
      let data = this.tail.data;
  
      //if head(=tail) is target
      if (this.head == this.tail) {
        this.head = null;
        this.tail = null;
      } else {
        this.tail = this.tail.prev;
        this.tail.next = null;
      }
      this.size--;
      return data;
    }
  
    // front 값 확인
    get_front() {
      console.log(this.head.data);
    }
  
    // rear값 확인
    get_rear() {
      console.log(this.tail.data);
    }
  
    // Dequeue 출력 
    print() {
      let result = '';
      let current = this.head;
  
      if (current === null) console.log('Dequeue is Empty');
      else {
        while (current.next) {
          result += `${current.data} `;
          current = current.next;
        }
        result += current.data;
        console.log(result);
      }
    }
  }
  
  let deque = new Dequeue();
  
  deque.add_front(1); // front에 1 추가 => 1
  deque.add_rear(2); //  rear에 2추가  => 1 2
  deque.add_front(3); // front에 3추가 => 3 1 2
  deque.add_rear(4); // rear에 4 추가 => 3 1 2 4
  deque.print(); //   3 1 2 4 출력
  
  deque.delete_front(); // front 제거 => 1 2 4
  deque.print(); // 1 2 4 출력
  
  deque.delete_rear(); // rear 제거  => 1 2
  deque.print(); // 1 2 출력
  
  deque.get_front(); //  front 확인 => 1 출력
  deque.get_rear(); // rear 확인 =>  2 출력
  deque.print(); // 확인만 하고 값을 제거하지 않았기 때문에 1 2 출력
  
  deque.init(); // 초기화
  console.log(deque.isEmpty()); // 초기화 했으므로 비어있기 때문에 true 출력
  deque.print(); // Dequeue is Empty출력
  

Ref

• 두콩