[Java] stack의 구현

stack이란?

• First in Last out인 자료구조이다.
• Java에서 Stack이라는 클래스로 구현할 수 있다.

Stack class

• vector를 상속받는 클래스다.
• 추가 메모리 할당시 기존 사이즈의 두 배 만큼 할당한다.

Deque vs Stack

그럼 Deque를 활용해서 stack처럼 사용하면 되지 않는가?라는 생각이 들 수 있다.
Java 공식문서에서는 레거시인 Stack 대신 Deque를 사용하기를 권장한다.

• 함수는 아래와 같이 매핑된다.
  - push = addFirst(e)
  - pop() = pollFirst() 또는 removeFirst()
  - peek() = peekFirst()
• 속도는 Deque를 통해 구현했을 때 Stack 구현체보다 더 빠르다고 한다.
• 메모리는 추가 할당시 Deque는 기존 사이즈의 50%만큼을 추가 할당하고, Stack은 기존 사이즈의 100%만큼 할당하여 Deque이 더 적은 메모리를 사용한다.

왜 xxxLast가 아닌 First를 권장하는가

• 전제 조건: 습관처럼 peek()을 쓰기가 쉽다.
• 문제 원인: peek은 First를 가리키는 것이 default이다.
• addLast, pollLast를 할 시 습관대로 peek()을 사용하면 확인하고자 하는 값이 아닌 다른 값을 조회하는 행위

removeFirst()와 pollFirst()의 차이

• removeFirst(): 만약 deque이 비어있다면 NoSuchElementException이 발생
• pollFirst(): deque이 비어있더라도 null을 반환

stack에 대응되도록 구현하려면 예외를 발생시키는 removeFirst를 사용하는 것이 바람직하다
다만 pollFirst는 예외처리를 강제하지 않기 때문에 null 체크만 해준다면 더 간결한 코드를 작성할 수 있다.

정리

stack 구현	Deque	Stack
속도	더 빠르다	더 느리다
메모리	더 적게 씀	더 많이 씀
legacy	X	O
사용 권장	O	X

출처

자바 공식 문서: https://docs.oracle.com/javase/8/docs/api/java/util/Stack.html