저번 시간에 이어, 이번에는 스택(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에 더 이상 데이터를 추가할 수 없는 것을 의미합니다. 주로 재귀 호출에서 빠져나오지 못할 때 발생합니다.
마치며
이번 시간에는, Stack에 대한 면접 질문을 간단하게 알아보았습니다. Queue에 비해 등장하는 빈도는 낮지만, 그래도 명확하게 이해하고 넘어가야 하는 부분입니다.
다음 시간에는, 트리(Tree) 자료구조에 대해 알아보겠습니다.
답글 남기기