Stack·Queue — 같은 세 개를 넣었는데 왜 다른 게 나올까?
A, B, C를 차례대로 넣고 하나만 꺼낸다고 해 보겠습니다. C가 나오면 스택(Stack), A가 나오면 큐(Queue)예요. 넣은 순서가 같으니 차이는 꺼낼 때 생깁니다. 어느 쪽 끝에서 꺼내느냐가 처음부터 정해져 있거든요.
1. 이름보다 먼저, 꺼내는 순서부터
스택은 쌓아 둔 접시, 큐는 가게 앞에 선 줄이에요. 접시는 맨 위의 C를 치워야 B에 손이 닿고, 줄은 먼저 선 A부터 들어갑니다. 나중에 들어온 게 먼저 나가는 규칙을 , 먼저 들어온 게 먼저 나가는 규칙을 라고 불러요. 넣은 순서는 같고, 꺼내는 끝만 다릅니다. 둘 다 A·B·C가 들어 있어요. 버튼을 누를 때마다 양쪽에서 하나씩 꺼냅니다.A → B → C, 차례대로 넣어보면
STACK 스택
나중에 넣은 것부터 · LIFOQUEUE 큐
먼저 넣은 것부터 · FIFO
값을 정렬한 것도 아닌데 결과가 갈린 건, 꺼내는 자리가 한쪽 끝으로 고정돼 있어서입니다. 그래서 Stack·Queue라는 이름은 값을 담는 그릇보다 넣고 꺼내는 규칙을 가리킵니다.
2. Stack — 맨 위에서 넣고 빼기
Stack에서 쓰는 동작은 세 가지입니다. push는 맨 위에 넣고, pop은 맨 위 값을 꺼내면서 지우고, 는 지우지 않고 맨 위 값만 봐요. 자바스크립트 배열의 push()와 pop()이 마침 맨 뒤에서만 일하니까 그대로 Stack이 됩니다.
const stack = ["A", "B"];
stack.push("C"); // ["A", "B", "C"]
stack.pop(); // "C"가 먼저 나옴
배열이라 stack[1]로 B를 바로 꺼낼 수도 있지만, 그렇게 쓰는 순간 Stack 규칙에서 벗어나요. Stack으로 쓰려면 맨 위 한 군데로만 드나들어야 합니다. 실행 취소(Undo)도 이렇게 동작해요. 문장을 세 번 고쳤다면 마지막 수정부터 되돌리죠.
3. Queue — 먼저 들어온 순서대로 처리하기
Queue는 뒤에 넣는 걸 enqueue, 앞에서 꺼내는 걸 dequeue라고 합니다. 배열로는 push와 shift로 흉내 냅니다.
const queue = ["A", "B"];
queue.push("C"); // ["A", "B", "C"]
queue.shift(); // "A"가 먼저 나옴
규칙은 맞는데 항목이 많아지면 shift()가 걸려요. 맨 앞을 지우면 뒤에 남은 값들의 인덱스를 하나씩 당겨야 하니까요. 그래서 큰 Queue는 값을 옮기는 대신 맨 앞 위치만 기억합니다. 이 위치를 인덱스라고 불러요.
A를 꺼내도 B와 C는 제자리에 있고, 배열을 연속된 칸으로 보면 n개짜리 배열의 head만 0에서 1로 옮겨 갔습니다. 처리한 앞 칸이 계속 쌓이면 공간이 아까우니, 실제 구현에서는 앞부분을 가끔 정리하거나 끝에 닿으면 처음으로 돌아가는 원형 버퍼(ring buffer)를 써요.더 보기 · shift()는 무조건 O(n)일까?
shift()는 나머지 n-1개를 당기니 O(n)입니다. 그런데 자바스크립트 명세는 실행 시간을 정해 두지 않아서, 엔진이 내부 최적화로 더 빠르게 처리하기도 해요. 작은 배열에선 신경 쓸 일이 없고, 값이 많이 오가는 Queue에서만 head 인덱스를 고려하면 됩니다.
4. Deque — 앞뒤를 둘 다 쓸 수 있다면
는 Double-Ended Queue의 줄임말이에요. 앞에서도 넣고 빼고, 뒤에서도 넣고 뺄 수 있습니다. 2장의 실행 취소에 기록 개수 제한을 걸면 바로 이게 필요해져요. 기록은 최대 3개예요. 새로 편집하거나 실행 취소해 보세요.새 편집은 뒤로, 넘치면 앞에서 버리기
편집과 실행 취소는 뒤쪽에서만 일어나니 여기까지는 Stack입니다. 넘친 기록을 버릴 때만 앞쪽을 써요. 뒤로만 넣고 빼면 Stack, 뒤에 넣고 앞에서 빼면 Queue가 되고, Deque는 그 둘을 한 구조에서 같이 합니다.
5. 연결 리스트는 Stack·Queue와 같은 종류일까요?
Stack·Queue를 찾아보면 연결 리스트(Linked List)가 같이 나와서 Queue의 다른 이름처럼 보이기도 합니다. 그런데 Stack·Queue는 어떤 순서로 넣고 꺼낼지 정한 규칙이고, Array·Linked List는 그 값을 어떻게 저장할지 고른 방법입니다. Queue를 배열로도, 연결 리스트로도 만들 수 있는 이유예요. 칸 번호(인덱스)로 원하는 칸에 바로 찾아가요. 노드가 next를 따라 한 칸씩 이어져요. 맨 앞이 head, 맨 뒤가 tail입니다.Queue를 꼭 배열로 만들어야 할까요?
Linked List는 값과 다음 노드를 가리키는 next를 묶은 를 줄줄이 이은 구조예요. Queue를 여기에 올리면 head에서 꺼내고 tail에 붙이면 되고, 양 끝을 이미 알고 있으니 둘 다 O(1)입니다. 대신 중간의 n번째 값은 head부터 차례로 따라가야 해서 O(n)이 들어요.
React 훅도 이렇게 이어져 있습니다. 처음 그릴 때 단일 연결 리스트(Singly Linked List)는 노드가 Stack을 Linked List로 만들면 useState, useEffect가 불린 순서대로 노드가 next로 연결되고, 다시 그릴 때는 같은 순서로 따라가며 값을 꺼냅니다. 훅을 조건문 안에서 부르면 안 되는 이유도 여기 있어요. 한 번 건너뛰면 순서가 어긋나서 다른 훅의 값을 읽게 됩니다.더 보기 · 단일 연결 리스트와 이중 연결 리스트
next 하나만 갖고, 이중 연결 리스트(Doubly Linked List)는 이전 노드를 가리키는 prev도 가집니다. 단일 연결 리스트에서 tail을 지우려면 그 앞 노드를 찾으러 처음부터 걸어가야 해서, 뒤에서도 빼야 하는 Deque는 보통 이중 연결 리스트로 만들어요.head 한쪽에서 push·pop을 다 처리합니다. 직접 짤 때는 빈 리스트와 원소가 하나뿐인 리스트가 까다로워요. 이때는 head와 tail을 같이 바꿔야 해서, 이 두 경우부터 테스트해 보는 게 좋습니다.
6. 성능은 얼마나 다를까요?
Stack이라서 빠르고 Queue라서 느린 건 없어요. 같은 Queue도 어떤 저장 구조 위에 올렸느냐에 따라 비용이 달라집니다. 아래 표의 O(1), O(n)은 표기로, 데이터가 늘 때 작업량이 어떻게 늘어나는지를 나타내요.
| 구현 | 넣기 | 꺼내기 | 따로 신경 쓸 것 |
|---|---|---|---|
| Stack + 배열 맨 뒤 | push O(1)* | pop O(1) | 배열이 꽉 차면 더 큰 공간으로 옮김 |
Queue + 배열 shift() | push O(1)* | shift() O(n) | 남은 값을 앞으로 당김 (3장) |
| Queue·Deque + head 인덱스, 원형 버퍼, 연결 리스트 | O(1) | O(1) | 맨 앞·맨 뒤 위치를 따로 관리 |
*이 붙은 O(1)은 분할상환(amortized) 비용입니다. 대부분의 push는 바로 끝나지만, 배열이 꽉 찼을 때 한 번은 전체를 새 공간으로 옮겨요. 그 비용을 모든 push에 나눠 보면 평균이 O(1)이 되는 거죠.
7. 우리가 작성한 함수도 Stack을 쓸까요?
씁니다. 함수가 다른 함수를 부르면 그 실행 문맥이 에 한 칸씩 쌓여요. 그런데 setTimeout으로 넘긴 함수는 여기 바로 쌓이지 않고, Task Queue라는 별도의 줄에 먼저 섭니다.setTimeout으로 넘긴 함수는 언제 돌까?
function main() {
load();
setTimeout(render, 0);
}
function load() { … }
function render() { … }
main();
load()는 main()보다 늦게 불렸는데 먼저 끝납니다. 나중에 불린 함수가 먼저 끝나는 구조라 LIFO 그대로고, 종료 조건 없는 재귀가 터지는 이유도 여기 있어요. 호출이 끝나지 않고 칸만 쌓이다가 공간이 바닥나면 Maximum call stack size exceeded가 납니다.
render()는 0ms로 걸었는데도 main()이 다 끝난 뒤에야 돌아요. Task Queue에 선 함수는 Call Stack이 빌 때까지 기다리기 때문입니다. 이 줄은 Event Loop를 볼 때 다시 나와요.
8. 실제로 어디에 쓰일까요?
| 상황 | 어울리는 규칙 | 왜 쓰는가 |
|---|---|---|
| 브라우저 뒤로·앞으로 가기 | Stack 두 개 | 뒤로 가면 빠진 페이지가 앞으로 쪽에 쌓이고, 새 페이지로 가면 앞으로 쪽이 비워짐 |
| 토큰 갱신 중에 실패한 요청 모아 두기 | Queue · FIFO | 갱신이 끝나면 들어온 순서대로 다시 보냄 |
| 범위를 밀면서 최댓값 찾기 (슬라이딩 윈도우) | Deque | 새 값은 뒤에서 넣고, 범위를 벗어난 값은 앞에서 뺌 |
| 트리·그래프를 넓게 탐색하는 BFS | Queue | 발견한 순서대로 다음 노드를 봄 |
| 트리·그래프를 깊게 탐색하는 DFS | Stack 또는 재귀 | 한 갈래를 끝까지 따라간 뒤 돌아옴 |
탐색 두 줄은 같은 주의 Tree, Graph, DOM Tree 글에서 더 자세히 다뤄요. BFS는 발견한 노드를 Queue에 넣어서 출발점에서 가까운 노드부터 보고, DFS는 Stack이나 재귀 호출의 Call Stack을 써서 한 갈래를 끝까지 파고들어요.
직접 고쳐 쓴 도구에서
브라우저 자동화 도구 Playwriter는 한 세션 안의 요청을 순서대로 실행합니다. 줄이 세션마다 따로고 탭은 같이 쓰니까, 에이전트 둘이 같은 탭을 잡으면 한쪽이 페이지를 여는 도중에 다른 쪽 클릭이 끼어들어요. 그래서 Playwriter를 고쳐 쓰면서 탭마다 주인을 정했습니다. 에이전트는 자기 탭에서만 일하고, 새 탭을 잡는 순간만 프로필 전체에서 한 줄로 세웠어요. 아래에서 「공식 그대로」와 「고친 뒤」를 바꾸면 코드도 같이 바뀝니다. 줄은 둘 다 에이전트마다 하나예요. 다른 건 탭을 같이 쓰느냐예요.요청이 동시에 들어오면 누가 어디서 돌까
두 코드 모두 Queue예요. 공식은 Promise를 이어 붙여 줄을 만들고, 고친 쪽은 「고친 뒤」 코드에서 순서는 Queue가 정하고, 한 번에 하나만 들여보내는 건 Semaphore는 하나가 아니라 정해진 수만큼 들여보냅니다. 프론트에서 자주 보는 예가 이미지 여러 장 업로드예요. 20장을 한꺼번에 보내지 않고 동시에 3장씩만 올리면, 넷째 장은 자리가 날 때까지 기다립니다. 탭을 새로 잡는 순간은 프로필 전체에서 한 번에 한 에이전트만 처리해요. 셋이 동시에 올라가고, 하나가 끝나야 사진 4가 들어가요. Queue는 누가 먼저인지, Mutex는 한 번에 하나만 들어가는지, Semaphore는 동시에 몇 개까지 들어가는지를 정해요.push로 뒤에 넣고 shift로 앞에서 꺼냅니다. 부딪힘은 탭 소유권이 막습니다. 실제 고친 코드에는 너무 오래 기다린 요청을 줄에서 빼는 처리와, 서로 부딪히지 않는 요청은 함께 보내는 예외가 더 붙어 있습니다.더 보기 · 한 번에 하나만 — Mutex와 Semaphore
running 깃발이 맡아요. 이렇게 공유 자원에 동시에 하나만 들어가게 막는 장치를 Mutex(상호 배제)라고 부릅니다. 새 탭을 잡는 순간을 프로필 전체에서 하나씩 처리하는 줄도, 탭마다 주인을 하나로 정한 소유권도 같은 생각이에요.한 번에 하나, 또는 정해진 수만큼
정리
넣는 순서가 같아도 꺼내는 끝이 다르면 결과가 갈립니다. 한쪽 끝만 쓰면 Stack, 반대쪽 끝에서 꺼내면 Queue, 양쪽을 다 열어 두면 Deque예요. 이 규칙을 배열에 올릴지 연결 리스트에 올릴지는 그다음 문제고, 성능은 거기서 정해집니다. 우리가 매일 쓰는 함수 호출도 이미 Stack 위에서 돌고 있고요.
복습 질문
① A·B·C를 넣고 두 번 꺼낸 뒤 D를 넣었다면, 다음에 꺼낼 때 Stack과 Queue에서는 각각 뭐가 나올까?
Stack은 D, Queue는 C입니다. Stack은 방금 넣은 D가 맨 위에 올라가고, Queue는 D가 남아 있던 C 뒤에 줄을 서요.
② 뒤로 가기를 두 번 누른 다음 링크로 새 페이지에 가면, 앞으로 가기는 어떻게 될까?
비활성화됩니다. 뒤로 가며 쌓아 둔 앞으로 쪽 Stack이 새 페이지로 가는 순간 비워집니다.
③ console.log(1); setTimeout(() => console.log(2), 0); console.log(3); 의 출력 순서는?
1 → 3 → 2예요. setTimeout 콜백은 Task Queue에 서고, 지금 Call Stack에서 돌던 코드가 3까지 다 찍고 빠진 다음에야 실행됩니다.
④ 항목이 수만 개인 Queue를 shift()로 하나씩 비우면 전체 작업량은?
꺼낼 때마다 남은 값을 당기니 한 번이 O(n), 다 비우면 O(n²)입니다. head 인덱스로 바꾸면 값을 옮기지 않아서 전체가 O(n)으로 줄어요.
⑤ BFS에서 Queue 대신 Stack을 쓰면 어떻게 될까?
가장 최근에 발견한 노드부터 보게 돼서, 한 갈래를 깊게 파고드는 DFS 순서로 바뀝니다.
⑥ 「공식 그대로」에서 에이전트 1의 C는 기다리는데 에이전트 2의 B는 왜 안 기다릴까?
줄이 세션마다 하나라서요. C는 같은 줄의 A 뒤에 섰고, B는 다른 줄의 맨 앞이라 바로 실행됩니다. 고친 쪽은 B를 세우는 대신 자기 탭에서 돌게 해서 부딪히지 않게 했어요.