JavaScript Deque(Double-Ended Queue) - 덱/데크 만들기, Data Structures

이전 원형 큐(Circular Queue - 또는 환상 큐)처럼 JavaScript의 Array 객체의 메서드를 사용하지 않고 덱/데크(Deque - Double-Ended Queue)를 만들어 보겠습니다.

​

덱/데크(Deque - Double-Ended Queue)는 양쪽 모두에서 데이터를 넣고 가져오는 구조입니다.

​

프로그램에서는 버퍼를 사용하기 때문에 방향의 개념이 없습니다. 그래서 큐의 뒤에서 데이터를 넣거나 가져오기 위해서 rear의 위치를 계산하여 처리하고 큐의 앞에서 데이터를 넣거나 가져오기 위해서 front의 위치를 계산하여 처리해야 합니다. front와 rear의 위치를 사용하여 데이터를 넣거나 가져옵니다.

[파란색 화살이 front, 주황색 화살이 rear]

​

큐의 뒤에 데이터를 넣으려면 먼저 rear의 위치를 증가시키고 큐의 앞에 데이터를 넣으려면 먼저 front의 위치를 감소시켜야 합니다. 반대로 큐의 뒤에 있는 데이터를 가져가면 rear의 위치를 감소시키고 큐의 앞에 있는 데이터를 가져가면 front의 위치를 증가시켜야 합니다.

[파란색 화살이 front, 주황색 화살이 rear]​

 

그래서 프로그램에서는 큐를 기준으로 구동되기 때문에 데이터를 넣을 때 rear의 위치가 큐의 마지막 위치(queueSize - 1)에 있으면 rear의 위치를 큐의 첫 번째 위치(0)로 이동시키고 front의 위치가 큐의 첫 번째 위치(0)이면 front의 위치를 큐의 마지막 위치(queueSize - 1)로 이동시켜 데이터 넣습니다.

 

반대로 데이터를 가져간 후 rear의 위치가 큐의 첫 번째 위치(0)이면 rear의 위치를 큐의 마지막 위치(queueSize - 1)로 이동시키고 front의 위치가 큐의 마지막 위치(queueSize - 1)에 있으면 front의 위치를 큐의 첫 번째 위치(0)로 이동시킵니다.

이렇게 함으로써 큐를 빈 공간 없이 사용할 수 있습니다.

​

덱/데크(Deque)가 생성되면 front와 rear의 위치가 -1입니다. 이 상태가 큐가 비어있는 상태입니다.

첫 번째로 큐의 앞이나 뒤에 데이터를 넣으려면 무조건 큐의 첫 번째 위치(0)에 들어갑니다.

[파란색 화살이 front, 주황색 화살이 rear]

 

​

​

덱/데크(Deque - Double-Ended Queue) 객체 생성하기

​

JavaScript에서 객체 생성하는 방법은 "JavaScript Object - 객체 생성"(https://carrotweb.tistory.com/184)를 참고하시기 바랍니다.

​

function()으로 Deque 객체를 선언하겠습니다.

객체 생성할 때 큐의 크기를 받아서 큐를 초기화합니다.

var Deque = function(queueSize) {
	// Array 객체 생성
	this.queue = [];
	// 데이터 위치
	this.front = -1;
	this.rear = -1;
	// 큐의 크기
	this.queueSize = queueSize;
	// 큐 초기화
	for (var index = 0; index < queueSize; index++) {
		this.queue.push(null);
	}
	// 큐의 앞에서 데이터 넣기 함수
	this.frontPush = function(data) {
		var result = true;
		if (this.isFull()) {
			console.log("Queue Full");
			result = false;
		} else {
			if (this.front == -1) {
				this.front = 0;
				this.rear = 0;
			} else if (this.front == 0) {
				this.front = queueSize - 1;
			} else {
				this.front--;
			}
			this.queue[this.front] = data;
		}
		return result;
	}
	// 큐의 뒤에서 데이터 넣기 함수
	this.rearPush = function(data) {
		var result = true;
		if (this.isFull()) {
			console.log("Queue Full");
			result = false;
		} else {
			if (this.front == -1) {
				this.front = 0;
				this.rear = 0;
			} else if (this.rear == queueSize - 1) {
				this.rear = 0;
			} else {
				this.rear++;
			}
			this.queue[this.rear] = data;
		}
		return result;
	}
	// 큐의 앞에서 데이터 가져오기 함수
	this.frontPop = function() {
		var result = null;
		if (this.isEmpty()) {
			console.log("Queue Empty");
		} else {
			result = this.queue[this.front];
			this.queue[this.front] = null;
			if (this.front == this.rear) {
				this.front = -1;
				this.rear = -1;
			} else if (this.front == queueSize - 1) {
				this.front = 0;
			} else {
				this.front++;
			}
		}
		return result;
	}
	// 큐의 뒤에서 데이터 가져오기 함수
	this.rearPop = function() {
		var result = null;
		if (this.isEmpty()) {
			console.log("Queue Empty");
		} else {
			result = this.queue[this.rear];
			this.queue[this.rear] = null;
			if (this.front == this.rear) {
				this.front = -1;
				this.rear = -1;
			} else if (this.rear == 0) {
				this.rear = queueSize - 1;
			} else {
				this.rear--;
			}
		}
		return result;
	}
	// 큐에 데이터가 공백 상태인지 확인하는 함수
	this.isEmpty = function() {
		return (this.front == -1);
	}
	// 큐에 데이터가 포화 상태인지 확인하는 함수
	this.isFull = function() {
		return ((this.front == 0 && this.rear == this.queueSize - 1) || this.front == this.rear + 1);
	}
	// 큐 정보 출력 함수
	this.consoleLog = function() {
		console.log(this.queue);
		console.log("front: " + this.front + ", rear: " + this.rear);
	}
}

큐의 데이터와 front, rear의 위치를 알기 위해서 console로 출력하는 consoleLog 함수를 만들었습니다.

 

​

function()으로 선언된 덱/데크(Deque)를 생성(new) 하겠습니다.

var deque = new Deque(4);

console.log(deque);
--> CircularQueue {queue: Array(4), front: 0, rear: 0, queueSize: 0, frontPush: ƒ, rearPush: ƒ, frontPop: ƒ, rearPop: ƒ, isEmpty: ƒ, isFull: ƒ, consoleLog: ƒ}
console.log(typeof deque);
--> object
console.log(deque instanceof Object);
--> true
console.log(deque instanceof Deque);
--> true
deque.consoleLog();
--> (4) [null, null, null, null]
--> front: -1, rear: -1

 

생성된 덱/데크(Deque)에 데이터를 넣고 가져오겠습니다.

deque.rearPush("Data 1");
deque.consoleLog();
--> (4) ['Data 1', null, null, null]
--> front: 0, rear: 0

deque.frontPush("Data 2");
deque.consoleLog();
--> (4) ['Data 1', null, null, 'Data 2']
--> front: 3, rear: 0

deque.rearPush("Data 3");
deque.rearPush("Data 4");
deque.consoleLog();
--> (4) ['Data 1', 'Data 3', 'Data 4', 'Data 2']
--> front: 3, rear: 2

console.log(deque.isFull());
--> true

deque.rearPush("Data 5");
--> Queue Full
deque.consoleLog();
--> (4) ['Data 1', 'Data 3', 'Data 4', 'Data 2']
--> front: 3, rear: 2

var popData = deque.frontPop();
console.log(popData);
--> Data 2
deque.consoleLog();
--> (4) ['Data 1', 'Data 3', 'Data 4', null]
--> front: 0, rear: 2

frontPush() 함수와 rearPush() 함수의 리턴 값이 false 이면 큐에 데이터를 더 이상 추가할 수 없는 포화 상태이고 frontPop() 함수와 rearPop() 함수의 리턴 값이 null이면 큐에 데이터가 없는 상태입니다.