스택(Stack)과 큐(Queue)는 어떤 순서로 데이터를 처리하며 구현 시 무엇을 주의해야 하나요?

이렇게 답해 보세요 (핵심 답변)

스택은 마지막에 넣은 값을 먼저 꺼내는 후입선출(LIFO) 추상 자료형이고, 큐는 먼저 넣은 값을 먼저 꺼내는 선입선출(FIFO) 추상 자료형입니다. 스택은 함수 호출 복귀와 DFS에, 큐는 작업 대기열과 BFS에 잘 맞습니다. 다만 배열, 연결 리스트, 원형 버퍼 중 어떤 자료구조로 내부를 구현하느냐에 따라 실제 연산 비용이 달라지므로 추상적인 처리 순서와 구체적인 시간 복잡도를 구분해 설명해야 합니다.

함께 설명하면 좋은 이유 (꼬리질문 대비)

1. 배열의 맨 끝에서 push와 pop만 수행하는 스택은 간단하면서도 상환 O(1)로 빠르게 동작합니다.
2. 배열 맨 앞 요소를 매번 삭제(shift)하는 큐는 O(n) 이동 비용이 들기 때문에, 읽기 인덱스를 따로 두거나 원형 버퍼·연결 리스트를 써야 O(1)을 유지할 수 있습니다.

면접에서 자주 하는 실수

큐라는 이름만 붙이면 내부 구현 방식과 상관없이 모든 dequeue 연산이 무조건 O(1)이라고 단정하면 안 됩니다.