DevRoutine — 매일 기술 면접 질문

Stack, Queue, Deque는 데이터를 넣고 빼는 규칙이 다른 선형 자료구조입니다. Stack은 마지막에 넣은 것을 먼저 꺼내는 LIFO, Queue는 먼저 넣은 것을 먼저 꺼내는 FIFO, Deque는 양쪽 끝에서 삽입과 삭제가 가능한 구조입니다.

핵심 개념

Stack은 함수 호출, 괄호 검사, 되돌리기 같은 최근 상태 처리에 적합합니다.
Queue는 작업 대기열, BFS, 메시지 처리처럼 도착 순서가 중요한 상황에 적합합니다.
Deque는 슬라이딩 윈도우 최댓값, 양방향 큐, 브라우저 히스토리처럼 양끝 조작이 필요할 때 사용합니다.

동작 방식 또는 판단 기준

이 주제를 이해할 때는 다음 순서로 보면 실무 적용이 쉬워집니다.

무엇을 해결하려는가: 성능, 표현력, 안정성, 접근성 중 어떤 문제를 줄이려는지 확인합니다.
전제 조건은 무엇인가: 정렬 여부, 브라우저 지원, 네트워크 특성, 동시성 조건처럼 성립해야 하는 조건을 점검합니다.
비용은 어디서 발생하는가: 시간 복잡도, 메모리, 캐시, 재시도, 렌더링 비용처럼 병목 지점을 나눠 봅니다.
실패 시 어떤 문제가 생기는가: 잘못 적용했을 때의 버그나 운영 리스크를 함께 고려합니다.

실제 예시

JavaScript

// Stack
const stack = [];
stack.push('A');
stack.push('B');
stack.pop(); // B

// Queue: JS 배열 shift는 O(n)이므로 head index 사용
class Queue {
  items = [];
  head = 0;
  enqueue(x) { this.items.push(x); }
  dequeue() { return this.items[this.head++]; }
  get size() { return this.items.length - this.head; }
}

실무에서 주의할 점

JavaScript에서 큰 큐에 shift()를 반복하면 요소 재배치 때문에 느릴 수 있습니다.
Stack을 재귀로만 구현하면 입력이 깊을 때 call stack overflow가 발생할 수 있습니다.
Deque는 언어 표준 라이브러리에 없을 수 있어 직접 구현 품질이 중요합니다.

실무 적용 가이드

문제의 순서 규칙이 LIFO인지 FIFO인지 먼저 확인합니다.
BFS는 queue, DFS는 stack 또는 재귀를 사용합니다.
성능이 중요한 큐는 ring buffer나 검증된 deque 라이브러리를 사용합니다.

함께 연결해서 보면 좋은 키워드

Stack, Queue, Deque, FIFO, LIFO

정리

Stack, Queue, Deque는 데이터를 넣고 빼는 규칙이 다른 선형 자료구조입니다. 다만 개념 자체보다 중요한 것은 적용 조건과 한계를 함께 이해하는 것입니다. 작은 예제에서는 단순해 보여도 실제 서비스에서는 성능, 보안, 유지보수성, 접근성 요구사항이 함께 얽히므로, 문제의 성격을 먼저 파악한 뒤 적절한 도구로 선택하는 것이 좋습니다.

Stack, Queue, Deque의 차이를 설명해주세요.

답변 포인트

정답 및 해설