[자료구조] 4. Java 스택 인터페이스 (Stack Interface)

Stack Interface

스택은 먼저 들어온 데이터가 마지막에 나가게 되는 후입선출(LIFO = Last In First Out) 구조를 가지는 자료구조이다. 코딩을 하다가 자주 만나게 되는 'java.lang.StackOverFlowError'가 이 스택에서 나는 것이다. 메소드를 호출할 때마다 메소드 내에 정의된 변수들의 값이 stack 메모리에 쌓이게 되는데 재귀가 깊어지면 stack 메모리에 이 값들이 쌓이면서 해당 총량이 할당된 메모리보다 커질 때 내뱉게 된다.

 

자바 내부에서는 스택은 Vector 클래스를 상속받아 사용한다. Vector는 ArrayList와 크게 다르지 않다. 내부 구조는 Object[] 배열로 데이터들을 관리하며 전체적인 메소드 구조도 많이 유사하다. 다만 차이점은 동기화를 지원 여부이다. ArrayList에서는 지원하지 않지만 Vector는 지원한다. 그래서 속도는 ArrayList가 조금 더 빠르지만, 쓰레드 안정성은 그렇지 않다. 그래서 멀티 스레드 환경에서는 Vector, 아닐경우는 ArrayList를 사용한다.

---

Stack의 활용

1. 페이지 뒤로가기

2. 실행 취소

3. 수식 괄호 검사

 

대표적으로 위 3가지를 이야기할 수 있다.

1번은 가장 최근에 방문한 페이지가 가장 상단에 위치하게 되서 뒤로가기를 누를때 마다 그보다 전에 방문했던 페이지들을 꺼내 차례대로 보게 된다. 실행 취소도 마찬가지이다. 3번의 수식 괄호 검사는 알고리즘 문제에서 스택의 활용 문제로써 단골로 등장하는 문제이다.

 

Stack Interface에 선언된 대표적인 메소드

메소드	리턴 타입	설명
push(E item)	E	스택의 맨 위에 요소를 추가한다.
pop()	E	스택의 맨 위 요소를 제거하고 제거된 요소를 반환한다.
peek()	E	스택의 맨 위 요소를 제거하지 않고 반환한다.
search(Object o)	int	스택의 상단부터 탐색하여 지정된 객체가 있는 요소의 위치를 반환한다. 없을 경우에는 -1을 반환한다.
size()	int	현재 스택에 있는 요소의 개수를 반환한다.
clear()	void	모든 요소들을 제거한다.
empty()	int	현재 스택에 요소가 존재하지 않을 경우 true, 그 외의 경우는 false를 반환한다.

스택에서의 search 메소드는 내부 배열의 인덱스 값이 아닌 스택의 상단으로부터 몇번째 위치하는지를 반환하는 것이다. 즉, 거리 개념이다. 자바 내부에서의 스택은 Vector 클래스를 상속받다보니 위의 메소드보다 훨씬 더 많은 메소드를 지원한다. 하지만 이 자료구조 구현의 목적은 자료구조 자체의 특성에 집중한 것이니 위의 메소드를 중점으로 구현할 것이다.

 

public interface StackInterface<E> {

    /**
     * 스택의 맨 위에 요소를 추가한다.
     *
     * @param item 스택에 추가할 요소
     * @return 스택에 추가된 요소
     */
    E push(E item);

    /**
     * 스택의 맨 위에 있는 요소를 제거하고 제거된 요소를 반환한다.
     *
     * @return 제거된 요소
     */
    E pop();

    /**
     * 스택의 맨 위에 있는 요소를 제거하지 않고 반환한다.
     *
     * @return 스택의 맨위에 있는 요소
     */
    E peek();

    /**
     * 스택의 상단부터 특정 요소가 몇번째 위치에 있는지 반환한다.
     * 중복되는 원소가 있을 경우 가장 위에 있는 요소의 위치가 반환된다.
     *
     * @param value 스택에서 위치를 찾을 요소
     * @return 스택의 상단부터 처음으로 요소와 일치하는 위치를 반환
     *         만약 일치하는 요소가 없다면 -1 반환.
     */
    int search(Object value);

    /**
     * 스택의 요소 개수를 반환한다.
     *
     * @return 스택에 있는 요소 개수를 반환
     */
    int size();

    /**
     *  스택에 있는 모든 요소를 삭제한다.
     */
    void clear();

    /**
     * 스택에 요소가 비어있는지를 반환한다.
     *
     * @return 스택에 요소가 없을 경우 {@code true}, 그 외의 경우 {@code false} 반환.
     */
    boolean isEmpty();

}