java stack 클래스와 대체해서 쓸 만한 arraydeque를 간단히 알아봅시다.

 java에는 stack 클래스가 있습니다. 스택은 마지막에 들어온 원소가 먼저 빠져나가는 것으로 유명한 자료구조입니다. 계산기 같은 것을 구현할 때 많이 쓰이기도 합니다. 백준 문제를 풀다 보면 간혹 가다 쓰일 때가 있습니다. 간단한 예제를 하나 보겠습니다.

 

---

 위 예제는 0부터 4까지의 수를 넣은 다음에, 맨 위에 있는 원소를 peek으로 가져오기만 합니다. 다음에, pop으로 맨 위에 있는 원소를 가져오면서 제거합니다.

 

 

 peek 메서드의 설명을 보면, 보다 명확합니다. 스택에서 원소를 제거하지 않고 stack의 맨 위에 있는 원소를 가져온다. 반면에 pop은 제거까지 합니다. 비어있는지 검사하기 위해서 empty를 호출했습니다. 다음에, 원소를 넣기 위해 push를 썼습니다.

 

 

 나중에 넣은 4가 먼저 빠지고, 먼저 넣은 0이 나중에 빠지게 됩니다. 그래서 이것을 그대로 써도 될 듯 하지만, 한 가지 함정이 있습니다. 이 클래스는 Vector를 상속한 클래스입니다.

 

 Stack 클래스 내부에 들어가 보면 알 수 있습니다. extends Vector. 이 Vector 클래스는 grow rate는 상당히 크지만, 거의 모든 메소드에 synchronized가 걸려 있습니다. 따라서 경합이 일어나지 않는 환경에서 활용하는 경우 쓸데 없는 락이 생성되고 해제되는 오버헤드가 들어가게 됩니다.

 

 일례로 push 메소드 안에 addElement가 있습니다. 안으로 들어가 보면 이 메서드에도 synchronized가 걸려있음을 볼 수 있습니다. 그 탓일까요? 500만개의 원소를 넣고 빼는 작업을 수행했을 뿐인데 생각보다 오랜 시간이 걸렸음을 볼 수 있습니다.

 

 

 약 300ms가 걸렸습니다.

 

---

 이것을 어떻게 바꾸면 될까요? Deque를 이용하면 됩니다. Deque는 양 끝에서 insert, delete를 매우 빠르게 수행할 수 있습니다. 고로, 한 쪽에서 insert, delete를 빠르게 하는 스택의 기능도 수행할 수 있습니다.

 

 

 위 예제와 비교하면, 바뀐 부분은 단 1줄입니다. 시간 측정을 위한 코드를 제외하고는 Stack<Integer> st = new Stack<>(); 이 부분을 Deque<Integer> st = new ArrayDeque<>(); 로 바꾼 것 뿐입니다.

 

 

 기본적으로 이 클래스는 synchronized를 걸지 않기 때문에, race condition이 걸릴 수 있는 상황에서는 안전하지 않습니다. 그런데, 그렇지 않은 경우에는 Vector를 상속받은 Stack보다 훨씬 빠르게 처리할 수 있습니다. 아까와 마찬가지로 500만개의 수를 push 한 다음에, pop하는 시간을 측정해 보겠습니다.

 

 

 180 ~ 190ms. 아까보다 1.5배 가량 빨라졌습니다. 경합이 없다면, Stack 대신에 이용할 만한 클래스라는 의미입니다. 정리하면 자바에서 스택을 쓸 때에는 경합 상태가 아니라면, Stack 대신에 ArrayDeque를 이용하면 더 빠르다는 것입니다.