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

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번에 넣은 뒤 정상적으로 읽었습니다.

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 큐를 참고하세요. 외부 문제의 지문과 예시는 이 글에 옮기지 않았습니다.