QnA [Java] 스택 자료구조 쓸 때 뭘 써야하는가

제목: 자바에서 스택 자료구조 쓸 때 뭘 써야하는가
질문 날짜: 2022.10.30.Sunday
태그: #Java

---

질문 내용

const solution = (str) => {
  // stack 사용
  const char = [...str];
  let stack = [];

  for (i = 0; i < char.length; i++) {
    const stackLength = stack.length;
    if (stack[stackLength - 1] === char[i]) {
      stack.pop();
    } else stack.push(char[i]);
  }
  return stack.join("");
};

에서 자바로 코드를 바꾸려고 하는데 스택을 어떻게 써야할지 모르겠다.

    public static String solution(String cryptogram) {
        // String answer = "answer";
        List<Character> chars = cryptogram
                .chars()
                .mapToObj(e -> (char) e)
                .collect(Collectors.toList());

        int charSize = chars.size();
        LinkedList<Character> linkedList = new LinkedList<>();

        for (int i = 0; i < charSize; i++) {
            char currentChar = chars.get(i);
            if (linkedList.contains(currentChar) && linkedList.getLast() == currentChar) {
                linkedList.pollLast();
            } else {
                linkedList.add(currentChar);
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        ListIterator<Character> listIterator = linkedList.listIterator();
        while (listIterator.hasNext()) {
            stringBuilder.append(listIterator.next()).append("");
        }
        return stringBuilder.toString();
    }

처음에는 LinkedList로 구현했는데 stack을 쓰는게 맞을 것 같기도 하고 deque라는 자료구조를 쓰는게 맞나.., 뭐가 왜이리 많음

질문 관련 서치 내용

Java 의 Stack 대신 Deque
Java Deque vs. Stack | Baeldung
[JAVA] Deque/ArrayDeque(데크) 개념 및 사용법 정리
[Java] 자바 Stack 클래스 사용법 & 예제 총정리

java - ArrayDeque vs ArrayList to implement a stack - Stack Overflow
performance - What is the fastest Java collection with the basic functionality of a Queue? - Stack Overflow
The main difference between both implementation is the resize strategy

ArrayList is resized to a new size of oldCapacity + (oldCapacity >> 1), resulting in an increse of ~50%. The default capacity is 10, resulting in a capacities after resize of 15, 22, 33, 49, 73, 109, 163, 244, 366...

ArrayDeque is always resized to a power of 2. On resize, the capacity is doubled. Starting with the default of 16, the resuling capacities after resize are 32, 64, 128, 256,...

So the ArrayDeque reaches higher capacities with much less resize operation, which are costly because of array copy. I.e. to store 256 in default-sized ArrayList, it requires 9 resize calls, while the ArrayDeque only need 4. Array copy may be fast, but may also require a GC to free some space for the new data sets, in addition to the memory copy costs (where the ArrayDeque might also perform better due to it's alignment to power-of-2).

Both datastructures have best-case complexity of O(1) for push and pop through direct access on either head & tail (ArrayDequeue) respectively add and remove(Last) size (ArrayList)

질문을 정리하면서 새롭게 얻은 해답이 있는가?

stack 자료형이 따로 있다는걸 처음 알았음 (자스는 걍 []로 선언함
일단 LinkedList는 아닌 것 같음

글을 읽어봤는데 나는 string으로 스택 값 읽어올 때 넣은 순서대로 읽어와야하므로 stack을 쓰는게 맞는듯 한데 또 찾아볼수록 ArrayDeque 쓰는게 더 합당한듯 (메모리, 반복순회 면에서)

추가 질문

LinkedList 는 별로인 이유

너무 느림 (생각해보니 당연함)

Deque 의 구현체는 ArrayDeque 과 LinkedList 가 있다. 둘의 차이점을 살펴보자.

ArrayDeque 은 Deque 인터페이스의 구현체이며 크기가 재설정을 할 수 있다.
LinkedList 는 List 의 구현체다.
LinkedList 는 null 요소를 추가할 수 있지만 ArrayDeque 은 불가능하다.
LinkedList 는 반복중에 현재 요소를 제거하는 것이 효율적이고, ArrayDeque 은 양쪽 끝에서 추가, 제거가 효율적이다.
LinkedList 는 ArrayDeque 보다 더 많은 메모리를 소모한다.
메모리 소모량이 적을 때는 iterate 효율이 좋은 ArrayDeque 를 사용하고 스택의 사이즈가 커지거나 심한 변동이 예상될 때는 즉각적인 메모리 공간 확보를 위해 LinkedList 를 사용한다.

자바 Stack 클래스 안쓰는 이유

질문 관련 서치내용에 있는 링크에 더 자세히 나와있는데 간단하게 더 정리
자바에 있는 Stack은 Vector에다가 스택용으로 쓸만한 메서드들 편의를 위해 넣어놓은 것
Vector는 ArrayList보다 옛날에 나온 거고 ArrayList와 다르게 멀티쓰레드 동기화가 된다.
그래서 느리다.
멀티쓰레드 환경에서 List를 공유할 필요가 있으면 Vector 쓸 일이 생길지는 모르겠지만, 암튼 잘 안씀

(관련 키워드는 나중에 찾아보기)

이펙티브자바 3판 120페이지 참고

Array, ArrayList 차이

Array vs ArrayList in Java - GeeksforGeeks → 정적배열, 동적배열
보통 동적배열 씀 (근데 가끔 정적배열 요구하는 api 있음)

큐 구현은 뭐로 함?

→ 원형 큐 (싱글쓰레드에서는)
왼쪽에서 원소를 빼면 "start = 1" 이렇게 이제 1번부터 시작이라고 기록을 함
왼쪽에 넣으면 start--인 거고 빼면 start++인 거고
배열이 원형으로 이어져있다고 생각하면 왼쪽에 접근하든 오른쪽에 접근하든 start, end 번호만 갱신하면 됨
그러다 꽉 차서 start랑 end가 만나는 일이 생기면 동적 배열마냥 배열 2배 늘리고 다시 넣음
그래서 ArrayList 확장형에 불과하기에 배열 기반이라고 ArrayDeque라고 하는 것임
근데 멀티쓰레드에서는 뭐 락 잡고 갱신하든지 LinkedList 비스무리한 거 쓰든지 함

질문 답변 (해결 방안)

동적 배열 및 스택: ArrayList
큐 연산이 필요하면: ArrayDeque

연속된 메모리에 값이 저장된다는 점 때문에 캐싱이나 분기예측 등이 잘 작동해서 배열 관련 메서드 쓰는 것이 좋다.

질문이 나왔던 이유

자스는 자료구조나 타입 선언에 대해서 딱히 신경 안써도 되는데 자바는 그렇지 않아서 헷갈린다.

새롭게 알게된 추가 개념

같은 의미로 큐는 deque의 사용성을 제한해서 만들어지는 것
원래 ArrayList든 쟈스 리스트든 동적 배열은 오른쪽에다가 원소 추가하고 빼는 건 다 지원을 함
"오른쪽에다가만 원소 접근을 하겠다" 이렇게 생각하는 방법론이 스택인 거지
근데 이제 "왼쪽에다가도 원소 추가하고 빼겠다"가 나오면 이건 ArrayDeque로 deque로의 확장이 필요한데 "오른쪽에다가만 추가하고 왼쪽에서만 빼겠다" 이렇게 제한을 걸고 쓰면 큐라고 하는 것임

---