[java] Stack (ArrayDeque)

---

---

📌 Stack 이란?

Stack이란 LIFO(Last In First Out) 후입선출 자료구조 이다. 마지막에 추가된 요소가 가장 먼저 제거되는 방식이다. Java에서 스택을 구현할 수 있는 방법은 여러 가지가 있지만, 대표적으로 java.util.Stack 클래스와 Deque 인터페이스가 있다.

 

오늘도 역시 Java Doc 부터 확인해보자

 

오늘은 생각보다 짧다. 해석 및 요약 해보자면

• Stack 클래스는 Vector를 상속하며 LIFO 스택을 구현한다.
• push, pop, peek, isEmpty, search 등의 메서드를 제공한다.
• 하지만 Deque 인터페이스와 그 구현체(ArrayDeque 등)를 사용하는 것이 더 권장된다. Deque는 더 완전하고 일관된 스택 연산을 제공하기 때문이다.

자바 Doc에서도 ArrayDeque를 추천한다. Stack? 그만 알아보자

 

농담이고 ArrayDeque를 사용하는 이유는 뭐지? 궁금해 졌다.

---

📌 Stack < ArrayDeque ?

일단 ArrayDeque를 추천하는 이유를 GPT에게 물어봤다.

Stack은 오래된 API이고, 성능이나 설계 측면에서 비효율적일 수 있습니다.
ArrayDeque는 동기화되지 않아 성능이 뛰어나며, 유연한 큐와 스택 모두를 지원하는 현대적인 자료 구조입니다.
단일 스레드 환경에서는 ArrayDeque가 더 빠르고 메모리 효율이 좋습니다.

 

음.. Queue에서도 ArrayDeque를 추천하고, Stack도 추천하면 이러면 무지성 ArrayDeque를 사용해도 된다는 말인가?

 

직접 확인해보자.

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

public class StackTest {
    public static void main(String[] args) {
        TimeCheck timer = new TimeCheck();

        Stack<Integer> stack1 = new Stack<>();

        // 2596059708
        for(int i = 0; i < 100_000_000; i++) {
            stack1.push(i);
        }
        timer.start();

        // 1119155125
        for(int i = 0; i < 100_000_000; i++) {
            stack1.pop();
        }

        timer.stop();
        System.out.println(timer.getElapsedTimeInNano());

        Deque<Integer> stack2 = new ArrayDeque<>();

        // 2380544667
        for(int i = 0; i < 100_000_000; i++) {
            stack2.push(i);
        }

        timer.start();
        // 445408958
        for(int i = 0; i < 100_000_000; i++) {
            stack2.pop();
        }

        timer.stop();
        System.out.println(timer.getElapsedTimeInNano());

    }
}

 

실험 결과

	Stack	ArrayDeque
push	2,596,059,708	2,380,544,667
pop	1,119,155,125	445,408,958

 

push연산에서는 비슷하지만 ArrayDeque가 성능이 더 좋았고, pop에서는 2배 정도 성능이 좋았다.

 

그러면 ArrayDeque는 동기화를 하지 않아 빠르다고 치면, 동기화가 필요한 상황에서는 Stack이 더 좋은가? 

GPT에게 물어봤더니 Stack클래스의 동기화 방식은 구시대적 코드이므로 ArrayDeque와 같은 현대적이고 빠른 자료구조를 사용한뒤 Collections.synchronizedList로 동기화를 하거나 ConcurrentLinkedDeque 같은 동시성 컬렉션을 사용을 추천한다.

 

결론적으로는 Stack 보다 더 좋은 자료구조가 많다!

---

📌 메서드

Stack클래스 메서드

메서드	설명
empty()	스택이 비어있는지 확인한다
peek()	요소의 제거 없이 스택의 top을 확인한다
pop()	요소를 제거하면서 top을 반환한다.
push(E item)	스택의 top에 요소를 삽입한다.
search(Object o)	해당 요소의 위치를 반환한다. ( 1 - top , 없으면 -1 )

Vector 클래스의 메서드

메서드	설명
isEmpty()	벡터가 비어있는지 확인한다.
size()	벡터의 사이즈를 반환한다.

 

음.. Stack에도 empty()가 있고 Vector에도 isEmpty()가 있는데 왜 Stack에서 다시 만든거지? 궁금하다.

 

일단 이건 Vector클래스의 isEmpty()이다.

 

이거는 Stack클래스의 Empty()이다.

 

이유를 찾아보니 Stack 자료구조에서 전통적으로 empty가 사용되었고, 그로인해 Stack클래스에서도 Vector에 isEmpty()가 있음에도 불구하고 따로 만들었다고 한다.

 

또 나는 여기서 search메서드를 처음 봤다.

 

코드를 확인 해보니 Stack클래스에서 상속받은 Vector 클래스 메서드인 lastIndexOf 메서드를 이용해서 equals를 통해 값을 찾는다.

for문으로 반복문을 도는것으로 보아 선형의 시간복잡도를 요구 할 것 같다.

재미있게도 null도 확인하는 것을 볼 수 있다.

 

ArrayDeque에서는 search메서드가 없는 것을 확인했다. 왜지?

ArrayDeque는 간단하고 빠른 스택 및 큐 동작을 제공하기 위해 설계된 자료구조로, search()와 같은 기능을 내장하지 않았습니다. 대신 필요하다면 사용자가 직접 구현할 수 있도록 유연성을 남겨둔 것입니다. ArrayDeque는 삽입과 삭제 작업을 O(1)에 가깝게 수행하며, 성능을 우선시하는 많은 현대적인 애플리케이션에서 더 적합한 선택으로 여겨집니다.

 

GPT가 친절하게 답변해줬다 ㅎㅎ

 

ArrayDeque 스택 관련 메서드

메서드	설명
push(E e)	스택 맨 위 (Deque의 앞쪽)에 추가한다.
pop()	스택의 맨 위에 있는 요소를 제거하고 반환한다.
peek()	맨위의 있는 요소를 제거하지 않고 반환한다.
isEmpty()	스택이 비어있는지 여부를 확인한다.
size()	스택에 있는 요소의 개수를 반환한다.

 

ArrayDeque도 Stack관련 메서드가 있다.

---

🤔 느낀점

Stack 클래스보다 ArrayDeque클래스가 Stack의 구현체로 더 좋다는 것에 놀라웠다. 이제는 ArrayDeque를 많이 이용해야 겠다.