[2022-1-4] Stack<E> 뜯어보기

오늘 프로그래머스에서 푼 크레인 인형뽑기 게임 은 Stack을 쓰면 매우 쉽게 풀리는 문제였다. Stack 객체를 생성하여 풀었는데 Stack의 개념은 학교에서 배워서 알고있었지만 c언어로만 구현해 봤을 뿐 자바에서 사용해본 것은 처음이라 이번에 사용하면서 Stack 클래스가 어떻게 동작하는지 알아봤다.(문제 풀이는 하단에)

 

Stack 클래스는 Vector클래스를 상속받는다.

 

Vector 의 상속을 받는 Stack

Vector 클래스에서 protected Object[] elementData 로 선언된 객체 배열에 데이터를 저장하게 된다. 처음 Vector를 봤을 때 이게 도대체 뭔가했더니 그냥 배열이었다. elementCount는 배열에 추가된 객체의 개수이고 capacityIncrement 는 배열이 꽉 찼을 때 더해주는 크기이다.

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

때문에 이와같이 stack 인스턴스를 생성하면 부모 클래스인 Vector 클래스의 생성자가 다음과 같이 호출된다.

 

this() 를 통해 결국 initialCapacity 는 10, capacityIncrement 는 0 으로 초기화 된다.  stack.push()를 통해 스택에 값을 계속 추가하면 아래 이미지처럼 Vector에 구현된 addElement(), add() 메서드가호출되며 값을 추가하고 elementCount를 1늘려준다.

 

Stack 클래스의 push() / Vector 클래스의 addElement() / Vector 클래스에 add()

Vector 클래스의 add() 메서드에서 elementData.length == s 일 때, 즉 배열이 꽉 찼을때 grow() 메소드를 통해 배열을 확장해준다.

 

Vector 클래스 grow()&amp;amp;amp;nbsp;

grow() 메소드에서는 elementCount + 1 만큼을 newCapcity 에 넣어주고 Arrays.copyOf 메소드를 통해 기존 배열을 더큰 크기의 배열로 복사하여 재할당 한다.

 

Vector 클래스 newCapacity()&amp;amp;amp;nbsp;

그런데 newCapcity 메소드를 보면 Vector() 생성자가 호출될 때 capacityIncrement 를 0으로 초기화 해줬기 때문에

변수 newCapacity 는 항상 oldCapacity + oldCapacity 가 되고, 그러면 이는 원래 배열의 크기에 두배가 되기 때문에 배열이 꽉찰 때마다 현재 배열 크기의 두배로 복사되는 것 처럼 보였다. 그래서 직접 테스트를 해보았는데 아래 이미지처럼 정말 배열의 용량이 꽉찰 때 마다 현재 크기의 두배로 늘어났다.

 

Vector 의 배열 크기가 변할 때마다 배열 크기 capacity를 출력

이렇게 되면 Vector로 객체를 생성할 때는 배열크기 증가값을 설정해 줄 수 있지만 Stack 객체를 생성해줄 때는 자동으로 배열의 크기는 두배씩 증가 할 수 밖에 없다.

 

Vector는 capacityIncrement , 설정가능 Stack 은 불가

왜 Stack은 capacityIncrement 를 설정할 수 없도록 구현 됐는지 이유가 궁금하다.

 

--> 이에 대한 답은 다음에서 찾을 수 있었다.

https://stackoverflow.com/questions/10419250/why-double-stack-capacity-instead-of-just-increasing-it-by-fixed-amount

Why double stack capacity instead of just increasing it by fixed amount?

크기 100의 배열이 꽉찼다면 충분히 200, 300 크기의 배열용량이 필요할 수 있고 capacityIncrement 가 10으로 고정되어있다면 110, 120, 130 이렇게 배열을 계속 새로 만드는 것보다 기존 크기의 두배로 해주는 것이 훨씬 성능적으로 이득이라는 것이다. 그리고 만약 배열의 크기를 예측할 수 있는 상황이라면 Stack을 스스로 구현하여 최적화된 capacityIncrement 를 설정해줌으로써 성능을 향상 시킬 수있다고 한다.

 

어쨌든 이런식으로 새로 만들어줄 배열의 크기를 얻고, 기존배열과 함께 Arrays.copyOf() 의 파라미터로 넘겨주어 복사된 새로운크기의 배열을 elementData 에 할당한다. Arrays.copyOf() 메소드의 구현은 다음과 같다.

 

Arrays 에 정의된 copyOf()

결국 System.arraycopy() 메소드를 통해 기존 배열이 복사된 newLength 크기의 새로운 배열을 만들고 이를 반환해준다. 이 과정을 끝으로 Stack 클래스에서 push() 메소드를 통해 데이터가 배열에 저장된다.

 

결론 및 느낀점

처음에는 자바가 구현해 놓은 Stack 클래스가 어떻게 작동하는지(배열로 구현됐는지 연결리스트로 구현됐는지) 알고싶어서 코드를 보기 시작했는데 보다보니까 길어져서 여기까지 왔다.

 

아직 공부 못해본 부분이 많아서(특히 제네릭) 이해 안가는 부분도 많았지만, 처음으로 자바에서 구현해본 어떤 클래스에 대해서 이렇게 깊게 공부해보면서 내가 사용하는 코드가 어떻게 동작하는지 아는게 정말 중요하다는 것을 느꼈다. 또한 공부하면서 이건 왜이렇고 저건 왜저렇게 될까를 고민하고 그에대한 답을 얻어내는 과정이 재밌었다. 오늘도 공부하면서 역시 공부할게 너무 많다는 것을 느꼈지만 새로 알게되고 느낀점이 많아서 뿌듯한 마음이 더 크다. 내일도 화이팅!!!!!!

 

스택을 활용한 프로그래머스 문제 및 풀이

import java.util.Stack;

class Solution {
    public int solution(int[][] board, int[] moves) {

        Stack<Integer> basket = new Stack<Integer>();
        int answer = 0;

        for(int move : moves){
            for(int[] row : board){
                if(row[move - 1] != 0){
                    if(basket.empty() || basket.peek() != row[move-1]){
                        basket.push(row[move - 1]);
                    }
                    else {
                        basket.pop();
                        answer += 2;
                    }
                    row[move - 1] = 0;
                    break;
                }
            }
        }

        return answer;
    }
}