5. 덱(deque)

덱의 개념

데이터의 추가와 삭제를 head와 tail에서 자유롭게 할 수 있다.

양방향 연결 리스트를 사용하여 쉽게 구현할 수 있다.

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

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

	addFirst(data) {
		this.list.insertAt(0, data);
	}
	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 =====');
console.log(`isEmpty: ${deque.isEmpty()}`);
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()}`);

λ node test_Dqque.mjs 
===== addFirst =====
isEmpty: true
[5,4,3,2,1]
isEmpty: false


===== removeFirst =====
[4,3,2,1]
[3,2,1]
[2,1]
[1]
[]
isEmpty: true


===== addLast =====
isEmpty: true
[1,2,3,4,5]
isEmpty: false


===== removeLast =====
[1,2,3,4]
[1,2,3]
[1,2]
[1]
[]
isEmpty: true