[자료 구조와 알고리즘] 덱(Deque)

 

 

 

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

 

덱(Deque)

 

 

 

 

📍 덱(Deque)

👉🏻 데이터의 삽입과 제거를 head, tail에서 자유롭게 할 수 있음

👉🏻 덱을 이용하여 스택, 큐를 모두 구현할 수도 있음

 

 

 

📍 덱의 추상 자료형

[ Deque.mjs ]

import { DoublyLinkedList } from './DoublyLinkedList.mjs';

class Deque {
    constructor() {
        this.list = new DoublyLinkedList();
    }

    printAll() {
        this.list.printAll();
    }

    // O(1)의 성능
    addFirst(data) {
        this.list.insertAt(0, data);
    }

    // O(1)의 성능
    removeFirst() {
        return this.list.deleteAt(0);
    }

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

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

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

export { Deque };

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

let deque = new Deque();

console.log("===== addFirst =====");
console.log(`isEmpty: ${deque.isEmpty()}`);
deque.addFirst(1);
deque.addFirst(2);
deque.addFirst(3);
deque.addFirst(4);
deque.addFirst(5);
deque.printAll();

console.log(`isEmpty: ${deque.isEmpty()}`);
console.log("\n");

console.log("===== removeFirst =====");
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();
deque.removeFirst();
deque.printAll();

console.log(`isEmpty: ${deque.isEmpty()}`);
console.log("\n");

console.log("===== addLast =====");
deque.addLast(1);
deque.addLast(2);
deque.addLast(3);
deque.addLast(4);
deque.addLast(5);
deque.printAll();

console.log(`isEmpty: ${deque.isEmpty()}`);
console.log("\n");

console.log("===== removeLast =====");
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();
deque.removeLast();
deque.printAll();

console.log(`isEmpty: ${deque.isEmpty()}`);
console.log("\n");

👉🏻 printAll : 모든 데이터 출력

 

👉🏻 addFirst : head에 데이터 삽입

👉🏻 removeFirst : head에서 데이터 제거

👉🏻 addLast: tail에 데이터 삽입

👉🏻 removeLast: tail에서 데이터 제거

👉🏻 isEmpty: 리스트 비었는지 체크