🔥 그림으로 쉽게 배우는 자료 구조와 알고리즘
덱(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: 리스트 비었는지 체크