큐와 FIFO: head 인덱스로 JavaScript 대기열 만들기

선수 지식: JavaScript 변수·배열·조건문을 먼저 익힙니다. 객체 참조나 함수가 낯설면 아래 단계별 예제부터 시작하고, class 전체 구현은 해당 동작을 손으로 추적한 뒤 읽습니다. 각각의 코드는 독립 실행합니다.

1. A가 먼저 왔다면 A를 먼저 부릅니다

상담 창구에 A가 도착하고, 그 뒤에 B가 도착했다고 생각해 보세요. 창구가 한 사람을 부르면 A가 나갑니다. 그때 C가 새로 와도 B보다 먼저 상담받지는 않습니다. 남은 줄은 B → C입니다. 이처럼 먼저 들어온 항목을 먼저 꺼내는 줄을 큐(queue)라고 합니다.

우선 코드 없이 아래 표를 손으로 따라가 보세요. 화살표의 왼쪽이 줄의 앞이고 오른쪽이 뒤입니다. 새 사람은 오른쪽에 서고, 부를 사람은 왼쪽에서 나갑니다.

일어난 일	기다리는 줄: 앞 → 뒤	이번에 부른 사람
아무도 오지 않음	비어 있음	없음
A 도착	A	없음
B 도착	A → B	없음
한 사람 호출	B	A
C 도착	B → C	없음
다시 한 사람 호출	C	B

다음 차례가 C인 이유는 “C의 이름이나 번호가 더 작아서”가 아닙니다. 먼저 도착한 A와 B가 이미 나갔기 때문입니다. 이 규칙을 영어로 FIFO(First In, First Out), 우리말로 선입선출이라고 부릅니다. 용어보다 “뒤에 넣고 앞에서 꺼낸다”를 기억하면 됩니다.

2. 배열 여섯 줄로 같은 줄을 만들어 봅니다

이 글의 예제는 브라우저 개발자 도구의 Console 탭에서 실행합니다. 설치나 파일 저장 없이 코드 블록 전체를 붙여 넣으세요. 각 예제는 독립적으로 실행됩니다. 같은 예제를 다시 실행할 때 이름이 이미 선언되었다는 오류가 나오면 페이지를 새로고침한 뒤 실행하세요. 콘솔에 추가로 표시되는 undefined는 마지막 명령의 반환값일 수 있으며 아래 출력 예시에 포함하지 않습니다.

const line = [];
line.push("A");
line.push("B");
console.log(line.shift());
line.push("C");
console.log(line.join(", "));

출력:

A
B, C

코드	왜 이 줄이 필요한가
const line = [];	아직 사람이 없는 빈 줄을 만듭니다.
line.push(“A”);	배열 뒤에 A를 넣습니다.
line.push(“B”);	B는 A 뒤에 섭니다.
console.log(line.shift());	shift가 맨 앞 A를 꺼내고, console.log가 그 값을 보여 줍니다. 배열에는 B만 남습니다.
line.push(“C”);	남아 있는 B 뒤에 C를 붙입니다.
console.log(line.join(“, “));	남은 이름을 쉼표로 이어 B, C라고 표시합니다. join은 줄에서 사람을 꺼내지 않습니다.

push와 shift는 JavaScript 배열에 이미 있는 기능입니다. 큐를 이해하기 위해 처음부터 클래스를 만들 필요는 없습니다. 위 여섯 줄만으로도 “도착한 순서로 한 명씩 부른다”는 규칙을 구현했습니다.

3. 잠깐, 다음 호출은 누구일까요?

현재 줄은 B → C입니다. 여기서 D가 도착한 뒤 두 사람을 차례로 부릅니다. 누가 나가고, 누가 남을까요?

답과 이유 확인하기

B, C 순서로 나가고 D만 남습니다. D는 새로 왔으므로 줄의 뒤에 서기 때문입니다. “마지막에 넣은 D부터 꺼낸다”면 큐가 아니라 스택의 방식입니다.

4. 사람을 옮기지 않고, 읽을 위치만 표시할 수도 있습니다

앞의 shift 방식은 배우기 쉽고 작은 예제에 충분합니다. 다만 배열의 첫 항목을 없애면 뒤의 항목이 앞선 인덱스로 옮겨진 모습이 되어야 합니다. A, B, C에서 A를 꺼내면 B가 0번, C가 1번이 됩니다. 앞에서 꺼내는 일이 아주 많다면 이 자리 변경을 반복하지 않는 방법을 생각할 수 있습니다.

다른 방법은 배열을 그대로 두고 “다음에 읽을 위치”만 한 칸 옮기는 것입니다. 그 위치를 저장할 변수 이름을 head라고 하겠습니다. head는 사람이나 사람 수가 아니라 0, 1, 2 같은 배열 인덱스입니다.

상태	배열의 0번 / 1번 / 2번	head	실제로 기다리는 줄
A, B가 기다림	A / B / 없음	0	A → B
0번 A를 읽고 head를 1로	A / B / 없음	1	B
C를 배열 뒤에 추가	A / B / C	1	B → C
1번 B를 읽고 head를 2로	A / B / C	2	C

두 번째 줄에서 배열 안의 A가 남아 있어도 다시 부르지 않습니다. 이제 0번은 지난 자리이고 head가 가리키는 1번부터 기다리는 사람이기 때문입니다. “배열에 남아 있는 값”과 “아직 기다리는 값”을 구분하는 것이 이 방법의 핵심입니다.

const waiting = ["A", "B"];
let head = 0;
console.log(waiting[head]);
head += 1;
waiting.push("C");
console.log(waiting.slice(head).join(", "));
console.log(waiting.length - head);

출력:

A
B, C
2

코드	생각할 순서
let head = 0;	첫 사람은 배열 0번에 있으므로 0에서 시작합니다.
console.log(waiting[head]);	지금 head가 가리키는 A를 먼저 읽습니다.
head += 1;	A를 처리했으므로 다음 위치로 표시를 옮깁니다. 먼저 옮기면 A를 건너뛰게 됩니다.
waiting.push(“C”);	새 사람은 여전히 배열 뒤에 추가합니다.
waiting.slice(head).join(“, “)	head부터 끝까지를 복사해 눈으로 확인합니다. 사람을 호출하는 코드가 아니라 표시용입니다.
waiting.length – head	배열 길이 3에서 이미 읽은 자리 1개를 빼면 대기 인원은 2명입니다.

slice(head)는 남은 줄을 보여 주려고 쓴 것입니다. 매번 호출할 때 필요한 동작은 값 하나를 읽고 head를 하나 늘리는 것뿐입니다. 남은 배열을 매번 복사하는 기능까지 빠르다고 생각하면 안 됩니다.

5. head가 배열 끝에 도착했다면

배열이 [A, B, C]이고 head가 3이면 누구를 불러야 할까요? 배열 길이는 3인데 대기 인원도 3명일까요?

답과 이유 확인하기

아무도 부르지 않습니다. 0번, 1번, 2번을 모두 읽었고 다음 위치 3번에는 대기자가 없습니다. 대기 인원은 배열 길이 3 − head 3 = 0명입니다. 다음 코드에서는 이때 null을 돌려줘 “빈 큐”라고 알립니다.

아래 전체 코드에서는 큐가 완전히 비면 배열을 []로 바꾸고 head도 0으로 되돌립니다. 다음 A, B, C를 같은 방식으로 받을 수 있도록 시작 위치를 정리하는 것입니다. 일부만 처리했을 때 배열을 줄이는 고급 방법은 지금 넣지 않습니다.

6. 배운 동작을 세 함수로 묶습니다

이번 코드에서는 값으로 문자열과 숫자만 넣습니다. null은 저장하지 않고 “꺼낼 항목이 없다”는 결과로 사용합니다. 같은 이름을 두 번 넣으면 별개 항목 두 개로 처리합니다. 잘못된 종류의 입력을 검사하는 코드는 생략했으므로 이 약속을 지켜 사용하세요.

enqueue는 뒤에 넣기, dequeue는 앞에서 꺼내기, size는 대기 개수입니다. createQueue()가 이 세 함수를 묶어 돌려주므로 queue.enqueue(“A”)처럼 사용할 수 있습니다. 마지막 사용 예제까지 포함한 아래 블록 전체를 콘솔에 붙여 넣으세요.

function createQueue() {
  let items = [];
  let head = 0;

  function enqueue(value) {
    items.push(value);
  }

  function dequeue() {
    if (head === items.length) return null;
    const value = items[head];
    head += 1;
    if (head === items.length) {
      items = [];
      head = 0;
    }
    return value;
  }

  function size() {
    return items.length - head;
  }

  return { enqueue, dequeue, size };
}

const queue = createQueue();
queue.enqueue("A");
queue.enqueue("B");
console.log(queue.dequeue());
queue.enqueue("C");
console.log(queue.size());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
queue.enqueue("D");
console.log(queue.dequeue());

출력:

A
2
B
C
null
D

dequeue의 순서는 빈 상태 확인 → 현재 값 보관 → head 증가 → 모두 끝났으면 초기화 → 보관한 값 반환입니다. 값보다 head를 먼저 옮기면 첫 사람을 빠뜨리고, 값을 보관하기 전에 배열을 비우면 반환할 이름을 잃습니다. 이 순서가 단순한 코드 스타일이 아니라 동작의 이유입니다.

return { enqueue, dequeue, size }는 밖에서 사용할 함수 세 개를 묶어 주는 줄입니다. 배열 items와 head는 createQueue 안에서 기억하고, 밖에서는 세 함수를 통해서만 줄을 다룹니다. 우선 내부 문법을 모두 외우기보다 enqueue가 push를, dequeue가 읽기와 위치 이동을 담당한다는 연결을 확인하세요.

7. 마지막 예제를 손으로 다시 확인합니다

연산	대기 줄	대기 개수	출력
A, B 넣기	A → B	2	없음
dequeue()	B	1	A
C 넣고 size()	B → C	2	2
dequeue() 두 번	비어 있음	0	B, C
빈 상태에서 dequeue()	비어 있음	0	null
D를 넣고 dequeue()	비어 있음	0	D

위 전체 코드에서 마지막 줄의 출력이 D라면 무엇을 확인한 것일까요?

답과 이유 확인하기

한 번 비었던 큐도 다시 사용할 수 있다는 뜻입니다. 모두 꺼냈을 때 items와 head를 함께 초기화했고, D를 새 배열의 0번에 넣은 뒤 정상적으로 읽었습니다.

바로 실행해 보는 핵심 예제

독자 질문: 대기열에서 shift 없이 먼저 온 작업을 꺼내려면?

왜 쓰나요? head 인덱스를 앞으로 옮기고, 사용하지 않는 앞 공간은 때때로 정리합니다.

아래 바닐라 JavaScript 코드는 독립 실행 예제입니다. 본문에서 배운 개념을 새 데이터로 확인합니다. 다른 예제와 같은 콘솔에 이어 붙이지 말고 새 콘솔 또는 새 .cjs 파일에서 실행하세요.

class Queue {
  items = [];
  head = 0;
  enqueue(value) { this.items.push(value); }
  dequeue() {
    if (this.head === this.items.length) return undefined;
    const value = this.items[this.head++];
    if (this.head > 32 && this.head * 2 >= this.items.length) {
      this.items = this.items.slice(this.head);
      this.head = 0;
    }
    return value;
  }
}
const queue = new Queue();
["A", "B", "C"].forEach((x) => queue.enqueue(x));
console.log(queue.dequeue(), queue.dequeue(), queue.items.slice(queue.head).join(","));

실행 결과와 비용

이번 검토에서는 Node.js v24.18.0에서 위 독립 예제를 실행해 다음 출력과 일치하는지 확인했습니다.

A B C

시간·공간 복잡도: enqueue·dequeue는 정리 비용을 여러 호출에 나누면 분할 상환 O(1)입니다. 드문 slice 한 번은 O(n), 저장 공간은 O(n)입니다.

직접 풀 문제

C 다음 D를 enqueue한 후 두 번 dequeue하면 순서가 어떻게 되나요?

풀이와 기대 결과

C, D입니다. 이미 소비한 A·B는 다시 나오지 않습니다.

원자료의 다른 학습 순서 (선택)

자료구조 과정 원래 순서의 다음 글: 06 head·tail을 유지하는 단방향 연결 리스트

검증 범위: 위 독립 예제의 출력만 로컬에서 확인했습니다. 이 글은 독립 자료구조 실습입니다. 실제 브라우저 표시와 모든 입력·플랫폼의 실행은 검증하지 않았습니다.

8. 상담 창구 문제로 이어갑니다

이제 상담 창구 대기열에서 ARRIVE를 enqueue에, CALL을 dequeue에, COUNT를 size에 연결해 보세요. 처음에는 입력 파일 처리보다 “한 명 도착 → 한 명 호출 → 현재 인원”을 직접 함수로 실행하면 충분합니다.

최근에 넣은 항목부터 꺼내는 스택의 push·pop과도 비교해 보세요. 같은 A, B, C를 넣어도 큐는 A부터, 스택은 C부터 꺼냅니다.

연결된 문제의 전체 정답은 값의 종류를 더 넓게 다루기 위해 빈 결과를 {done:true}로 표시하고 배열 정리 기능도 포함합니다. 이 글은 이해를 위해 null을 사용하는 간단한 버전입니다. 두 버전의 반환 형식을 섞지 말고, 먼저 FIFO 규칙이 같은지 비교하세요.

더 알아보기: 많은 작업을 오래 처리한다면

shift는 뒤의 항목을 당기는 비용을 고려해야 하고, head 방식은 그 이동을 피합니다. 대신 이 간단한 구현은 큐가 완전히 빌 때까지 지난 자리도 배열에 남깁니다. 한 번도 비지 않는 긴 대기열에는 주기적인 배열 정리나 원형 큐가 필요합니다. 큐의 기본 규칙을 익힌 다음 살펴볼 내용입니다.

참고 자료

배열의 앞 제거 동작은 ECMAScript의 Array.prototype.shift에 정의되어 있습니다. 추가 연습은 백준 10845 큐를 참고하세요. 외부 문제의 지문과 예시는 이 글에 옮기지 않았습니다.

연결 큐에서도 FIFO와 반환값 계약을 먼저 맞춥니다

큐의 FIFO 규칙은 배열의 head 인덱스로도, 연결 노드로도 구현할 수 있습니다. 단방향 연결 큐에서 head는 먼저 꺼낼 노드, tail은 새 값을 붙일 마지막 노드를 가리키게 하면 뒤 삽입과 앞 삭제가 모두 O(1)입니다. A 뒤에 B를 붙인 뒤 앞에서 꺼내면 A가 반환되고 head는 B로 옮겨집니다. 마지막 B까지 꺼낸 순간에는 head와 tail을 함께 null로 바꿔야 하며, 다시 C를 넣으면 두 참조가 같은 새 노드를 가리켜야 합니다.

앞에 넣고 뒤에서 꺼내는 배치도 이중 연결 리스트라면 양끝 연산으로 FIFO를 만들 수 있습니다. 같은 배치를 단방향 리스트로 옮기면 뒤 삭제의 직전 노드 탐색 때문에 O(N)이 될 수 있습니다. 연결 큐를 별도로 만든다면 dequeue가 노드인지 저장한 값인지, 빈 큐가 undefined인지 별도 상태인지부터 명시하세요. head 인덱스 배열은 사용한 앞부분의 참조 정리·압축 정책이 필요하고, 연결 큐는 항목마다 노드와 링크를 저장합니다. 논리적 순서가 같아도 메모리 배치와 개별 구현의 비용은 따로 비교해야 합니다.

이어서 공부할 개념

• DFS와 BFS 비교: 깊이·대기열·최소 간선 수를 구분하기

첨부 test_queue.mjs에서 연결 방향과 FIFO 반환 순서를 비교합니다

dev.zip의 dev/test_queue.mjs는 이름에 test가 있지만 assert로 통과·실패를 판정하는 자동 테스트가 아닙니다. console.log와 출력용 메서드로 결과를 관찰하는 시연 파일입니다. 아래에서 호출 뒤 남은 상태와 함수가 반환하는 값을 따로 읽어 보세요. 원본은 상대 모듈을 가져오므로 코드 한 조각만 콘솔에 붙이면 독립 실행되지 않습니다.

원본 Queue는 이중 연결 리스트에 앞에서 넣고 뒤에서 꺼냅니다. 따라서 enqueue(1), enqueue(2), enqueue(3) 뒤의 head부터 읽은 순서는 [3,2,1]이지만, 대기열에서 꺼낼 순서는 1,2,3입니다. front()는 head가 아니라 list.tail을 돌려줍니다. “front”라는 이름은 다음에 처리할 항목이라는 뜻입니다.

test_queue.mjs의 상태와 실제 반환 계약

원본 호출	head → tail / count	반환 또는 출력에서 볼 값
enqueue(1), enqueue(2), enqueue(3)	[3,2,1] / 3	enqueue는 undefined이며 로그로 출력하지 않습니다.
console.log(queue.front())	[3,2,1] / 3 유지	data=1인 Node 객체입니다. 숫자 1 자체를 반환하지 않습니다.
첫 console.log(queue.dequeue())	[3,2] / 2	data=1인 Node입니다. 직전 front와 같은 객체입니다.
둘째 dequeue()	[3] / 1	data=2인 Node입니다.
셋째 dequeue()	[] / 0	data=3인 Node입니다. 마지막 삭제 뒤 head와 tail이 모두 null입니다.
넷째 dequeue(), isEmpty()	[] / 0 유지	null, 이어서 isEmpty: true를 출력합니다.

원본은 Node 전체를 console.log 하므로 실제 콘솔에는 data 외에 next·prev도 보일 수 있습니다. 이중 연결 객체에는 서로를 가리키는 참조가 있어 도구가 순환 참조 표시를 붙일 수도 있습니다. FIFO를 확인할 때에는 세 반환 Node의 data가 [1,2,3]인지, front 전후 count가 같은지, 네 번째 반환이 null인지 따로 봅니다. 제거된 Node의 링크가 모두 null이라고 가정하지 않습니다.

현재 글 안의 큐 예제와 첨부 Queue를 구분합니다

구현	정상 dequeue 반환	빈 dequeue 반환
본문의 기초 createQueue()	저장한 값	null
본문 “바로 실행해 보는 핵심 예제”의 class Queue	저장한 값	undefined
첨부 dev/Queue.mjs	저장한 값을 data에 가진 Node	null

위 세 구현에 같은 dequeue().data 표현을 사용하면 안 됩니다. 원본 Node를 값으로 바꿔 읽으려면 먼저 null 여부를 확인한 다음 data를 꺼냅니다. 원본의 빈 front()도 tail이 null이므로 null입니다. 원본 dequeue의 catch는 내부 삭제에서 발생한 예외를 null로 바꾸므로, null 출력만으로 “내부 오류 없이 빈 경우만 처리했다”까지 증명되지는 않습니다.

앞 삽입과 뒤 삭제가 모두 O(1)인 이유는 원본이 tail과 prev를 가진 이중 연결 리스트를 쓰기 때문입니다. 단방향 리스트에 같은 방향을 적용하면 뒤 삭제 전에 직전 노드를 찾아야 합니다. 자동 검증으로 옮길 때에는 assert로 1·2·3 순서와 마지막 양끝 null을 확인하고, 비운 뒤 4를 넣어 head와 tail이 같은 새 Node인지도 추가로 확인하세요. 원본 시연에는 이 재삽입 호출이 없습니다.

자기 확인: head.data가 3인데 front().data가 1이어도 FIFO인가요?

그렇습니다. 이 구현은 앞에 새 항목을 붙이고 tail의 가장 오래된 항목부터 꺼냅니다. front 조회 뒤 count는 3이며 첫 dequeue 뒤에는 2입니다.