Java.util.List Interface(3) Stack

이번엔 List의 구현체중 Stack에 대해 기록하려 합니다.

 

정확하게 Stack 은 Vactor를 상속받은 구현체입니다. 하지만 stack에서 제공해주는 대부분의 기능은 거의 대부분 vector의 기능을 사용하고 있습니다.

 

먼저 일반적인 자료구조의 스텍을 먼저 살펴보면 가장 나중에 들어간 데이터가 가장 먼저 나오게되는 LIFO(Last In First Out)의 특징을 가지고 있습니다. 데이터를 넣는 과정을 push라고 칭하며 데이터를 빼는 작업을 pop이라고 부르게 됩니다.

 

그렇다면 이제 Stack을 사용할때 주로 사용하는 기능들을 살펴보겠습니다.

 

1. push

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

//아래부턴 Vector내부
public synchronized void addElement(E obj) {
    ++this.modCount;
    this.add(obj, this.elementData, this.elementCount);
}

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

    elementData[s] = e;
    this.elementCount = s + 1;
}

private Object[] grow() {
    return this.grow(this.elementCount + 1);
}

private Object[] grow(int minCapacity) {
    return this.elementData = Arrays.copyOf(this.elementData, this.newCapacity(minCapacity));
}

private int newCapacity(int minCapacity) {
    int oldCapacity = this.elementData.length;
    int newCapacity = oldCapacity + (this.capacityIncrement > 0 ? this.capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity <= 0) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        } else {
            return minCapacity;
        }
    } else {
        return newCapacity - 2147483639 <= 0 ? newCapacity : hugeCapacity(minCapacity);
    }
}

push의 특이한 점이 있다면 add연산된 값을 리턴값으로 다시 받을수 있는점과, 내부적으로 백터 상속받아 Vector의 기능을 사용하면서 synchronized를 사용하게 되고, 객체에 Lock을 거는 단계가 추가됩니다. 아래부분은 비교적 비슷하나 특성 사이즈가 되었을때 grow하는 규칙이 달라지게 됩니다. 먼저 this.capacityIncrement의 값은 초기 vector생성시 선언해주는 값으로 별도의 선언이 없으면 0이됩니다.  즉 Stack은 Default로 Vector의 선언 사이즈 10의 사이즈를 가지고 시작합니다.

//10을 넘겨주고
public Vector() {
    this(10);
}

// 기본사이즈 10, capacityIncrement 0 을 넘겨주고
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

//객체 생성
public Vector(int initialCapacity, int capacityIncrement) {
    if (initialCapacity < 0) {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    } else {
        this.elementData = new Object[initialCapacity];
        this.capacityIncrement = capacityIncrement;
    }
}

 

 

2. Pop, peak()

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

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

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

E elementData(int index) {
    return this.elementData[index];
}

public synchronized void removeElementAt(int index) {
    if (index >= this.elementCount) {
        throw new ArrayIndexOutOfBoundsException(index + " >= " + this.elementCount);
    } else if (index < 0) {
        throw new ArrayIndexOutOfBoundsException(index);
    } else {
        int j = this.elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(this.elementData, index + 1, this.elementData, index, j);
        }

        ++this.modCount;
        --this.elementCount;
        this.elementData[this.elementCount] = null;
    }
}

먼저 두개의 기능의 차이점을 말하자면 pop은 array에서 값을 하나 제거하며, peak는 제거하지않고 맨 마지막에 insert된 값을 반환해줍니다. 그리고 둘다 size가 0인 상태에서 반환 요청을 하는경우 EmptyStackException() 을 뱉어내게 됩니다.

 

peak부터 살펴보면 len-1( 최고 높은 인덱스) 를 반환하는 로직을 통해 마지막 값을 받아옵니다.

 

pop의 경우, peak을 통하여 리턴할 object를 받아오고, 해당 인덱스를 null처리하게 됩니다. removeElementAt의 경우 stack에서는 j는 0이 뜨게 됩니다.

 

3. empty

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

해당 함수의 경우 size가 0일 경우에 true, 아닌경우 false를 뱉어줍니다.

 

 

4. search

public synchronized int search(Object o) {
    int i = this.lastIndexOf(o);
    return i >= 0 ? this.size() - i : -1;
}

public synchronized int lastIndexOf(Object o) {
    return this.lastIndexOf(o, this.elementCount - 1);
}

public synchronized int lastIndexOf(Object o, int index) {
    if (index >= this.elementCount) {
        throw new IndexOutOfBoundsException(index + " >= " + this.elementCount);
    } else {
        int i;
        if (o == null) {
            for(i = index; i >= 0; --i) {
                if (this.elementData[i] == null) {
                    return i;
                }
            }
        } else {
            for(i = index; i >= 0; --i) {
                if (o.equals(this.elementData[i])) {
                    return i;
                }
            }
        }

        return -1;
    }
}

해당 함수는 인덱스를 반환받게 됩니다.

먼저 찾고자 하는 index를 search(Object o) 함수에 전달하게됩니다. 그다음 스텍의 특성에 맞게 인덱스가 큰 순에서 역순으로 검색을 해나가며 해당 object와 같은 값을 가지는 경우, index를 반환해줍니다.

만약 찾지 못한 경우, return -1을 반환받게됩니다.

 

간단하게 stack에서 사용하는 함수, pop, push, peak, empty, search에 대해 정리하는 시간이였습니다.