프론트엔드 개발자라면 누구나 한 번쯤 자바스크립트의 태스크 큐에 대해 들어보았을 텐데요. 태스크 큐는 자바스크립트의 비동기 처리를 관리하는 중요한 역할을 합니다. 여기까지는 많이 알려진 사실이지만, '태스크 큐'라는 이름의 유래나, 왜 큐라는 자료구조가 사용되었는지에 대해 깊이 생각해 본 적은 없었습니다. 이번에 자료구조 큐를 공부하면서 태스크 큐가 왜 큐를 사용하게 되었는지 이해하게 되었고, 이에 대해 내용을 공유하고자 합니다.
큐
큐는 스택과 마찬가지로 선형 자료구조이며, FIFO (First-In-First-Out) 방식으로 작동합니다. 즉, 먼저 들어간 요소가 가장 먼저 나오는 구조를 가지고 있습니다. 이 원리만 이해하면 큐는 비교적 단순한 자료구조처럼 보입니다.
이전 글에서 다룬 스택은 배열(Array)이나 연결 리스트(LinkedList)로 구현할 수 있었습니다. 큐 역시 비슷하게 배열이나 연결 리스트를 사용하여 구현할 수 있습니다. 다만, 큐는 요소가 들어오고 나가는 방향이 다르다는 점에서 스택과 차이를 보입니다.
Array로 큐를 구현할수 있을까?
처음에는 JavaScript의 Array를 이용해서 큐를 구현해 보았는데요. 다음은 제가 작성한 코드 입니다.
class ArrayQueue {
constructor(maxSize) {
this.queue = Array(maxSize).fill(Infinity);
this.front = 0;
this.rear = -1;
}
isFull() {
return this.rear === this.queue.length - 1;
}
isEmpty() {
return this.front > this.rear;
}
enqueue(item) {
if (this.isFull()) {
throw Error("Queue is Full");
}
this.rear += 1;
this.queue[this.rear] = item;
}
dequeue() {
if (this.isEmpty()) {
throw Error("Queue is Empty");
}
for (let i = 0; i < this.rear; i++) {
this.queue[i] = this.queue[i + 1];
}
--this.rear;
}
}Array를 사용하여 큐를 구현한 방식에서, dequeue메서드를 실행할때마다 모든 요소를 앞으로 이동시켜야 한다는 문제가 발생했습니다. 물론 front를 단순히 +=1로 증가시키는 방식으로 수정할 수도 있지만, 또 다른 문제가 생깁니다. 배열의 길이가 제한되어 있기 때문에, 일정 크기를 넘어서는 요소를 enqueue할 수 없게 됩니다.
결국 Dequeue시 모든 요소를 이동시키는건 O(n)의 시간 복잡도가 발생하며, 이는 효율적이지 않은 방법이라 판단했습니다!
LinkedList로 구현한 선형 큐
오늘도 혼자 구현을 하다 결국 gpt의 도움으로 LinkedList를 이용한 선형 큐를 만들 수 있었습니다. T.T
class Node {
constructor(newNode) {
this.value = newNode;
this.next = null;
}
}
class LinkedListQueue {
constructor() {
this.first = null;
this.rear = null;
}
isEmpty() {
return !this.first && !this.rear;
}
enQueue(item) {
const newNode = new Node(item);
if (!this.rear) {
this.current = newNode;
this.rear = newNode;
return;
}
this.rear.next = newNode;
this.rear = newNode;
}
deQueue() {
if (this.isEmpty()) {
throw Error("Queue is Empty");
}
const value = this.first;
this.first = this.first.next;
if (!this.front) {
this.rear = null;
}
}
이 코드에서 LinkedListQueue는 연결 리스트를 사용하여 큐를 구현합니다. 동작 원리는 다음과 같습니다.
- 큐의 첫번째(front)와 마지막(rear) 노드를 가리키는 포인터로 시작과 끝을 추적합니다.
- enQueue연산시, 큐가 비어있지 않다면 rear.next를 새 노드로 설정하고, rear 포인터를 새 노드로 생신합니다.
- deQueue연산시, 큐의 첫번째 요소를 제거하고 front를 다음 노드로 이동시킵니다.
연결리스트 큐의 장점과 단점
연결 리스트로 구현된 큐는 enQueue와 deQueue 연산을 O(1) 시간 복잡도로 수행할 수 있습니다. 따라서 배열 기반 큐에서 발생하는, deQueue시 모든 요소를 앞으로 이동시키는 추가 연산이 필요하지 않다는 장점이 있습니다.
하지만 연결리스트로 구현된 큐는 각 노드가 다음 노드에 대한 포인터를 가지고 있어야 하므로 추가적인 메모리 공간이 필요합니다. 또한, 특정 요소를 찾을때는 순차 접근만 가능하여 시간복잡도가 O(n)이 됩니다. 이 점은 큐에서의 일반적인 요소 접근에는 영향을 주지 않지만, 특정 요소 검색이 필요한 경우에는 성능에 제약이 될 수 있을거라 판단이 됩니다.
태스크큐는 어떤 큐일까?
지금까지 제가 이야기한 큐는 큐의 4가지 종류중 가장 기본적인 "선형 큐"에 해당합니다. 서두에 이야기 했던 태스크 큐는 비동기 작업을 순서대로 실행하도록 보장하는 큐입니다. 태스크 큐는 작업에 대한 우선순위나 특정한 순환 방식 없이 단순하게 작업을 순차적으로 실행합니다. 따라서 기본적인 선형 큐를 사용하는 것이 적합합니다.
프론트엔드 개발에서 큐 사용 사례
프론트엔드 개발을 하면서 큐를 직접 구현해본 경험이 두가지가 있습니다. 여기서는 네트워크 통신 관리와 JWT토큰 만료 처리라는 두 가지 상황에서 큐를 어떻게 활용했는지 공유해보려합니다.
- 네트워크 통신 관리
특정 네트워크 통신 장치와 클라이언트 간에 지속적으로 통신을 유지해야 하는 경우, 웹소켄을 통해 요청을 전송하는 경우가 있는데요. 하지만 때때로, 네트워크의 불안정으로 인해 장치로부터 응답이 없거나 요청이 실패할 수 있습니다. 이때 각 요청을 임시 큐인 waitingQueue에 저장해 두고, 모든 요청이 정상적으로 완료되지 않은 경우 재요청을 보내는 방식으로 문제를 해결할 수 있습니다. 이때 큐는 실패한 요청을 차례로 다시 시도하도록 해줍니다.
- JWT토큰 만료 처리
JWT기반 인증 서비스에서 토큰이 만료되면 서버 요청이 거부되거나 실패하게 됩니다. 이떄 ProcessQueue라는 간단한 큐를 만들어 실패한 요청을 담아 두고, 토큰을 갱신 시킨후 순차적으로 재실행되도록 하여 사용자들의 UX를 향상시킬수 있습니다.
이때 큐의 역할은 토큰이 유효하지 않아도 요청이 손실되지 않도록 해주며, 토큰 갱신 후에도 실행 순서를 유지할 수 있습니다.
왜 배열로 구현했을까?
사실 위 두가지 사례에서 배열을 사용해 큐를 구현했는데, 이는 연결 리스트의 복잡성이 불필요 했기 때문인데요. 단순히 요청을 순서대로 담아두고 필요한 시점에 순차적으로 실행하면 되는 상황이었기에 배열을 선택했습니다. 배열 큐는 접근성과 메모리 측면에서 간단하게 문제를 해결할 수 있기에 선택하게 되었습니다.
프론트엔드 개발에서 큐는 비동기 작업의 흐름을 관리하고, 사용자 경험을 원활하게 하기위한 유용한 도구인것같습니다. 실제로 프론트엔드에서 배열을 이용한 큐 구조는 간단하면서도 비동기 작업으리 순서를 보장하는 데 충분한 역할을 할 수 있습니다. 앞으로 더 복잡한 비동기 작업이나 데이터 흐름을 처리해야 하는 상황이 온다면, LinkedList 기반의 큐를 이용할 수 있다면 활용해 보는것도 좋은 시도가 될것같다고 생각했습니다!
다음 포스팅은 이어서 큐의 또 다른 종류인 우선순위 큐, 원형큐, 덱 에대해서 공유하는 글을 이어서 작성해보겠습니다.
감사합니다.
