코딩테스트 스터디를 만들고 나서 JS로 자료구조와 알고리즘을 공부하는 요즘, Queue에 대해 문득 드는 의문점을 해결하지 않은 채 둔 게 있습니다.

<aside> ❓ 배열에 shift라는 메서드가 있던데, 그거 쓰면 같은 거 아닌가? 왜 굳이 queue를 구현해서 써야한다고 얘기하는거지?

</aside>

라는 내용인데요.

이참에 의문점을 파고들어 해소하고 지나치자는 생각에 오늘도 한 편의 글을 남기게 되었습니다.

시작하기 앞서

스택오버플로우에서 2018년도에 올라온 질문이 있습니다 Array.shift와 링크드리스트 방식의 퍼포먼스 차이에 대한 질문인데요. 한번 보고 오면 좋을 것 같습니다

What is the performance difference between Array.shift and a Linked List's equivalent in JavaScript

요약하자면,

5만개 기준으로, 5만개보다 적은 경우엔 30-40%정도 느리다고 하며 5만개의 요소를 넘어가는 순간부터는 100%만큼 느리다고 답변이 달려있습니다.

큐를 구현하는 방식

기본적으로 2가지 방식이 있다고 알려져 있습니다.

1. Class Queue - 링크드 리스트

소스코드 기본 형태는 다음과 같습니다*(완벽한 형태가 아닙니다)*.

class Queue {
	constructor() {
		this.storage = {};
		this.headIndex = 0;
		this.tailIndex = 0;
	}
	
	enqueue(item) {
		this.storage[this.tailIndex] = item;
		this.tailIndex++;
	}
	
	dequeue() {
		const item = this.storage[this.headIndex];
		delete this.storage[this.headIndex];
		this.headIndex++;
		return item;
	}
	
	getLength() {
		return this.tailIndex - this.headIndex;
	}
	
	getItem() {
		return this.storage[this.headIndex];
	}
}

2. Array.shift() + Array.push()

사실, 배열 방식에서 원소를 넣어주는 push메서드에서 시간 차이가 발생하진 않습니다. 그러나, **shift()**의 경우엔 다음과 같은 내부로직이 존재합니다