[JAVA] 스택(Stack)

Goal

- 스택(Stack)의 각 함수의 시간복잡도를 구할 수 있다.
- 자바로 스택(Stack)을 구현할 수 있다.

스택(Stack)의 개념

LIFO(Last in First Out) 구조의 선형 자료구조

즉, 가장 최근에 넣은 데이터만 pop()을 통해서 뽑아낼 수 있다.

스택(Stack)의 함수

push()

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

        return item;
    }

자바 라이브러리에서 구현한 함수를 봤을때,

우선 Generic을 사용해서 여러 자료형의 Data 혹은 객체가 Stack에 들어올 수 있게 해주었고,

부모 클래스인 Vector에 있는 addElement를 통해서 데이터를 push하고 있는 것을 알 수 있다.

단순 데이터를 맨마지막에 집어넣는 작업이므로, 시간 복잡도 O(1)

peek()

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

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

맨 마지막에 넣은 데이터를 삭제하지 않고 가져온다.

syncronized 즉, 동기화 되어있는데,

이는 Stack과 Vector클래스를 지금 잘 사용하지 않는 이유를 잘 설명한다.

보통 동기화는 전체 작업의 순서를 통제하기 위하여 쓰지,

위와 같이 개별 작업의 순서를 통제하기 위하여 쓰지는 않는다.

이와 같이 개별 작업의 순서를 동기화 하는 경우,

lock에 걸릴 위험에 덜 안전할 뿐더러, 개별로 동기화되기 때문에 속도도 더 느리기 때문에 지금은 Stack과 Vector를 잘 사용하지 않는다.

참고: https://stackoverflow.com/questions/1386275/why-is-java-vector-and-stack-class-considered-obsolete-or-deprecated

pop()

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

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

        return obj;
    }

마지막에 넣은 데이터를 삭제하고 return 해준다.

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 */
}

Vetor클래스의 removeElementAt() 함수이다.

단지 배열의 한 인덱스를 null값으로 바꾸어주는 작업이기 때문에 상수 시간이 걸린다.

즉, pop()은 O(1)의 시간 복잡도를 가진다.

empty(), size()

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

size()가 0인 경우 true, 그렇지 않은 경우 false를 반환한다.

protected int elementCount;

public synchronized int size() {
    return elementCount;
}

Vector의 size() 함수이다.

Vector는 내부 요소의 개수를 elementCount를 통해서

요소가 들어올 때 더해주고, 삭제될 때 빼주고 하는 작업을 해주기 때문에,

배열의 size를 알려주는 size() 함수,empty() 함수의 시간 복잡도도 O(1)이다.

마치며,

자바 라이브러리를 보며, 실제로 어떻게 구현되어있는지 알아보았고,

각 함수의 시간복잡도를 알아보았다.

Stack의 함수들은 모두 O(1)의 시간복잡도를 가지기 때문에 사실 알고리즘 문제를 풀 때는 안심하고 쓰는 편이었는데,

최근에 잘 쓰지 않는다는 말에 조금 놀랐다.

다시 한번 느끼지만 깊이 있는 개발에 대한 공부는 더욱 중요한 것 같다.
무작정 만들고 구현되어서 좋아하는게 아니라,
어떤 코드가 더 효율적이고, 이 코드는 어떻게 돌아가고,
자바 라이브러리에선 어떻게 구현되어있는지 하나하나 알고 구현할 필요성을 다시 한번 알아가는 것 같다.

김베어의 개발일지