Stack이란?

Stack은 사전 정의 그대로 "쌓다"라는 뜻을 가지고 있다. 즉, 접시에 음식을 쌓아 올리듯 데이터를 차곡차곡 쌓아올리는 것을 말한다.
이렇게 아래 그림과 같이 스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는데 이러한 자료 구조를 LIFO구조라고 한다.

Java의 Stack이란?

java의 stack class는 vactor class를 상속 받고 있으므로 Thread-Safe하다는 특징이 있다.

추가로 java로 stack을 구현할경우 java.util.stack을 사용하여 구현 해도 되지만 Java의 Stack 구현체인 Vector는 동기화된 메서드로 구현되어 있어 멀티 쓰레드 환경에 안전하게 구현되어 있기 때문에 단일 쓰레드 환경에서는 성능상 불리하다.
한 예로 아래 Stack Class의 push 메서드의 구현체를 보면 synchronized가 붙어 있다.

• stack.push()

    public E push(E item) {
        addElement(item);

        return item;
    }

• stack.push()의 구현체 addElement()

public synchronized void addElement(E obj) {
        modCount++;
        add(obj, elementData, elementCount);
    }
    

Java 공식문서에서도 스택을 Stack Class보다 Deque Class를 사용하라고 권장하고 있다.

정리하자면 나는 취준 코테를 준비하므로 java.util.stack class를 이용할 생각이다.
코딩테스트 풀이 예시들을 보면 대부분 Stack 클래스를 활용해 구현하는 경우가 많다. 다만, 시간 제한이나 성능이 중요한 문제에서는 Deque를 스택처럼 활용하는 것이 더 효율적인 선택이 될 수 있다.

Java로 구현해보기

package stack;

import java.util.ArrayDeque;
import java.util.Deque;

public class Stack {
    public static void main(String[] args) {
        //stack 생성
        java.util.Stack<String> stack = new java.util.Stack<>();
        stack.push("A");
        stack.push("B");
        stack.push("C");

        // 1. push() : 데이터 삽입
        System.out.println("push 후 stack: "+stack);

        // 2. peek() : 최상단 원소 확인 (삭제 안 됨)
        System.out.println("peek(): " + stack.peek());
        System.out.println("peek 후 stack: " + stack);

        // 3. pop() : 최상단 원소 꺼내기
        System.out.println("pop(): " + stack.pop());
        System.out.println("pop 후 stack: " + stack);

        //4. 성능 측정 테스트
        runBenchmark();


    }

    /**
     * 2. Stack vs Deque 성능 비교 메서드
     */
    private static void runBenchmark() {
        System.out.println("\n=== Stack vs Deque 성능 비교 ===");
        for (int n = 1; n <= 1_000_000; n *= 10) {
            long stackTime = benchmarkStack(n);
            long dequeTime = benchmarkDeque(n);

            System.out.printf("[N=%d] Stack: %.3f ms | Deque: %.3f ms%n",
                    n, stackTime / 1_000_000.0, dequeTime / 1_000_000.0);
        }
    }

    /**
     *  Stack 성능 측정
     */
    private static long benchmarkStack(int n) {
        java.util.Stack<Integer> stack = new java.util.Stack<>();
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) stack.push(i);
        for (int i = 0; i < n; i++) stack.pop();
        return System.nanoTime() - start;
    }

    /**
     *  Deque 성능 측정
     */
    private static long benchmarkDeque(int n) {
        Deque<Integer> deque = new ArrayDeque<>();
        long start = System.nanoTime();
        for (int i = 0; i < n; i++) deque.push(i);
        for (int i = 0; i < n; i++) deque.pop();
        return System.nanoTime() - start;
    }
}

실행결과:

push 후 stack: [A, B, C]
peek(): C
peek 후 stack: [A, B, C]
pop(): C
pop 후 stack: [A, B]

=== Stack vs Deque 성능 비교 ===
[N=1] Stack: 0.008 ms | Deque: 0.006 ms
[N=10] Stack: 0.005 ms | Deque: 0.004 ms
[N=100] Stack: 0.037 ms | Deque: 0.027 ms
[N=1000] Stack: 0.308 ms | Deque: 0.343 ms
[N=10000] Stack: 0.579 ms | Deque: 0.635 ms
[N=100000] Stack: 3.794 ms | Deque: 2.663 ms
[N=1000000] Stack: 21.302 ms | Deque: 19.855 ms

Process finished with exit code 0

전체적으로 Deque를 활용한 스택 구현이 Stack 클래스보다 성능 면에서 우위를 보였다. 따라서 코딩테스트에서는 큰 차이가 없을 수 있지만, 실제 프로젝트 환경에서는 Deque를 사용하는 것이 더 바람직한 것 같다.