스택: 스택 클래스와 활용

들어가며

최초 작성일(yy/mm/dd): 24/01/07 최초 작성

학습 목표

1. 자바8에서의 스택 이용법과 주의사항을 학습한다.
2. 스택이 어떤 상황에서 활용되는지 간략하게 살펴본다.

학습 상황

• 자바에 내장된 스택 클래스를 이용할 때의 주의사항을 기억하고, Problem Solving 시에 효율적이고 적절하게 쓸 필요가 있다.

스택: Java.util.Stack

스택 클래스 뜯어보기

Fig 1. Java.util.Stack의 상속 순서와 설명
출처: docs.oracle.com

• 스택과 상속
  
  스택 클래스까지의 상속 관계를 살펴보자면, Object → AbstractCollections → AbstractList → Vector → Stack 순으로 상속됩니다.

Fig 2. java.util.Stack이 상속받은 메소드
출처: docs.oracle.com

특히 Vector에서 직접적으로 상속된 메소드가 많다는 점이 눈에 띕니다. 따라서 스택 클래스와 관련해서는 Vector를 유심히 살펴봐야 합니다.

• 스택 클래스의 단점

  문서 마지막에서는 스택 클래스를 사용하는 개선된 방식으로 ArrayDeque의 이용을 권장합니다. 이는 Vector 클래스가 가진 결점 때문입니다.

  1. 배열과 같은 방식으로 접근되고 사용될 수 있음

     Random Access 방식의 접근은 물론, add와 같은 메소드 역시 특정 인덱스에 요소를 추가할 수 있다는 점에서 스택이 가진 구조와 배치됩니다.

Fig 3. java.util.Stack의 기본 메소드
출처: docs.oracle.com

일례로, search 메소드가 대표적입니다. 스택 자료구조에서 Random Access 방식의 search는 어울리지 않습니다.

2. 동기화(synchronization)로 인한 성능 및 동시성 저하벡터 클래스에서는 get(), set() 등 메소드에 동기화가 적용됩니다. 동기화는 사용중인 스레드 이외에서의 접근을 막아 동시성을 저하합니다.

   또한, 락 오버헤드(Lock Overhead)로 인한 비용으로 성능 역시 저하됩니다.

• 자바에서 스택 이용

  Deque<E> stack = new ArrayDeque<E>();

  Vector에서 비롯된 Stack의 문제점이 개선되었고, search() 메소드는 이용할 수 없습니다.

  그러나 Problem Solving에서 search() 메소드가 급히 필요하거나 구현 시간이 부족하다면, 권장되지 않겠지만 Stack 클래스를 이용할 수 있지 않을까요?
  

스택: 어디에 쓰일까?

스택의 활용

• Postfix/Prefix conversion

• 되돌아가기 및 취소(Redo-undo) 기능

• 스택 메모리

  지역 변수, 매개 변수, 반환 주소(return address)가 저장되는 메모리입니다. 주로 primitive type의 지역변수, 매개변수가 저장됩니다.

  ↔ 전역 변수는 Static 메모리에 저장됩니다.
  

• 문자열 역순

• 함수 호출

  메소드가 호출되면 필요한 크기만큼 메모리를 할당받고, 수행이 끝나면 메모리를 반환합니다. 최상단 메소드가 실행중인 메소드이며, 스택의 bottom-up 순서는 호출된 순서입니다.
  

⇒ Problem Solving만이 아니라, JVM이나 메모리 구조와 관련된 주제도 많다는 점이 보입니다.

참고 자료

• https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated
• https://brunch.co.kr/@kd4/156
  https://didrlgus.github.io/java/05-post/
  → synchronization에 대해 엿볼 수 있는 글입니다.
  
• https://hyeyoo.com/79 → Lock에 관해 정리해주신 글입니다.
  
• https://baddotrobot.com/blog/2013/01/10/stack-vs-deque/ → stack interface에서 제한을 통해 스택을 구현하는 법에 대해 소개하는 글들입니다.