저번 시간에 이어, 이번에는 스택(Stack) 자료구조에 대해 알아보겠습니다. Stack은 Queue와 비교되며 나오는 개념이긴 하지만, Queue에 비해 상대적으로 적게 나오는 편입니다. 중요하긴 해도 Queue만큼의 질문 범위가 넓진 않다고 할 수 있죠. 어렵지 않으니 간단하게 알아보고 넘어가도록 합시다.
Q: Stack은 어떤 자료구조인가요?
후입선출 LIFO(Last In First Out)의 자료구조입니다. push, pop 모두 O(1)의 시간복잡도를 가지며 후위 표기법 연산, 괄호 유효성 검사, 웹 브라우저 방문기록(뒤로 가기), DFS 등이 있습니다.
Q: Stack과 Queue의 차이점은 무엇인가요?
Stack은 후입선출(LIFO)로 가장 최근에 추가된 요소가 먼저 제거됩니다. 반면 Queue는 선입선출(FIFO) 원칙을 따르며, 가장 먼저 추가된 요소가 먼저 제거됩니다.
Q: 스택 오버플로우(Stack Overflow)란 무엇이고 어떤 상황에서 발생할까요?
Stack에 더 이상 데이터를 추가할 수 없는 것을 의미합니다. 주로 재귀 호출에서 빠져나오지 못할 때 발생합니다.
자료구조 추천 서적
Dynamic Array 관련하여 깊게 공부할 수 있는 책 3권 추천해 드립니다. 🙂
마치며
이번 시간에는, Stack에 대한 면접 질문을 간단하게 알아보았습니다. Queue에 비해 등장하는 빈도는 낮지만, 그래도 명확하게 이해하고 넘어가야 하는 부분입니다.
다음 시간에는, 트리(Tree) 자료구조에 대해 알아보겠습니다.
“이 포스팅은 쿠팡 파트너스 활동의 일환으로, 이에 따른 일정액의 수수료를 제공받습니다.”
답글 남기기