[JavaScript] Queue

기존에 Queue에 대해

 

shift, pop등 자바스크립트에선 배열로 구현해서 자주 가져왔는데,

 

알고리즘을 하다보니, Queue를 활용해야하는데, 자바스크립트에서 shift는

 

배열의 순서를 전부 재정렬해야하기 때문에, 시간복잡도가 O(n)이다.

 

데이터가 적으면 상관없겠지만,

 

큐의 자료구조를 시간복잡도에 맞게 활용하고 싶은 경우엔 O(1)이 나와야한다.

처음엔 {} 에 키밸류로 넣는 구조로 구현 했지만, 링크드리스트를 활용한 예제가 괜찮아서, 내가 쓸 것들로 만들어봤다.

 

알고보니 npm에 있었다. 아놔ㅠ

 

class Node {
	constructor(data) {
		this.data = data;
		this.next = null;
	}
}

class Queue {
	constructor() {
		this.first = null;
		this.last = null;
		this.size = 0;
	}

	enqueue(data) {
		const node = new Node(data);
		if (!this.first) this.first = node;
		else this.last.next = node;
		this.last = node;
		this.size++;
	}

	dequeue() {
		if (!this.first) return false;
		const data = this.first.data;
		this.first = this.first.next;
		this.size--;
		return data;
	}

	getFirst() {
		return this.first && this.first.data;
	}

	getLast() {
		return this.last && this.last.data;
	}

	getQueue() {
		if (!this.first) return false;
		let node = this.first;
		const array = [];
		while (node) {
			array.push(node.data);
			node = node.next;
		}
		return array;
	}
}

const queue = new Queue();

enqueue할 때 this.first.next를 할당하는게 없는데 왜 this.first.next에 값이 변경되냐면,

자바스크립트에서 객체의 프로퍼티를 변경하는 것은, 주소값을 참조하기 때문에 같은 값을 가리키고 있어서,

다같이 변경이된다.

이걸 함수에서 인자로 넣는 것으로 설명하면, 콜바이레퍼런스라고 하고,

원시타입만 넘기는걸 콜바이밸류라한다.

근데 또 새로운 객체를 할당시켜버리면, 주소값이 바뀌기 때문에, 자바스크립트는 콜바이레퍼런스, 콜바이밸류 사이에 있는

 

콜바이쉐어링이라고 한다.