[Java] 단일 스레드 환경에서는 Stack 보다 ArrayDeque ?!

 들어가기 전에

Stack 관련 Algorithm 문제를 풀던 중 SonarLint에서 아래와 같이 스택을 구현하기 위해 Stack 클래스를 사용하면 issue가 발생합니다. 아니 스택 구현은 Stack 클래스를 사용하는 게 아니었어?! 😮😮

SonarLint issue

단일 스레드 환경에서는 Stack 보다 Deque을 사용하기를 권장한다고 하여 어떤 이유에서 그런 것인지 알아보았습니다.

 

단일 스레드 환경에서 Stack 클래스의 문제점은 어떤 것이 있을까?

Stack 클래스를 뜯어보기 위해 코드를 열어보았는데, 열자마자 이런 내용이 나옵니다.

그동안 잘 모르고 쓰고 있었네요🤣🤣

Stack.java 설명

Stack 클래스는 LIFO 스택을 나타내는 데, 완전하고 일관된 LIFO 스택을 위해서는 Deque 인터페이스를 우선적으로 사용하는 것이 좋다고 합니다. 어떤 이유에서인지 좀 더 알아보겠습니다.

문제점 1. Vector 클래스 확장

위 사진을 통해 Stack 클래스는 Vector 클래스를 확장하고 있는 것을 알 수 있습니다. 그렇기에 LIFO 구조를 유지하는 것이 아니라 중간에 데이터를 삭제하거나 삽입하는 것이 가능합니다.

문제점 2. 초기 용량 설정 불가

Stack 클래스를 만들 때 초기 용량을 설정할 수 없습니다. ( ArrayDeque 은 초기 용량이 설정되어 있어요! )

문제점 3. synchronized

Stack 내부를 살펴보면 아래와 같이 거의 모든 메서드에 synchronized 가 있기 때문에 단일 스레드 환경에서는 성능이 떨어집니다.

Stack.java 내부 코드 일부

 

그런데 ArrayDeque 는 무엇일까? 🤔

This class is likely to be faster than Stack when used as a stack, and faster than LinkedList when used as a queue. 

공식 문서에 따르면 스택 구조로 사용할 때 Stack 클래스보다 빠르고, 큐 구조로 사용할 때 LinkedList 클래스보다 빠르다고 합니다. (참고로, Queue 인터페이스는 LinkedList 클래스로 구현됩니다.)

이렇듯 ArrayDeque 클래스는 LIFO 구조를 만들기 위해 적합한 클래스입니다.

그리고 ArrayDeque는 선언 시 크기는 16이며, 크기에 제한이 없습니다.

ArrayDeque 초기화

참고로, 초기 크기를 변경도 가능합니다.

ArrayDeque 크기 지정 초기화

초기 크기가 설정되어 있다는 점과 초기 크기를 지정할 수도 있다는 점도 알았는데, 초기 크기를 넘어가면 어떻게 동작하기에 용량에 제한이 없는 걸까요? 해당 내용은 아래 코드를 통해 기존 크기가 64 미만이면 약 2배, 64 이상이면 1.5배 정도 늘려준다는 것을 알 수 있습니다.

ArrayDeque 크기 변경

이렇듯 단일 스레드 환경에서 알고리즘을 풀기 때문에 스택이나 큐 구조를 만들어야 하면 ArrayDeque 클래스로 구현되는 Deque 인터페이스를 쓰는 게 더 좋다는 사실을 알았습니다. 단일 스레드 환경은 Deque! 기억해두면 좋겠죠? 😄😄

 

그래서 Deque 는 어떻게 쓰는 건데

Deque가 더 좋다는 걸 알았으니 사용법도 익히기 위해 사용법을 정리해두었습니다. 사실 제가 보려고 만들었어요 ㅎㅎ

	Frist Element (Head)		Last Element (Tail)
Insert	addFirst(e)	offerFirst(e)	addLast(e)	offerLast(e)
Remove	removeFirst()	pollFrist()	removeLast()	pollLast()
Examine	getFirst()	peekFrist()	getLast()	peekLast()

참고로, Stack이나 Queue에서 사용하는 Method도 제공이 되어서 추가한 내용을 아래 정리해두었습니다.

	Frist Element (Head)		Last Element (Tail)
Insert	addFirst(e) / push()	offerFirst(e)	addLast(e) / add(e)	offerLast(e) / offer(e)
Remove	removeFirst() / remove() / pop()	pollFrist() / poll()	removeLast()	pollLast()
Examine	getFirst() / element()	peekFrist() / peek(0	getLast()	peekLast()

 

 

🔗 참고

https://junghyungil.tistory.com/116

https://devlog-wjdrbs96.tistory.com/245​

http://yuminana.blogspot.com/2017/12/java-arraydeque.html