[Java] Stack Class

API 문서와 소스를 통해 스택 자료구조가 작성되어 있는 Stack 클래스를 분석해보도록 하겠습니다.

Java Platform SE 8

Stack 클래스의 구조

Stack 클래스란?

public class Stack<E>
extends Vector<E>

1. 스택 클래스는 객체의 LIFO 스택을 표현합니다.
2. 스택 클래스는 백터를 스택으로 취급할 수 있게 해주는 다섯 가지 작업로 백터 클래스를 확장합니다.
3. push와 pop 작업이 제공되고, 스택의 상단 요소를 찾기 위한 메서드와,
   스택이 비어있는지 확인할 수 있는 메서드, 그리고 요소를 찾을 수 있는 메서드와 상단으로부터 얼마나 떨어져 있는지 찾기 위한 메서드가 제공됩니다.
4. 더 완전하고, 일관된 LIFO 스택 작업의 set은 Deque 인터페이스와 이것을 상속함으로써 제공됩니다.
   스택 클래스에서는 Deque의 사용을 우선적으로 해야 합니다.

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

Stack의 필드와 생성자

스택 클래스는 다음과 같은 필드를 Vector클래스로부터 상속받습니다.

protected Object[] elementData;

protected int elementCount;

protected int capacityIncrement;

추가적으로 Vector클래스가 상속받는 AbstractList 클래스로부터 다음과 같은 필드도 상속받습니다.

protected transient int modCount = 0;

스택은 기본 생성자만 존재합니다.

public Stack() {
}

Stack의 메서드

상속받는 것 외에 스택이 갖는 메서드는 총 다섯 개입니다.

순서대로 살펴보도록 하겠습니다.

1. empty()

size()가 0인지를 연산하여 반환합니다.

public boolean empty() {
    return size() == 0;
}

size()는 Vector 클래스로부터 상속받고, elementCount를 반환합니다.

public synchronized int size() {
    return elementCount;
}

2. peek()

peek메서드는 스택의 요소를 제거하지 않고, 상단의 요소를 반환해주는 메서드입니다.

public synchronized E peek() {
    int     len = size();

    if (len == 0)
        throw new EmptyStackException();
    return elementAt(len - 1);
}

len 변수를 선언하여 size()로 초기화해주고, len이 0이면 예외를 던지고,

아니라면 Vector클래스의 elemnetAt(len - 1)을 호출하여 반환합니다.

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

    return elementData(index);
}

peek메서드로부터 스택의 아이템 개수인 len의 -1 값을 매개변수로 넘겨받았습니다.

인덱스가 요소의 개수보다 크거나 같지 않으면 다시 elementData(index)를 반환합니다.

Q.) peek()에서 len이 0이 아닐 경우에만 elementAt메서드가 호출되는데 아래 예외사항은 어떤 경우에 발생하는지 모르겠습니다.

protected Object[] elementData;

@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

배열 elementData의 index에 해당하는 요소를 반환합니다.

3. pop()

pop() 메서드는 스택의 상단 객체를 제거하고, 해당 삭제한 객체를 이 함수의 값으로서 반환합니다.

public synchronized E pop() {
    E       obj;
    int     len = size();

    obj = peek();
    removeElementAt(len - 1);

    return obj;
}

len 변수는 스택의 사이즈로 초기화하고, obj는 스택의 상단 요소로 초기화합니다.

 

pop메서드는 스택의 상단 요소를 제거한 후,

제거한 요소를 반환해주기 때문에 obj를 peek() 값으로 미리 초기화해줍니다.

 

그리고 removeElementAt(len - 1)을 호출합니다.

public synchronized void removeElementAt(int index) {
    modCount++;
    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);
    }
    elementCount--;
    elementData[elementCount] = null; /* to let gc do its work */
}

3개의 요소가 담긴 Stack이 있다고 가정해보겠습니다.

1. pop() 메서드가 호출이 되면 2를 index로 전달받을 것입니다.
2. int j = 3 - 2 -1; 로 초기화되어 0으로 초기화됩니다.
3. elementCount의 개수를 감소시키고, gc의 동작을 위해 elementData[elementCount]에 null을 넣어줍니다.
4. obj에 담아놨던 기존의 객체를 반환시켜줌으로써 pop의 동작을 종료합니다.

4. push(E item)

스택은 LIFO구조로서 마지막에 들어온 요소가 먼저 나가게 됩니다.

새로 추가되는 요소는 상단에 추가된다는 뜻과 같습니다.

push를 통해 스택에 새로운 요소를 추가할 수 있습니다.

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

    return item;
}

push메서드는 전달받은 요소를 Vector로부터 상속받은 addElement()에 전달하여 호출하고, 해당 요소를 반환합니다.

public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
}

private void ensureCapacityHelper(int minCapacity) {
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

ensureCapacityHelper 메소드는 Vector클래스로부터 상속받습니다.

스택의 공간을 늘려주는 로직을 수행합니다.

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

마지막 줄을 보시면, 기존 배열의 크기를 늘려 복사하여 다시 elementData에 대입해 주는 것을 볼 수 있습니다.

5. search(Object o)

public synchronized int search(Object o) {
    int i = lastIndexOf(o);

    if (i >= 0) {
        return size() - i;
    }
    return -1;
}

Search 메서드는 검색한 요소가 있으면 해당 요소의 인덱스를, 없다면 -1을 반환해줍니다.

Commnents

스택과 관련된 문제를 풀이하다, 스택 클래스가 정확히 어떻게 구성되어 있는지 궁금하여 분석해보았습니다.
상속과 구현을 이해하는 것에도 도움이 되는 것 같습니다.

 

TODO
- Vector 클래스에 대해 공부
- 동기화에 관련하여 공부