큐
자바스크립트 배열에서 shift로 값 1,000개 중 첫 값을 꺼내면 나머지 999개가 옮겨지지만, 고리 버퍼는 같은 일을 한 단계에 합니다.
먼저 들어온 것이 먼저
큐는 가게 계산대 앞의 줄과 같습니다. 사람들은 뒤에 서고 앞에서부터 계산을 마치므로, 먼저 온 사람이 먼저 나갑니다. 이 규칙을 선입선출(FIFO, first in first out)이라고 합니다. 연산은 두 가지입니다. enqueue는 맨 뒤에 값을 넣고, dequeue는 맨 앞 값을 꺼냅니다. MIT 6.006 강의 노트에서 큐는 순서열 인터페이스 가운데 insert last(x)와 delete first()만 쓰는 것입니다.
도착한 순서대로 처리해야 하는 일이 있는 곳에는 어디에나 큐가 있습니다. 프린터를 기다리는 문서, 프로그램을 기다리는 키 입력, 서버를 기다리는 메시지가 그렇습니다. 알고리즘 과정의 너비 우선 탐색은 아직 방문할 칸을 큐에 넣어 두는데, 그래서 거리가 같은 칸들을 한 겹씩 넓혀 가며 살핍니다.
쉬운 방법과 숨은 비용
자바스크립트에서 가장 쉬운 큐는 배열입니다. 뒤에 넣을 때 push, 앞에서 꺼낼 때 shift를 씁니다. 잘 동작하고 짧은 큐라면 문제도 없습니다. 하지만 shift가 하는 일을 보세요. MDN은 shift가 「모든 값을 왼쪽으로 1칸씩 옮긴다」고 설명하고, ECMAScript 명세는 이를 모든 k에 대해 k번째 값을 k − 1번 자리로 옮기는 반복문으로 적습니다. 첫 단원에서 본 것처럼 배열의 앞쪽은 비싼 쪽입니다. 값이 n개인 큐에서 꺼내려면 읽기 1번과 옮기기 n − 1번이 들므로, 값 1,000개짜리 큐는 꺼낼 때마다 1,000단계입니다. (엔진이 내부에서 지름길을 쓸 수도 있지만 명세가 약속하지는 않습니다.)
빈 배열에 값 5개를 넣고 다시 5개를 모두 꺼내면, 넣기에 5단계, 꺼내기에 5 + 4 + 3 + 2 + 1 = 15단계, 모두 20단계가 듭니다. 대부분은 꺼내지도 않는 값을 옮기는 데 쓰입니다.
값 대신 앞자리 표시를 옮기기
해결책은 값을 옮기지 않고 앞자리가 어디인지를 기억하는 것입니다. head라는 번호를 둡니다. 꺼낼 때는 head 자리의 값을 읽고 head에 1을 더할 뿐, 다른 값은 움직이지 않습니다. 다만 head 앞의 칸은 버려집니다. 고리 버퍼(원형 버퍼)는 그 칸을 다시 씁니다. 배열의 칸 수를 예를 들어 8개로 정해 두고, 위치가 돌아가게 해서 7 다음 칸을 0으로 합니다. head와 size를 기억합니다. 다음에 넣을 값은 (head + size) mod 8번 칸에 들어가고, 꺼낼 때는 head 칸의 값을 가져가고 head를 (head + 1) mod 8로 옮깁니다. 두 연산 모두 1단계입니다. 대신 칸 수가 정해져 있어서 size가 8이 되면 큐가 가득 찹니다. 동적 배열처럼 더 큰 고리로 모두 옮겨 적으면 늘릴 수 있습니다.
끌어서 돌리고, 휠이나 두 손가락으로 확대하세요.
| 값 n개인 큐 | 넣기 | 꺼내기 |
|---|---|---|
| 배열과 push, shift | 1(분할 상환) | 읽기 1 + 옮기기 (n − 1) |
| head 번호를 둔 배열 | 1(분할 상환) | 1, 앞쪽 칸은 버려짐 |
| 크기가 정해진 고리 버퍼 | 1, 또는 가득 참 | 1 |
어느 쪽을 써야 할까요? 값이 많아야 수십 개인 큐라면 push와 shift가 짧고 알아보기 쉬우며, 옮기는 비용도 거의 없습니다. 큰 너비 우선 탐색의 칸들처럼 항목 수천 개가 지나가는 큐라면 head 번호나 고리 버퍼가 꺼내기를 늘 한 단계로 지켜 주고, 줄이 길수록 차이가 커집니다.
| 선입선출(FIFO) | 먼저 들어온 값이 먼저 나감. |
| enqueue / dequeue | 뒤에 넣기 / 앞에서 꺼내기. |
| shift | 배열 첫 값을 빼고 나머지를 모두 한 칸씩 왼쪽으로 옮김. |
| 고리 버퍼 | 원처럼 쓰는 고정 배열. 다음 빈칸은 (head + size) mod 용량. |
- 큐는 값을 어떤 순서로 돌려줄까요?
- 먼저 넣은 것부터
- 나중에 넣은 것부터
- 큰 것부터
- 아무 순서로나
- A, B, C를 넣고 한 번 꺼낸 뒤 D를 넣습니다. 이제 빌 때까지 꺼냅니다. 꺼낸 값을 순서대로 놓으세요.
- push와 shift를 쓸 때 값 4개짜리 큐에서 한 번 꺼내는 데 몇 단계일까요(읽기 1번과 옮기기)?
- 같은 방식으로 값 1,000개짜리 큐에서 한 번 꺼내면 몇 단계일까요?
- 빈 배열에 push로 값 5개를 넣고 shift로 5개를 모두 꺼냅니다. 모두 몇 단계일까요?
- 칸이 8개(0~7)인 고리 버퍼에서 head = 6, size = 3입니다. 다음 넣기는 몇 번 칸을 쓸까요?
- 고리 버퍼에서 꺼내기는 값이 몇 개 있든 몇 단계일까요?
- 칸 8개짜리 고정 고리에 값이 8개 있습니다. 넣으면 어떻게 될까요?
- 맨 앞 값을 덮어쓴다
- 큐가 가득 차서 값을 받지 않는다
- 모든 값을 왼쪽으로 옮긴다
- 값을 정렬한다
- 알고리즘 과정의 탐색 가운데 기다리는 칸을 큐에 넣는 것은?
- 이진 탐색
- 너비 우선 탐색
- 깊이 우선 탐색
- 선형 탐색
- MIT 6.006 용어로 큐는 순서열 연산 가운데 어느 두 가지를 쓸까요?
- insert last와 delete last
- insert last와 delete first
- insert first와 delete first
- get at과 set at
- 큐는 선입선출입니다. 뒤에 넣고 앞에서 꺼냅니다.
- shift는 남은 값을 모두 옮기므로 값 n개에서 꺼내면 n단계입니다.
- head 번호나 고리 버퍼를 쓰면 꺼내기가 1단계입니다.
- 크기 c인 고리에서 다음 빈칸은 (head + size) mod c입니다.
이 과정의 출처 (5)
- MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon), lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append), 4 Hashing (chaining, pigeonhole collisions, chain length n/m), 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
- MDN Web Docs, Array.prototype.shift (shifts all values left by 1), Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
- ECMAScript 2025 Language Specification (tc39.es/ecma262), 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements"), Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
- D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
- "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).
확인한 날: 2026-10-18