자료구조 스택

자료구조 스택

●스택(Stack)

• 후입선출이(LIFO)라는 개념을 가진 선형 자료구조
• 스택 자료구조에서 삭제(pop)는 가장 최상단(top)에서만 이루어지며 비어있는 스택에서 값을 추출하려고 시도하는 경우를 스택 언더플로우라고 하며, 스택이 넘치는 경우를 스택 오버플로우라고 함
• 대표적인 활용 사례는 스택 메모리, 브라우저 뒤로가기 기능, 언두 기능, 수식 괄호 검사 등이 있음

●자바에서 스택은 어떻게 사용할까?

• Stack이라는 클래스를 사용할 수 있지만, Deque 인터페이스 구현체를 사용하는 것이 권장이 됨 왜냐하면, Stack 클래스는 내부적으로 Vector를 상속 받고 있기 때문, Vector를 상속받은 Stack은 인덱스를 통한 접근, 삽입, 제거 등이 실질적으로 가능하며 이는 후입선출 특징에 맞지 않기 때문에 개발자가 실수할 여지가 있음

• 또한, Vector의 메소드들은 synchronized로 구현되어 있어 멀티 스레드 환경에서는 동기화의 이점이 있으나, 단일 스레드 환경에서는 불필요한 동기화 작업으로 인해 성능 측면에서 좋지 않음

• Deque 인터페이스는 후입선출의 특성을 완전히 유지하면서도 동기화 작업을 가지는 구현체와 그렇지 않은 구현체를 선택할 수 있으며, 이는 개발자가 필요에 따라 동기화 작업의 오버헤드를 회피하고 성능을 최적화할 수 있도록 함

참고 : https://jud00.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9DStack%EA%B3%BC-%ED%81%90Queue%EC%97%90-%EB%8C%80%ED%95%B4%EC%84%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EC%9E%90