Deque - 개념과 구현

📌 Deque 이란 무엇인가 ?

덱은 양쪽 끝에서(head & tail) 삽입과 제거 모두 가능한 자료 구조의 한 형태이다.

• 두 개의 포인터를 사용하여, 양쪽에서 삭제와 삽입을 발생시킬 수 있다.
  
• 이러한 특성 때문에 덱은 스택과 큐를 전부 구현할 수 있다.

📌 Deque 의 추상자료형

printAll : 모든 데이터 출력

addFirst : head에 데이터 삽입

removeFirst : head에서 데이터 제거

addLast : tail에 데이터 삽입

removeLast : tail에서 데이터 제거

isEmpty : 리스트 비었는지 체크

[구현]

덱의 구형는 이전에 스태고가 큐의 구현에서 필요한 대부분의 기능을 구현했기 때문에 간단하다.
[Deque.mjs]

✅ printAll

  // 이중연결리스트의 printAll()함수를 호출한다.
  printAll() {
    this.list.printAll();
  }

연결리스트에서 head에 데이터 삽입, 제거는 O(1)의 성능을 보였다. 이를 이용해서 addFirst와 removeFist()를 아주 간다하게 구현할 수 있다.

✅ addFirst

• list의 insertAt 함수를 호출하고 인덱스를 0으로 주면 O(1)의 성능으로 헤드에 삽입된다.

  addFirst() {
    this.list.insertAt(0, data);
  }

✅ removeFirst

• list의 deleteAt 함수의 인덱스를 0으로 주면 O(1)의 성능으로 데이터를 제거한다.

  removeFirst() {
    return this.list.deleteAt(0);
  }

큐를 구현할 때 DoublyLinkedList클래스 내 insertAt 함수에서 마지막 인덱스에 삽입하는 경우 tail을 이용해서 O(1)의 성능으로 삽입하도록 수정했다. addLast 함수도 insertAt 함수를 이용하면 쉽게 구현할 수 있다.

✅ addLast

• list의 insertAt 함수의 인덱스로 현재 리스트의 카운트를 넣어주면 마지막 원소의 삽입을 뜻한다.

  addLast(data) {
    this.list.insertAt(this.list.count, data);
  }

✅ removeLast

• deleteLast() 함수를 호출해서 얻은 노드를 리턴

  removeLast() {
    return this.deleteLast();
  }

✅ isEmpty

• 덱이 비었는지 아닌지 확인

  isEmpty() {
    return this.list.count == 0;
  }

자 이제 테스트 파일을 작성해보자.

[test_deque.mjs]

import { Deque } from "./Deque.mjs";

// Deque 개채 만들어주기
let deque = new Deque();

// 📌  addFrist
console.log("=== addFrist ===");
// 덱이 비었는지 isEmpty() 함수 출력
console.log(`isEmpty: ${deque.isEmpty()}`);
// addFirst 함수로 1부너 5까지 넣어준다.
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);
deque.addFirst(4);
deque.addFirst(5);
// printAll 로 모든 요소 출력
deque.printAll();
// 덱이 비었는지 isEmpty() 함수 출력
console.log(`isEmpty: ${deque.isEmpty()}`);
console.log("\n");

// 📌 removeFirst
// 호출할 때마다 printAll 함수를 호출해서 변화 출력
console.log("=== removeFirst ===");
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
// 덱이 비었는지 isEmpty() 함수 출력
console.log(`isEmpty: ${deque.isEmpty()}`);
console.log("\n");

// 📌 addLast 
// addLast 함수로 1부터 5까지 삽입
console.log("=== addLast ===");
deque.addLast(1);
deque.addLast(2);
deque.addLast(3);
deque.addLast(4);
deque.addLast(5);
deque.printAll();
// 덱이 비었는지 isEmpty() 함수 출력
console.log(`isEmpty: ${deque.isEmpty()}`);
console.log("\n");

// 📌 removeLast
console.log("=== removeLast ===");
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
// 덱이 비었는지 isEmpty() 함수 출력
console.log(`isEmpty: ${deque.isEmpty()}`);

출력!!!

예상한 대로 출력이 되었다. 덱을 이용하면 스택과 큐를 간단하게 만들 수도 있다.

• addFirst와 removeFirst를 이용하면 스택이 되고 마찬가지로 addLast와 removeLast를 이용해도 스택이 된다.

• 반대로 큐를 만들기 위해서는 addFirst와 removeLast를 사용하거나 addLast 와 removeFirst를 이용하면 된다.

with 그림으로 쉽게 배우는 자료구조와 알고리즘