[알고리즘] 큐 (Queue), 덱(Dequeue)

📌 Queue

큐는 스택과 반대로 FIFO(First In First Out) 자료구조로, 가장 먼저 들어갔던 값이 가장 먼저 나온다.
스택처럼 가장 끝부분에서만 삽입과 삭제 연산이 이뤄지며 중간의 값은 알 필요가 없으나, 스택은 삽입과 삭제가 같은 쪽에서 이뤄지고 큐는 서로 다른 쪽에서 이뤄진다는 점에서 다르다.

 

큐는 입구인 rear와 출구인 front가 존재한다. pop을 할 때는 제일 앞에 있는 front에 있는 원소를 빼내게 된다. 참조할 수 있는 것도 일반적으로 front에 있는 원소이다.

 

운영체제에서 각종 이벤트(마우스 클릭)를 발생한 순서대로 처리하기 위해 대기시키는 이벤트 큐가 대표적인 예시이다.

큐는 스택과 마찬가지로 연결 리스트를 사용하여 구현한다. 삽입/삭제 연산이 O(1)이다.

 

 

큐 & 스택 in JS

자바스크립트는 싱글 스레드 기반의 언어이고, JS 엔진은 하나의 호출 스택(Call Stack)만을 사용한다. 고로, 요청이 동기적으로 처리되어, 한 번에 한 가지 일만 처리할 수 있다. JS 엔진은 스택과 큐 기반으로 작동한다. 마이크로 테스크 큐와 매크로 테스크 큐가 이벤트 루프에 의해 콜스택에 넘겨줌으로써 입력 처리한다.

 

• 이벤트 루프 : 콜 스택이 비었다면 태스크 큐에 있는 콜백 함수 처리
• 태스크 큐 : 태스크의 Set. 이벤트 루프는 하나 이상의 태스크 큐를 갖는다. 이벤트 루프에서 가장 오래된 태스크를 가져온다. (선입선출)

 

 

 

🔍 예시 코드

class ArrayQueue {
	constructor(size = 1000) {
		this.list = new Float32Array(size);
		this._front = 0;
		this._rear = -1;
		this.count = 0;
	}

	/** 큐에 데이터 삽입 */
	enqueue(data) {
		if (typeof data !== 'number') {
			throw new Error('숫자를 입력해주세요');
		}

		if (this.count === this.size) {
			throw new Error('큐가 가득 찼습니다 (Queue Overflow)');
		}

		this.list[++this._rear] = data;
		this.count++;
	}

	/** 큐에서 데이터 제거 */
	dequeue() {
		if (this.count === 0) {
			// console.error('큐가 비어있습니다 (Queue Underflow)');
			return null;
		}

		this.count--;
		return this.list[this._front++];
	}

	/** 큐의 프론트 데이터 출력 */
	front() {
		return this.list[this._front];
	}

	/** 큐의 레어 데이터 출력 */
	rear() {
		return this.list[this._rear];
	}

	/** 큐가 비어있는지 확인 */
	isEmpty() {
		return this.count === 0;
	}
}

export { ArrayQueue };

 

Remember) 자바스크립트 배열에서 FIFO를 구현하려면 그냥 shift, unshift를 써도 되지 않을까?하는 의문이 있을 것이다. 하지만 이와 같은 방식은 바람직하지 못하다. 자바스크립트에서 shift의 시간복잡도는 O(N)이기 때문이다.

다음은 shift에 대한 MDN 설명이다.

shift 메서드는 0번째 위치의 요소를 제거 하고 연이은 나머지 값들의 위치를 한칸 씩 앞으로 당깁니다. 그리고 제거된 값을 반환 합니다. 만약 배열의 length가 0이라면 undefined를 리턴 합니다.

 

즉, 한칸씩 당기는 로직을 구현하려면 결과적으로 모든 배열의 요소들을 탐색해야 하기에 시간복잡도는 O(N)이 된다.

그래서 객체 구조인 단일 연결 리스트를 사용하여 시간복잡도를 O(1)로 만들어줄 수 있다. (물론 연산 마지막에 객체를 배열로 변환시킬 때는 O(N)이다.)

 

👍 장점

• 데이터 접근, 삽입, 제거가 빠르다.

👎 단점

• 중간에 위치한 데이터에 대한 접근이 불가능하다.

 

 

---

📌 Dequeue

덱은 Doubled-Ended-Queue의 약자로, 덱은 앞, 뒤 양쪽에서 삽입 삭제가 모두 가능하다. (FIFO + FILO) 두 개의 포인터를 사용하여 양쪽에서 삽입 삭제를 발생시킬 수 있고, 큐와 스택을 합친 형태로 생각할 수 있다. 마찬가지로 삽입 삭제에 대한 시간복잡도는 O(1)이다.

 

 

🔍 예시코드

class Deque {
	constructor() {
		this.list = new DoubleLinkedList();
	}

	/** 모든 데이터 출력 */
	printAll() {
		this.list.printAll();
	}

	/** 헤드에 데이터 삽입 */
	addFirst(data) {
		this.list.insertAt(0, data);
	}

	/** head에 데이터 제거 */
	removeFirst() {
		this.list.deleteAt(0);
	}

	/** tail에 데이터 삽입 */
	addLast(data) {
		this.list.insertLast(data);
	}

	/** tail에 데이터 제거 */
	removeLast() {
		this.list.deleteLast();
	}

	/** 리스트가 비었는지 체크 */
	isEmpty() {
		return this.list.count === 0;
	}
}

export { Deque };

 

👍 장점

• FIFO 형식이든 FILO 형식이든 둘 다 사용할 수 있다는 점에서 유연하다.
• 양쪽에서 빠르게 요소를 추가/제거 가능하다.

👎 단점

• 중간 데이터에 접근하게 된다면 느린 편이다.
• 메모리 사용량이 크다. (이중연결리스트이기 때문)