티스토리 뷰

자료구조

[JAVA] Stack 직접 구현하기

최진영 2021. 4. 16. 13:36

Stack 이란

 Stack, 우리는 스택이라는 용어를 쌓여가는 것에 사용한다. 1스택, 2스택 .... . 즉, Stack은 데이터가 쌓여가는 것을 나타내는 자료구조로 생각하면 편한다. Stack을 이야기할 때 항상 따라서 나오는 용어는 LIFO(Last In First Out)이다. (FILO(First In Last Out) 선입후출로 표현하기도 하는데 여기서는 후입선출로 통일하여 이야기 할 것이다.)

Last In First Out

후입 선출

먼저 나온 것이 먼저 나온다.

 Stack은 데이터를 쌓아가면서 가장 마지막에 넣은 데이터를 먼저 꺼내는 형태의 자료구조를 말한다.

stack의 기본 구조이다.

 개념 자체는 매우 단순하다 먼저 넣을수록 밑으로 쌓여가고 빼낼때는 가장 최근에 넣은 값을 빼는 것, 예로 들면 웹페이지의 뒤로가기 버튼이 있다. 뒤로가기 버튼은 가장 최근의 웹페이지 기록부터 쌓여 이전 페이지로 넘어가주는 역할을 해주는 것이다.

 

Stack의 상속

 일단 우리는 Collection Framework 중 List Interface를 두 개나 알아봤다. ArrayList, LinkedList를 직접 구현해봤었는데 Stack 또한 마찬가지로 List 인터페이스에 속하는 컬랙션 클래스이다. 간단하게 잠시 Collection Framework의 구조를 알아보면

Collection Framework 기본구조

와 같은 형태로 List 인터페이스와 더불어 Set, Queue 인터페이스들이 Collection 인터페이스에 상속된 구조로 되어있다. 여기에서 가지치기되어 List 인터페이스에 상속된 클래스가 ArrayList, LinkedList, Stack 그리고 Vector이다.

 ArrayList와 LinkedList는 List인터페이스에 상속받아서 구현을 하였으나 Stack이 조금 특이한 구조로 되어있다. Stack은 Vector에 상속받아 구현이 되고 있는 것이다.

실제 Stack은 List 인터페이스가 아닌 Vector 클래스를 상속받는다.

 분명 List 인터페이스를 상속받은 컬랙션 클래스들은 ArrayList, LinkedList, Vector, Stack이고 그럼 Stack도 그냥 List 인터페이스만 받아서 구현하면 되지 않을까? 하는 것이 보통 생각이지만 Stack과 Vector가 나온 시기를 생각하면 이해하기 쉽다.

  • JDK1 : Vector, Stack, Hashtable, Properties가 Collection 프레임워크 없이 제공됨
  • JDK1.2 : Collection 프레임워크 제공
  • JDK1.5 : Iterable 인터페이스 추가 > Collection 인터페이스가 상속받음

 즉, Collection 프레임워크가 제공되기 이전에 이미 Vector와 Stack이 구현된 상태였고 그때 이미 List가 아닌 Vector를 상속받아 구현이 된 상태이기 때문에 Collection 프레임워크가 새로 생성되어 굳이 새로 구현하지 않고 Vector만 Collection 프레임워크를 상속받고 Stack은 Vector를 상속받은 채로 쭉 사용되고 있는 것이다.

(실제 위 스크린샷의 Since를 보면 Stack이 JDK1.0에서 업데이트되었다.)

 

구현

 지금 하는 직접 구현하기는 최대한 실제 클래스와 비슷한 구조로 구현을 하고자 하였다. 따라서 List 인터페이스를 상속받거나 따로 Stack 인터페이스를 생성해서 새로 짜는 것이 아니라 Vector를 상속받아서 Stack에 필요한 부분만 받아서 사용하고자 했다.

 단 구현하는 범위는 Vector를 포함하지 않을 생각이기 때문에 Vector를 상속받아 구현하는 것이 아닌 ArrayList를 상속받아 구현하고자 한다.

 사실 ArrayList와 Vector는 기능상의 차이가 거의 없고 큰 차이라면 자동 동기화를 기본으로 제공하느냐 아니냐의 차이이다. Vector는 동기화된 메소드로 구성되어있기 때문에 멀티 쓰레드가 동시에 이 메소드를 실행할 수 없고 한 쓰레드가 다쓰고나면 다음에 사용할 수 있다. 하지만 ArrayList는 자동동기화가 빠져있고 옵션으로써 동기화를 제공한다. 따라서 물론 멀티 쓰레드 환경에서는 동기화를 사용하는 것이 안전하지만 백터는 싱글 쓰레드일때도 동기화를 걸기 때문에 ArrayList보다 성능이 떨어진다.

 그 이외의 우리가 사용하게 될 기능상의 차이는 지금 만들어 놓은 List 인터페이스 상의 내용밖에 없기 때문에 Vector를 굳이 구현한다고 큰 차이가 없을 것이어서 ArrayList를 상속받아서 Stack을 구현하도록 한다.

 

 구현 목록은 다음과 같다. ArrayList를 상속받아서 사용하기 때문에 LIFO에 대한 내용의 구현의 주 핵심이다.

  • push()
  • pop()
  • peek()
  • search()
  • empty()

(코드 가독성을 위해 javadoc는 지우고 코드를 설명했다. 전체코드는 github.com/jinyoungchoi95/DataStructure/blob/master/src/DataStructure/List/Stack.java에서 확인할 수 있다.)

 

1. default 세팅

 Stack 클래스를 생성하고 ArrayList 클래스를 상속받는다.

package DataStructure;

import java.util.EmptyStackException;

public class Stack<E> extends ArrayList<E> {

    public Stack() {
    }

 ArrayList를 상속받아 사용하기 때문에 따로 Object 배열이나 다른 변수는 제공하지 않고 ArrayList의 값을 사용한다.

 

2. push()

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

    return item;
}

 Stack에서는 데이터를 추가할 때 ArrayList나 LinkedList와는 다르게 push한다고 표현한다.

 push는 항상 Stack의 마지막에 추가되어야하기 때문에 ArrayList에서 add() method를 사용하여 빠르게 구현할 수 있다. Object[] 배열로 구현을 하지만 이미 ArrayList에서 동적으로 Object[] 배열의 크기를 관리해주기 때문에 Stack에서는 이를 생각하지 않고 ArrayList.add() 메소드를 가져다가 쓰기만하면 되는 것이다.

 

3. peek()

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

    return get(len - 1);
}

 Stack은 LIFO로 항상 최근에 넣은 데이터를 밖으로 빼내며 그 밑에 있는 데이터는 사실 관심이 없다. Stack에서 데이터를 받을 수 있는 것은 최상단에 위치한 가장 최근의 데이터이기 때문이다. 따라서 가장 마지막에 넣은 데이터를 검색하는 peek()메소드를 지원한다.

 마지막 데이터라고 한다면 배열의 크기 size에서 -1을 한 값이 마지막 데이터라고 할 수 있다.(index는 0부터 시작하기 때문에) 따라서 len 변수에 ArrayList의 size를 받아오는 size()메소드를 받아온다. 그 후 ArrayList의 원하는 인덱스의 요소를 가져오는 get() 메소드를 사용한다면 Stack의 가장 최근 값을 받아올 수 있다.

 단, size가 0이라면 해당 배열은 비어있으므로 get(-1);이 호출되고 get()메소드에서는 존재하지 않은 index에 대해서 처리하는 IndexOutOfBoundsException이 존재하기 때문에 예외처리가 발생하도록 알아서 처리된다.

 

4. pop()

public E pop() {
    E object = peek();
    int len = size();

    remove(len - 1);

    return object;
}

 Stack에서 데이터를 뽑아낼때는 pop한다고 표현한다.

 pop은 데이터의 최상단에 있는 데이터를 가져옴과 동시에 해당 데이터를 제거하는 역할을 한다. 따라서 우선 최상단의 데이터를 peek() 메소드를 이용해서 object에 값을 담아 낸다. 만약 Stack이 비어있다면 이 과정에서 예외처리가 발생할 것이다.

 그 다음 ArrayList.remove() 메소드를 통해서 가장 마지막에 있는 요소를 제거하고 담아두었던 object를 반환한다.

 

5. search()

public int search(Object o) {
    int index = lastIndexOf(o);

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

    return -1;
}

 Stack의 search는 ArrayList에서 indexOf() 메소드와는 조금 다르게 구현된다.

 일단 ArrayList의 indexOf()와 lastIndexOf()는 어떻게 구현되었었을까? 처음부터 혹은 뒤부터 검사를 하여서 해당하는 배열의 위치를 그냥 반환했다. 즉, ArrayList의 elementDate[]배열의 위치를 반환했던 것이다.

 하지만 stack에서는 기준점이 항상 가장 마지막에 들어간 값이다. 따라서 일단 indexOf()를 이용해서 값의 배열에서의 위치를 받아오더라도 반환하는 값은 조금 조정해야한다. 반환해야하는 규칙은 가장 마지막에 들어온 값이 1이며, 그 다음값은 2, 3, ....의 식으로 값이 조정된다. 즉 배열위치와는 정반대위치이면서 시작이 1이어야 한다. 따라서 index를 찾아서 -1이 아닌 경우에는 배열의 크기 size()에서 index를 제거해준다면 원하는 로직이 완성된다. -1인 경우에는 찾지 못하였기 때문에 -1을 반환한다.

 그림으로 나타내면 다음과 같다.

실제 ArrayList 내의 index와 search() 메소드에서 가르키는 index가 다르다.

6. empty()

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

 Stack이 비어있는지를 확인하는 메소드이다. ArrayList.size() 메소드를 통해 받아낸 배열의 크기가 0라면 비어있다는 뜻이므로 true를 반환, 아니라면 false를 반환한다.

 

Stack의 한계점

 지금까지 Stack 구현은 실제 Stack 클래스가 구현된 방식을 토대로 구현했다. List 인터페이스를 상속받은 ArrayList(Vector)를 상속받아서 구현한 것이다.

 근데 이 Stack 클래스는 구조적으로 한계가 있다고 할 수 있다. 물론 Stack의 LIFO는 좋은 자료구조이며 이를 Stack 클래스에서 구현하긴 했다. 근데, 문제는 ArrayList를 상속받아서 구현했다는 것이다. 왜 이게 문제가 될까?

 

 Stack은 항상 LIFO, 후입선출이어야하며 중간에 index를 가져와서 제거하거나 중간에 값을 추가하면 안된다. 근데 지금 Stack의 경우 ArrayList를 상속받아 사용하기 때문에 Stack 객체를 만들어도 결국 ArrayList의 메소드를 사용할 수 있다. 근데 ArrayList에는 LIFO를 반하는 메소드들이 있다는게 이제 떠오른다.

public void add(int index, E element) {
    rangeCheckForAdd(index);
    resizeCapacity(size + 1);
    fastAdd(index);
    elementData[index] = element;
    size++;
}

public boolean remove(Object o) {
    int index = indexOf(o);
    if(index>-1){
        fastRemove(index);
        return true;
    }
    return false;
}

public E remove(int index) {
    rangeCheck(index);

    E oldValue = (E) elementData[index];
    fastRemove(index);

    return oldValue;
}

public E get(int index) {
    rangeCheck(index);

    return (E) elementData[index];
}

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = (E) elementData[index];
    elementData[index] = element;
    return oldValue;
}

 전부다 LIFO를 지키지 않고 중간에 있는 index값을 조정하는 메소드들이다. 따라서 사실 Stack을 사용한다, LIFO 자료구조를 사용한다라고 할 때 Stack 클래스를 사용하는 것은 구조적인 결함이 있는 클래스를 사용한다는 것과 같다.

 

 실제로 Oracle 공식 docs에서도 이와 같은 내용을 언급하여준다.

A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class. For example:

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

 보다 완전한 LIFO stack을 사용하고 싶다면 Stack 클래스가 아닌 Deque 인터페이스와 ArrayDeque를 활용하는 것이 바람직하다.

 

 

 

앞에서도 말했지만 전체 코드는 깃허브에 전부 저장해두었습니다.

최대한 공식문서와 실제 class 파일을 참고하여 만들었지만 혹시 모를 이탈자나 잘못된 부분은 댓글로 피드백 부탁드립니다.

 

[참고 자료]

https://docs.oracle.com/javase/7/docs/api/java/util/Stack.html (oracle java docs)

저작자표시

'자료구조' 카테고리의 다른 글

[JAVA] Collection Interface/ add()와 offer() 차이  (1) 2021.04.21
[JAVA] Deque 직접 구현하기  (0) 2021.04.20
[JAVA] Queue 직접 구현하기  (1) 2021.04.20
[JAVA] LinkedList 직접 구현하기  (1) 2021.03.22
[JAVA] ArrayList 직접 구현하기  (2) 2021.03.19
댓글
최근에 올라온 글
Total
Today
Yesterday