자료구조 스택에 대해서 설명해 주세요.

스택(Stack)은 후입선출(LIFO) 개념을 가진 선형 자료구조입니다. 스택에서 삽입(push)과 삭제(pop)는 최상단(top)에서만 이루어집니다. 비어있는 스택에서 pop을 시도하는 경우를 스택 언더플로우라고 하며, 스택이 넘치는 상황을 스택 오버플로우라고 합니다. 스택의 대표적인 활용 사례로는 스택 메모리, 뒤로 가기 기능, 수식 괄호 검사 등이 있습니다.

---

자바에서 스택은 어떻게 사용할 수 있나요?

자바에는 Stack이라는 클래스가 있습니다. 하지만 Deque 인터페이스 구현체를 사용하는 것이 권장됩니다. 왜냐하면, Stack 클래스는 내부적으로 Vector를 상속받고 있기 때문입니다. Vector의 메서드들은 synchronized로 구현되어 있어 멀티 스레드 환경에서는 동기화의 이점이 있을 수 있겠으나, 단일 스레드 환경에서는 불필요한 동기화 작업으로 인해 성능 측면에서 좋지 않습니다. Vector는 하위 호환을 위해 존재한다고 알고 있습니다.

반면 Deque 인터페이스는 스택의 후입선출 특성을 완전히 유지하면서도 동기화 작업을 가지는 구현체와 그렇지 않은 구현체를 선택할 수 있습니다. 대표적인 구현체로 ArrayDeque와 LinkedList가 있습니다. 이 중 ArrayDeque가 더 나은 성능을 보여주는 경우가 많습니다.