Stack - 자바 코드 뜯어보기

Stack은 LIFO 구조로 구현된 자료구조이다. 

 

여기서 LIFO(Last In First Out)란,

마지막으로 들어온 데이터가 가장 먼저 반환된다는 의미다.

 

실생활에서 우리는 LIFO를 책을 쌓아놓은 것으로 예를 들 수 있다.

책을 눕혀서 차곡차곡 쌓아놓으면, 가장 처음 쌓은 책은 가장 마지막에,

가장 마지막에 올려둔 책은 가장 먼저 꺼낼 수 있다. 

 

이것을 후입선출, LIFO 라고 한다. 

 

시작하기에 앞서, 자바에서는 Stack보다는 이후에 나온 Deque 구현체의 사용을 권장한다.

Deque는 LIFO,FIFO를 모두 지원하는 자료구조이다.

 

1. 상속

이제 자바의 Stack을 뜯어보자. Stack은 Vector라는 구현체를 상속하고있다.

public class Stack<E> extends Vector<E> {}

 

 Vector란 ArrayList와 유사하게 배열의 크기를 조절하는 자료구조로, ArrayList 이전에 구현된 자료구조이다.

이 둘은 기능적으로는 유사한점이 많지만, Vector는 다중 스레드에, ArrayList는 단일 스레드에 적합하다.

 

2. 삽입

먼저 삽입을 알아보자. 

Stack

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

 

Vector

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

private void add(E e, Object[] elementData, int s) {  
    if (s == elementData.length)  
        elementData = grow();  
    elementData[s] = e;  
    elementCount = s + 1;  
}

 

Vector의 add 메서드를 살펴보는데 궁금한점이 생겼다.

우리는 보통 List같은 자료구조로 데이터를 저장할 때 제네릭 타입을 이용해서 한가지 타입으로만 저장한다.

 

여기서 제네릭이란, <> 를 의미하며, 컴파일 시 타입을 체크해준다.

아래 예제에서는 <Integer>가 제네릭이며, Integer를 제네릭타입으로 지정한것이다.

List<Integer> numbers = new ArrayList<>();

 

근데 Vector의 맴버인스턴스를 확인해보면 배열의 타입이 Object로 되어있다.

public class Vector<E>  
    extends AbstractList<E>  
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable  
{  
    /**  
     * The array buffer into which the components of the vector are     * stored. The capacity of the vector is the length of this array buffer,     * and is at least large enough to contain all the vector's elements.     *     * <p>Any array elements following the last element in the Vector are null.  
     *     * @serial  
     */  
    @SuppressWarnings("serial") // Conditionally serializable  
    protected Object[] elementData;  
  
    /**  
     * The number of valid components in this {@code Vector} object.  
     * Components {@code elementData[0]} through  
     * {@code elementData[elementCount-1]} are the actual items.  
     *     * @serial  
     */  
    protected int elementCount;  
  
    /**  
     * The amount by which the capacity of the vector is automatically     * incremented when its size becomes greater than its capacity.  If     * the capacity increment is less than or equal to zero, the capacity     * of the vector is doubled each time it needs to grow.     *     * @serial  
     */  
    protected int capacityIncrement;
    
    ...

 

즉, 제네릭으로 타입체크를 한 후 자료구조에 저장을 하면

타입이 제네릭 타입으로 저장되는게 아니라, 

Object로 저장되는 것이다.

 

3. 반환

Stack

public synchronized E pop() {  
    E obj;  
    int len = size();  
  
    obj = peek();  
    removeElementAt(len - 1);  
  
    return obj;  
}

public synchronized E peek() {  
    int     len = size();  
  
    if (len == 0)  
        throw new EmptyStackException();  
    return elementAt(len - 1);  
}

 

 

여기서 elementCount는 요소의 수량을 반환하는것 같고, elementAt은 해당 인덱스의 값을 반환하는것 같다.

removeElementAt은 지정한 요소를 제거하는것 같은데, 로직이 뭔가 많다.

여기서 j는 뭘 의미하고, System.arraycopy는 무엇일까?

Vector

public synchronized int size() {  
    return elementCount;  
}

public synchronized void removeElementAt(int index) {  
    if (index >= elementCount) {  
        throw new ArrayIndexOutOfBoundsException(index + " >= " +  
                                                 elementCount);  
    }  
    else if (index < 0) {  
        throw new ArrayIndexOutOfBoundsException(index);  
    }  
    int j = elementCount - index - 1;  
    if (j > 0) {  
        System.arraycopy(elementData, index + 1, elementData, index, j);  
    }  
    modCount++;  
    elementCount--;  
    elementData[elementCount] = null; /* to let gc do its work */  
}

public synchronized E elementAt(int index) {  
    if (index >= elementCount) {  
        throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);  
    }  
  
    return elementData(index);  
}

 

j가 무엇인지 알려면, 일단 System.arraycopy가 어떤 역할을 하는지부터 알아야 한다.

이름을 보면 배열을 복사한다는것같은데, 파라미터는 또 왜이리 많은가?

 

코드를 뜯어보면 다음처럼 구성되어있다.

여기서 native 라는 선언은, 자바 코드가 아닌, c나 c++같은 로우레벨 언어로 구현된 메서드라는 의미이다.

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

 

Object src : 원본 배열
int srcPost :  복사를 시작할 첫번째 인덱스
Obejct dest : 목적 배열
destPos : 목적배열에서 복사한 값을 할당할 첫번재 인덱스
length : 복사할 배열 요소의 수

 

실제로 적용해보면 다음과 같다.
정말 단순히 배열값을 복사하는 메서드이다.

String[] src = {"a","b","c","d","e"};  
String[] dest = new String[5];  
System.arraycopy(src,2,dest,0,3);  
  
for (String s : dest) {  
    System.out.print(s + " ");  
}

---
c d e null null

 

이번엔 src와 dest에 모두에 src를 넣고 실행해보자.
1인덱스 요소부터 3개의 요소를 원본의 맨 처음 부분부터 할당한다.

String[] arr = {"a","b","c","d","e"};  
System.arraycopy(arr,1,arr,0,3);  
for (String s : arr) {  
    System.out.print(s + " ");  
}

---
b c d d e

 

b c d d e 가 된 이유는
원본 배열에 붙여 넣었으므로,

원본배열 : [a,b,c,d,e]
복사 요소 : b,c,d
배열 할당 : [b,c,d,d,e]

순서로 할당되기 때문이다.

 

이번엔 하나의 값만을 제거한 후 배열을 앞으로 당기는 예를 보자.

String[] arr = {"a","b","c","d","e"};  
System.arraycopy(arr,1,arr,0,4);  
arr[arr.length-1] = null;  
for (String s : arr) {  
    System.out.print(s + " ");  
}

---
b c d e null

 

이제 다시 벡터의 removeElement 메서드를 보면 이해가 좀더 쉽다.

 

이제 우리는 j가 삭제한 요소 뒤에 존재하는 요소들의 수량이라는것을 알았고,

 

System.arraycopy는 지정한 배열 요소를 복사하는 기능이며

상황에 따라 같은 배열의 값을 제거하고, 앞으로 당기는 역할을 할 수 있다는것을 알았다.

 

전체적인 로직은 이렇다.

삭제하고자 하는 배열의 인덱스가 마지막이면 바로 마지막 인덱스를 null 처리한다.
그렇지 않다면, arraycopy를 이용해 값을 제거하고 마지막의 불필요한 배열을 null처리한다.

 

왜 JVM의 스택 영역은 LIFO인것일까?

왜 스택 영역은 LIFO인가?

그전에, LIFO,FIFO의 차이는 뭘까?

처음엔 단순히 LIFO,FIFO의 차이는 '첫번째들어간 데이터가 나오는 순서의 차이' 로만 이해했지만,

지금은 LIFO,FIFO의 차이는 '데이터의 실행 시점의 차이'에 있다고 생각한다.

 

LIFO는 마지막 데이터가 가장 마지막으로 조회되지만, 가장 먼저 실행된다.
하지만 FIFO는 첫번째 데이터가 가장 먼저 실행된다.
즉, 조회는 동일하지만, 실행 시점에 있어서 차이가 있다는 의미다.

 

스택 영역은 메모리 호출 순서를 관리하는 곳인데,
말 그대로 Stack, LIFO로 구현된다.
그럼 왜 스택영역은 FIFO로 구현되면 안될까?

답은 간단했다. FIFO는 첫번째 실행된 메서드가 가장먼저 연산되어야 한다. 하지만 재귀같은 내부에 다른 메서드가 포함되어있는 메서드의 경우에는 어떤가? 첫번째 메서드가 실행이 완료되기전에 내부 메서드의 연산이 종료되고, 이후에 그 연산값을 이용해 첫번째 메서드가 연산을 완료한다.

즉, FIFO로 메모리 호출이 구현된다면
첫번째 메서드가 실행되면서 두번째 메서드를 실행하고, 첫번째 메서드는 연산을 기다린다. 하지만, 두번째 메서드는 실행되지 않는다. 왜냐?  첫번째 메서드가 종료되지 않았으니까!

하지만 LIFO는 조금 다르다
첫번째 메서드가 실행되면, 내부에서는 또 메서드를 실행한다.

그리고 가장 마지막 메서드의 연산값, 즉 마지막 메서드가 종료되면, 그 이전 메서드가 실행되게 된다.