[짤막 자바 상식] Stack vs Deque - 코테에서 뭘 쓰지?

안녕하세요. 오늘은 자바에서 Stack과 Deque를 간략하게 비교할까합니다.

두 자료구조의 정의나 기초적인 동작 방식은 생략하고 바로 본론으로 들어가겠습니다.

 

 

Stack

Stack은 LIFO 구조의 자료형으로 많은 곳에서 활용됩니다. 저와 같은 주니어 레벨의 개발자한테는 무엇보다도 코딩테스트에서 직접 쓸 일이 많아 보입니다.

스택을 활용하는 프로그래머스 문제 

프로그래머스

 

 

Deque

Deque는 삽입, 삭제 방향이 정해져 있는 Stack나 Queue와 달리 양방향 삽입, 삭제가 가능한 자료구조입니다. 그래서 개발자가 사용하기에 따라서 Stack, Queue로도 사용 가능합니다. 즉, Stack을 대체해서 쓸 수 있습니다!

 

 

 

자바에서는 Stack 대신 Deque를 쓰자.

결론은 간단합니다. 왜인지는 곧 설명하도록 하겠습니다.

이는 자바 공식 문서에서도 권장하고 있는 사항입니다. 아래는 공식문서의 Stack 페이지 내용의 일부입니다.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.

해석하면 Deque 인터페이스와 그 구현체들이 더 완벽하고 일관성 있는 LIFO 스택 연산들을 제공하니까, 이거(Stack)대신 그거 쓰셈

라는 내용입니다. 일단 Deque를 추천하는 이유에 대해 구체적으로 보겠습니다.

 

 

Class VS Interface

Stack은 구체 클래스인 반면, Deque는 인터페이스입니다. Deque는 ArrayDeque, LinkendList, LinkedBlockingDeque 등 여러 구현체가 있습니다. 즉, Stack은 상황에 따라 구현체를 교체할 수 있는 Deque에 비해 유연성이 떨어집니다.

 

 

Vector 상속

Stack은 Vector를 상속받고 있습니다. 여기서 2가지 문제가 있다고들 합니다.

1. Synchronized 메서드

Stack 뿐만 아니라 Vector의 내부 구현을 보면 동기화(synchronized) 메서드로 Thread-safe하게 설계 돼 있습니다. Stack이 공유 데이터가 되는 상황에서는 데이터 일관성을 지킬 수 있겠지만, 경쟁 상황이 없는 단일 스레드에서는 lock 획득과 해제는 불필요한 오버헤드입니다. 또한, Blocking으로 데이터 정합성을 지키길 바란다면 java.util.concurrent 패키지의 LinkedBlockingDeque을 쓰면 됩니다.

 

 

2. Stack이 Vector인가?

약간은 애매한 이유인데요, 스택 오버플로우의 개발자들에 의하면 Stack이 Vector의 서브클래스이지만 과연 Vector를 대변할 수 있는가?에 대한 의문입니다. 즉, 바람직하지 않은 상속 관계에 있다고 생각하는 것입니다. 일례로, Stack은 Vector의 서브클래스이기 때문에 인덱스 접근이 가능합니다. 우리가 생각하는 일반적인 스택의 정의와는 약간 다르죠.

 

 

그럼 코테에서는 뭐 쓸까?

사실 제가 이 글을 쓰는 목적입니다. 코테에 자주 쓰이는 플랫폼인 프로그래머스에서 성능 측정을 해봤습니다.(코드는 짜기 귀찮아서 GPT 행님이 짜줬습니다.) 프로그래머스는 컴파일에 OpenJDK 14.0.2를 사용합니다.

import java.util.*;
import java.util.concurrent.*;

class Solution {
    public String solution(String s) {
        
       final int ITERATIONS = 10_000_000; // 요소의 개수

        // Stack 테스트
        long startTime = System.nanoTime();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < ITERATIONS; i++) {
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            stack.pop();
        }
        long endTime = System.nanoTime();
        long durationStack = TimeUnit.NANOSECONDS.toMillis(endTime - startTime);
        System.out.println("Stack: " + durationStack + " ms");

        // ArrayDeque 테스트
        startTime = System.nanoTime();
        Deque<Integer> arrayDeque = new ArrayDeque<>();
        for (int i = 0; i < ITERATIONS; i++) {
            arrayDeque.push(i);
        }
        while (!arrayDeque.isEmpty()) {
            arrayDeque.pop();
        }
        endTime = System.nanoTime();
        long durationArrayDeque = TimeUnit.NANOSECONDS.toMillis(endTime - startTime);
        System.out.println("ArrayDeque: " + durationArrayDeque + " ms");

        // LinkedBlockingDeque 테스트
        startTime = System.nanoTime();
        LinkedBlockingDeque<Integer> linkedBlockingDeque = new LinkedBlockingDeque<>();
        for (int i = 0; i < ITERATIONS; i++) {
            linkedBlockingDeque.push(i);
        }
        while (!linkedBlockingDeque.isEmpty()) {
            linkedBlockingDeque.pop();
        }
        endTime = System.nanoTime();
        long durationLinkedBlockingDeque = TimeUnit.NANOSECONDS.toMillis(endTime - startTime);
        System.out.println("LinkedBlockingDeque: " + durationLinkedBlockingDeque + " ms");
        
        return s;
    }
}

 

실행 결과는 다음과 같습니다.

결과는 예상과는 반대로 Stack이 제일 빨랐습니다. 프로그래머스에서 코테를 본다면 Stack이 가장 좋은 선택지라고 여겨집니다.(Vector로 사용하지만 않는다면)

 

그럼 리트코드(OpenJDK 21)와 제 맥북(Zulu JDK 17)에서는 어떨까요?

리트코드 측정 결과

내 맥북에서 측정 결과

둘 다 ArrayDeque가 제일 빨랐습니다. 그와 별개로 LinkedBlockingDeque는 데이터가 많은 상황에서는 최적화가 잘되어 있지 않나봅니다. 흠.. 개인적으로는 프로그래머스가 JDK 버전을 올리거나 구현체를 바꾸는 것도 좋을 것 같습니다.(물론 14를 채택한 내부 사정이 있었겠지만요) 동기화 메서드가 있는 Stack이 더 빠르다는 것은 프로그래머스가 사용하는 JDK의 ArrayDeque에 문제가 있거나 확률은 낮지만 프로그래머스의 Stack에는 동기화가 없을 수도? 있을것 같습니다.

 

 어쨌든 프로그래머스에서는 많이 성능차이가 나지는 않으니 Stack과 ArrayDeque 둘 다 사용해도 상관없을 것 같네요. 비교적 많은 수의 데이터에도 그렇게 차이가 크지 않은걸 보면 보면요. (리트코드에서는 2배에서 1.1배로 들쭉 날쭉하긴 했지만 ArrayDeque가 항상 더 빨랐습니다.)

 

 

결론

프로그래머스에서 코테를 볼 때: Stack이 약간 더 빠르지만 차이가 크지 않으므로 쓰고 싶은거 쓰자.

그 외: 무적권 ArrayDeque를 사용하자.

 

 

 

참고

스택오버플로우

공식문서 Stack

공식문서 Deque(Stack 및 Queue로 사용할 수 있는 방법 설명이 있음, 원하면 보세용)

ArrayList와 Vector의 차이(쓰레드 세이프 관련)