[알고리즘] 자료구조 - 큐

🌱 이전 포스트

스택의 특징과 배열, 연결 리스트로 구현하는 방법 등을 담았습니다.
이번 포스트에서는 스택과 반대되는 큐(Queue)라는 또 다른 대표적인 자료구조에 대해서 다루겠습니다.

---

🌱 큐 Queue

큐는 FIFO(First In First Out)의 특징을 가지는 자료구조입니다.

연산 과정
push 3 - push 5 - pop - push 7 - pop - push 8 - pop - push 2 - push 9

결과
8, 2, 9

큐는 연결 리스트를 사용해서 구현할 수 있습니다.
큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장받습니다.
연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두 개의 포인터를 가집니다.

머리(head): 남아있는 원소 중 가장 먼저 들어 온 데이터를 가리키는 포인터
꼬리(tail): 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터

삽입할 때는 꼬리(tail) 위치에 데이터를 넣고
삭제할 때는 머리(head) 위치에서 데이터를 꺼냅니다.

마지막에 들어온 데이터가 마지막에 위치해야 함으로 꼬리에 들어가야 합니다.

🌱 배열 vs 연결 리스트

큐에 다수의 데이터를 삽입 및 삭제할 때에 대해서 배열과 연결 리스트로 각각 구현할 경우 수행 시간을 측정할 수 있습니다.
큐는 배열을 이용해서 구현할 경우보다 연결 리스트를 사용할 때 수행 시간 관점에서 더 효율적입니다.
JS에서는 큐를 연결 리스트로 구현하기 위해서 객체를 사용하여 구현하면 간단하게 구현할 수 있습니다.

class Queue {
	constructor() {
		this.items = {};
		this.headIndex = 0;
		this.tailIndex = 0;
	}
  
	enqueue(item) {
		this.items[this.tailIndex] = item;
		this.tailIndex++;
	}
  
	dequeue() {
		const item = this.items[this.headIndex];
		delete this.items[this.headIndex];
		this.headIndex++;
		return item;
	}
  
	peek() {
		return this.items[this.headIndex];
	}

  	getLength() {
		return this.tailIndex - this.headIndex;
	}
};

queue = new Queue();
queue.enqueue(5);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(7);
queue.dequeue();
queue.enqueue(1);
queue.enqueue(4);
queue.dequeue();

while (queue.getLength() != 0) {
	console.log(queue.dequeue());
}

---

🌱 마무리

큐는 스택과 더불어 대표적인 자료구조 중 하나입니다.
코딩테스트에서 BFS, 최단거리 문제를 해결하거나 DFS에서도 백준의 N-Queen과 같은 문제를 풀 때
큐를 사용할 줄 알아야 합니다. 큐의 개념과 자바스크립트에서 구현하는 방법을 알아보았습니다.