CS Fundamentals

스택, 큐, 덱에 대해서 설명해주세요

LIFO, FIFO, 양방향. 스택·큐·덱이 실제로 어떻게 동작하는지, 슬라이딩 윈도우 같은 고급 알고리즘까지 인터랙티브 시각화로 완벽히 준비합니다.

2026년 3월 18일 · 약 12분 읽기

Q. "스택, 큐, 덱의 차이를 설명하고, 각각 어떤 상황에서 사용하는지 말씀해주세요."

예상 꼬리질문

답변 가이드

"스택은 LIFO(Last In, First Out)로 한쪽 끝에서만 삽입·삭제합니다. 콜 스택, Undo, 괄호 검사가 대표 사례입니다. 큐는 FIFO(First In, First Out)로 한쪽에서 넣고 반대쪽에서 꺼냅니다. BFS, 프린터 대기열, 이벤트 처리에 사용합니다."

"덱은 양쪽 모두에서 삽입·삭제가 가능한 가장 유연한 구조로 스택과 큐의 상위 호환입니다. 세 자료구조 모두 삽입·삭제가 O(1)이지만, 어느 끝이 열려 있는지가 핵심 차이입니다."

"덱의 진가는 단조 덱(Monotonic Deque)으로 슬라이딩 윈도우 최대값을 O(nk)에서 O(n)으로 줄이는 것입니다. 각 원소를 최대 한 번만 삽입·삭제하기 때문입니다."

코딩 테스트에서 가장 자주 나오는 자료구조 세 가지가 스택, 큐, 덱입니다. "다 비슷하지 않나요?"라는 생각이 든다면, 이 글이 도움이 될 것입니다.

세 구조의 차이는 단순히 어느 쪽이 열려 있느냐지만, 그 차이가 알고리즘의 시간복잡도를 O(nk)에서 O(n)으로 바꾸기도 합니다.

1. 세 자료구조 한눈에 비교

꼬리질문: "스택, 큐, 덱의 차이를 설명해주세요"

스택, 큐, 덱은 모두 선형 자료구조로 삽입·삭제가 O(1)이지만, 어느 쪽 끝에서 연산이 허용되는지가 다릅니다.

스택은 top 한쪽만, 큐는 rear 삽입·front 삭제, 덱은 양쪽 모두 열려 있습니다.

세 가지 자료구조를 나란히 놓고 직접 원소를 넣고 빼보세요.

스택(Stack)

LIFO
↑ top
1
2
3← top

한쪽(top)에서만 삽입·삭제

큐(Queue)

FIFO
← front (dequeue)rear (enqueue) →
A
B
C

rear 삽입, front 삭제

덱(Deque)

양방향
↔ frontrear ↔
A
B
C

양쪽에서 모두 삽입·삭제

특성스택큐덱
순서 원칙LIFOFIFO양방향
삽입top만rear만front/rear 모두
삭제top만front만front/rear 모두
삽입/삭제O(1)O(1)O(1)

2. 스택 — LIFO의 힘

꼬리질문: "스택의 LIFO 특성이 실제로 어디에 활용되나요?"

스택(Stack)은 마지막에 넣은 것이 가장 먼저 나오는 LIFO(Last In, First Out) 구조입니다. 함수 호출 스택이 그 원리 그대로 — 가장 최근에 호출된 함수가 먼저 반환됩니다.

브라우저 뒤로 가기, 텍스트 에디터 Undo, 괄호 검사까지 — LIFO 특성 덕분에 역순 처리와 되돌리기가 필요한 모든 곳에 스택이 활용됩니다.

배열 기반 스택은 캐시 친화적이지만 리사이징 시 O(n)이 발생합니다. 연결 리스트 기반은 항상 O(1)이지만 포인터 오버헤드가 있습니다.

괄호 검사 시뮬레이션으로 스택이 어떻게 동작하는지 확인해 보세요.

프리셋 선택:

스택 상태:

↑ top

비어 있음

입력 문자열:

{
[
(
)
]
}
0 / 7 단계

3. 큐 — FIFO와 순환 버퍼

꼬리질문: "배열로 큐를 구현할 때 발생하는 문제와 해결책은?"

큐(Queue)는 먼저 온 것이 먼저 나오는 FIFO(First In, First Out) 구조로, 줄 서기와 같습니다. 프린터 대기열, CPU 스케줄링의 준비 큐, BFS 알고리즘이 모두 큐를 기반으로 합니다.

배열로 큐를 구현할 때 흔히 발생하는 메모리 낭비 문제가 있습니다. dequeue 후 앞 공간이 비어도 재사용되지 않습니다. 순환 배열(Circular Buffer)은 head와 tail 포인터를 모듈러 연산으로 관리해 이 문제를 해결합니다.

순환 버퍼가 메모리를 어떻게 재사용하는지 직접 확인해 보세요.

순환 배열capacity = 6
0
1
2
3
4
5
front: 0
rear: 0
size: 0/6

순환 배열 공식:

rear = (rear + 1) % 6 → 인덱스가 5 이후 0으로 래핑

데이터 있음
방금 enqueue
빈 슬롯

4. 덱 — 양방향의 유연함

꼬리질문: "덱이 스택과 큐보다 유리한 상황은 언제인가요?"

덱(Deque, Double-Ended Queue)은 front와 rear 양쪽에서 모두 삽입과 삭제가 가능한 가장 유연한 선형 자료구조입니다. 스택처럼도, 큐처럼도 쓸 수 있습니다.

덱이 진가를 발휘하는 것은 양방향 접근이 모두 필요한 알고리즘입니다. 앞에서 오래된 원소를 제거하고 뒤에서 새 원소를 관리하는 단조 덱 패턴이 대표적입니다.

모드 토글로 스택·큐·덱 모드를 전환하며 양방향 연산을 직접 체험해 보세요.

모든 연산 사용 가능
← frontrear →
FA
B
RC
index 0 (front)index 2 (rear)

front 연산

rear 연산

일반 모드: 덱의 4가지 연산을 모두 자유롭게 사용할 수 있습니다.

5. 단조 덱 — 슬라이딩 윈도우 최대값

꼬리질문: "슬라이딩 윈도우 최대값을 O(n)으로 구하는 방법을 설명해주세요"

덱의 진가는 단조 덱(Monotonic Deque) 기법에 있습니다. 배열에서 크기 k인 모든 슬라이딩 윈도우의 최댓값을 구할 때, 단순 접근은 O(nk)지만 단조 덱은 각 원소를 최대 한 번만 삽입·삭제하여 O(n)으로 해결합니다.

핵심 원리는 새 원소보다 작은 원소를 rear에서 제거하는 것입니다. 제거된 원소는 어차피 최대값이 될 수 없으므로 정확성이 유지됩니다. LeetCode 239(Sliding Window Maximum) 같은 문제에 직접 적용됩니다.

슬라이딩 윈도우가 이동하면서 단조 덱이 어떻게 갱신되는지 한 단계씩 확인해 보세요.

배열 (k=3):

[0]1
[1]3
[2]-1
[3]-3
[4]5
[5]3
[6]6
[7]7
현재 윈도우: [0…0]

덱 상태 (인덱스 저장, front = 현재 최댓값):

front →비어 있음← rear

결과 (각 윈도우 최댓값):

아직 없음
시뮬레이션을 시작하세요.
① 윈도우 밖 제거
② 작은 원소 제거
③ 현재 원소 삽입
④ 최댓값 기록
0/8 원소 처리

6. 언제 무엇을 쓸까?

꼬리질문: "세 자료구조 중 어떤 기준으로 선택하나요?"

세 자료구조를 "접근 패턴" 기준으로 고르면 쉽습니다. 역순 처리나 되돌리기가 필요하면 스택, 순서대로 공정하게 처리해야 하면 큐, 양쪽을 모두 다뤄야 하거나 슬라이딩 윈도우 최적화가 필요하면 덱을 선택합니다.

시나리오를 클릭하며 어떤 자료구조가 적합한지 확인해 보세요.

시나리오를 선택하세요:

위 시나리오 중 하나를 선택하세요

스택(Stack)LIFO
  • •
  • •
  • •
  • •
큐(Queue)FIFO
  • •
  • •
  • •
덱(Deque)양방향
  • •
  • •
  • •

퀴즈로 확인하기

개념을 제대로 이해했는지 확인해 보세요.

퀴즈 1

괄호 유효성 판단

다음 문자열의 괄호 유효성을 스택으로 검사할 때,
유효한 것은?

(A) ([)]
(B) {[()]}
(C) (((
(D) )(
퀴즈 2

순환 배열 큐 — front 포인터

capacity=5인 순환 배열 큐에서 다음 연산을 순서대로 실행했다.

enqueue(A), enqueue(B), enqueue(C)
dequeue(), dequeue()
enqueue(D), enqueue(E), enqueue(F)

front 포인터의 인덱스는?
퀴즈 3

단조 덱의 결과

arr = [2, 1, 5, 3, 6, 4, 8, 5]
k = 3
sliding_window_max(arr, k) 의 결과는?
퀴즈 4

덱으로 스택 에뮬레이션

덱(Deque)으로 스택을 에뮬레이션하려 한다.
올바른 연산 조합은?
퀴즈 5

슬라이딩 윈도우 시간복잡도

길이 n인 배열에서 크기 k인 모든 슬라이딩 윈도우의 최댓값을 구할 때,
각 방법의 시간복잡도는?

방법 1: 각 윈도우마다 max() 직접 호출
방법 2: 단조 덱(Monotonic Deque) 사용

면접 체크리스트

이 항목들을 자신 있게 설명할 수 있다면 자료구조 질문은 준비 완료입니다.

  • - 스택: 한쪽만 열린 LIFO — 역순 처리, Undo, 괄호 검사, 콜 스택
  • - 큐: 양쪽 각각 열린 FIFO — 순서 보장, BFS, 이벤트 처리
  • - 덱: 양쪽 모두 열린 만능 — 스택+큐 에뮬레이션, 슬라이딩 윈도우 O(n)
  • - 시간복잡도: 삽입·삭제 모두 O(1) — 어느 끝이 열려 있느냐가 알고리즘 복잡도를 결정
  • - 단조 덱: 새 원소보다 작은 원소를 rear에서 제거 → 슬라이딩 윈도우 최대값 O(n)
  • - 순환 버퍼: 배열 큐의 메모리 낭비 문제를 모듈러 연산으로 해결

참고 자료

의견을 들려주세요

서비스 개선에 큰 도움이 됩니다. 익명으로 자유롭게 남겨주세요.

0 / 1000