JavaScript Deque(Double-Ended Queue) - 배열 객체의 메서드로 덱/데크 만들기, Deque(Array - push,pop,shift,unshift), Data Structures

JavaScript에서 Array 객체의 push() 메서드, pop() 메서드, shift() 메서드, unshift() 메서드를 사용하여 덱/데크(Deque - Double-Ended Queue)처럼 사용할 수 있습니다.

​

​

덱/데크(Deque - Double-Ended Queue)

​

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

덱의 모양은 큐의 모양과 동일합니다. 빨대나 호스를 생각하시면 됩니다.

 

Array 객체의 push() 메서드, pop() 메서드, shift() 메서드, unshift() 메서드를 사용하여 ​덱/데크(Deque)에 데이터 넣고 가져오기

var deque = [];

console.log(deque);
--> []
console.log(deque.length);
--> 0

// 뒤에 데이터 넣기
deque.push("Data 1");
deque.push("Data 2");

console.log(deque);
--> (2) ['Data 1', 'Data 2']
console.log(deque.length);
--> 2

// 앞에 데이터 넣기
deque.unshift("Data 3");

console.log(deque);
--> (3) ['Data 3', 'Data 1', 'Data 2']
console.log(deque.length);
--> 3

// 뒤에서 데이터 가져오기
var popData = deque.pop();

console.log(popData);
--> Data 2
console.log(deque);
--> (2) ['Data 3', 'Data 1']
console.log(deque.length);
--> 2

// 앞에서 데이터 가져오기
var shiftData = deque.shift();

console.log(shiftData);
--> Data 3
console.log(deque);
--> ['Data 1']
console.log(deque.length);
--> 1

 

 

 

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

​

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

​

JavaScript의 Array 객체로 만들기 때문에 크기에 제한 없이 사용할 수 있습니다. 그래서 데이터를 계속 넣어도 오버플로(Overflow)가 발생하지 않습니다. 다음에 크기를 제한해서 만들어 보겠습니다.

​

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

push() 메서드와 pop() 메서드로는 앞과 뒤를 구별할 수 없습니다. 그래서 Java의 Deque 클래스의 메서드 명을 사용하여 함수를 만들겠습니다.

앞은 First, 뒤는 Last, 넣을 때는 add, 가져올 때는 remove를 사용합니다.

var Deque = function() {
	// Array 객체 생성
	this.deque = [];
	// Push 함수 - 뒤에 데이터 넣기
	this.addLast = function(data) {
		this.deque.push(data);
	}
	// Push 함수 - 앞에 데이터 넣기
	this.addFirst = function(data) {
		this.deque.unshift(data);
	}
	// Pop 함수 - 뒤에서 데이터 가져오기
	this.removeLast = function() {
		return this.deque.pop();
	}
	// Pop 함수 - 앞에서 데이터 가져오기
	this.removeFirst = function() {
		return this.deque.shift();
	}
	// Length 함수 - 덱/데크 크기 가져오기
	this.length = function() {
		return this.deque.length;
	}
	// GetData 함수 - 지정된 인덱스에 있는 데이터 가져오기
	this.getData = function(index) {
		return this.deque[index];
	}
}

 

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

var deque = new Deque();

console.log(deque);
--> Deque {deque: Array(0), addLast: ƒ, addFirst: ƒ, removeLast: ƒ, removeFirst: ƒ, length: ƒ, getData: ƒ}
console.log(typeof deque);
--> object
console.log(deque instanceof Object);
--> true
console.log(deque instanceof Deque);
--> true

생성된 덱/데크(Deque)는 function()으로 생성되었기 때문에 console.log()로 출력하면 Array처럼 배열이 나오지 않고 함수가 나옵니다.

​

deque 객체의 프로토타입 체인(Prototype Chain)은 다음과 같습니다.

deque > Deque > Object

 

 

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

// 뒤에 데이터 넣기
deque.addLast("Data 1");
deque.addLast("Data 2");

console.log(deque.length());
--> 2

// 앞에 데이터 넣기
deque.addFirst("Data 3");

console.log(deque.length());
--> 3

// 뒤에서 데이터 가져오기
var lastData = deque.removeLast();

console.log(lastData);
--> Data 2
console.log(deque.length());
--> 2

// 앞에서 데이터 가져오기
var firstData = deque.removeFirst();

console.log(firstData);
--> Data 3
console.log(deque.length());
--> 1

 

 

getData 함수로 데이터를 가져오게 하겠습니다.

var deque = new Deque();

// 데이터 넣기
deque.addLast("Data 1");
deque.addLast("Data 2");
deque.addFirst("Data 3");

console.log(deque.length());
--> 3

// 덱/데크 데이터 가져오기
for (var index = 0; index < deque.length(); index++) {
	var dequeData = deque.getData(index);
	console.log(dequeData);
}

--> Data 3
--> Data 2
--> Data 1

 

참고로

Scroll(입력 제한 덱/데크) - 입력이 한쪽만 가능하도록 설정한 덱/데크

Shelf(출력 제한 덱/데크) - 출력이 한쪽만 가능하도록 설정한 덱/데크

​

Deque 선언에 다양한 함수를 추가하여 사용해 보시기 바랍니다.