[자료구조] 5. 스택(Stack) 구현

스택(Stack) 구현

<필수 목록>

• 클래스 및 생성자 구성
• resize 메소드 구현
• push 메소드 구현
• pop 메소드 구현
• peek 메소드 구현
• search, size, clear, isEmpty 메소드 구현

<Stack 확장>

• ArrayList를 상속한 Stack

---

 

Stack 클래스 및 생성자 구하기

public class Stack<E> implements StackInterface{
    private static final int DEFAULT_CAPACITY = 10; // 최소 용적 크기
    private static final Object[] EMPTY_ARRAY = {}; // 빈 배열
    
    private Object[] array; // 요소를 담을 배열
    private int size; // 요소 개수
    
    public Stack() {
        this.array = EMPTY_ARRAY;
        this.size = 0;
    }
    
    public Stack(int capacity) {
        this.array = new Object[capacity];
        this.size = 0;
    }
}

 

DEFAULT_CAPACITY : 배열이 생성될 때의 최초 할당 크기. 최소 할당 용적 변수로 기본값은 10으로 설정.

EMPTY_ARRAY : 아무것도 없는 빈 배열

array : 요소들을 담을 배열

size : 배열에 담긴 요소의 개수

 

두 개의 생성자로 인해 위의 코드와 같이 미리 공간을 할당하지 않거나 할당하여 스택을 생성할 수 있다.

 

---

동적할당을 위한 resize 메소드 구현

들어오는 데이터의 개수에 따라 최적화된 용량을 가질 필요가 있다. 데이터가 적은데 용량이 크면 메모리가 낭비되고, 용량이 작은데 데이터가 많다면 넘쳐서 데이터를 담을 수 없게 된다. 그래서 size가 capacity에 얼만큼 차있는지를 확인하여, 적절한 크기에 맞게 용량을 변경해야 한다. 또한 용량은 외부에서 마음대로 접근하면 데이터 손상을 야기할 수 있으므로 private로 선언한다.

 

private void resize() {

    // 조건문 1) 빈 배열일 경우
    if (Arrays.equals(array, EMPTY_ARRAY)) {
        array = new Object[DEFAULT_CAPACITY];
        return;
    }

    int arrayCapacity = array.length;   // 현재 용량

    // 조건문 2) 용량이 가득 찼을 경우
    if (size == arrayCapacity) {
        int newCapacity = arrayCapacity * 2;

        // 배열 복사
        array = Arrays.copyOf(array, newCapacity);
        return;
    }

    // 조건문 3) 용량의 절반 미만으로 요소가 차지하고 있을 경우
    if (size < (arrayCapacity / 2)) {
        int newCapacity = arrayCapacity / 2;

        array = Arrays.copyOf(array, Math.max(DEFAULT_CAPACITY, newCapacity));
        return;
    }
}

 

조건문 1

 

앞서 생성자에서 사용자가 용량을 별도로 설정하지 않은 경우 EMPTY_ARRAY로 초기화 되어 있어 용량이 0인 상태이다. 이 경우를 고려해 이제 새로 array의 용량을 할당하기 위해 최소 용량으로 설정했던 DEFAULT_CAPACITY의 크기 만큼 배열을 생성하고 메소드를 종료한다.

 

조건문 2

 

데이터가 꽉 차있을 경우엔 데이터를 더 받을 수 있게 하기 위해 용량을 늘려야 한다. 기존 용량의 2배만큼 늘려주고 Arrays.copyof()를 통해 새로운 용량 크기만큼의 배열을 만들어 기존의 데이터도 복사해온다. 그 다음의 공간은 자동으로 null로 채워진다.

 

조건문 3

 

데이터가 용량의 절반에 미치지 못할 경우다. 이 경우엔 메모리가 불필요한 공간을 차지하고 있어 낭비가 된다. 그래서 용량을 최소 용량보다는 떨어지지 않도록 하는 선에서 절반으로 용량을 줄여 새로 할당한다.

 

---

push 메소드 구현

 

리스트로 치면 add(E value)와 같은 역할이다. 자바에 내장되어 있는 스택은 벡터를 상속받다보니 중간 삽입과 같은 것도 가능하지만 ArrayList를 상속하여 구현하는 파트에서 구현하고 우선 스택의 특징에 더 집중할 것이다.

 

1. 기본삽입 : push(E item)

자바 내부의 push 메소드는 push된 데이터를 리턴한다. 예제에서는 E 타입을 반환하는 메소드로 구현하였다.

 

@Override
public Object push(Object item) {

    // 용량이 꽉 찼다면 resize
    if (size == array.length) {
        resize();
    }

    array[size] = item; // 마지막 위치에 요소 추가
    size++;             // 사이즈 1증가

    return item;
}

 

---

pop 메소드 구현

고려해야 할 점은 삭제할 요소가 없는 경우 즉, 스택이 비어있는 경우 EmptyStackException으로 예외처리를 한다.

 

1. pop() 메소드

 

@Override
public Object pop() {

    // 삭제할 요소가 없다면 Stack 이 비었다는 것이므로 예외 발생 
    if (size == 0) {
        throw new EmptyStackException();
    }

    @SuppressWarnings("unchecked")
    E obj = (E) array[size - 1];        // 삭제될 요소를 반환하기 위한 임시 변수

    array[size - 1] = null;             // 요소 삭제

    size--;
    resize();

    return obj;
}

 

@SuppressWarnings("unchecked")를 붙이는 이유는 타입 안정성에 대해 경고를 보내기 때문이다. 하지만 스택에 push되는 아이템들은 유일하게 E 타입만 존재하므로 해당 어노테이션을 사용하여 ClassCastException이 발생할 일이 없으니 경고를 무시하는 것이다. 하지만 역시 남발하면 안된다. 형 변환시 예외 가능성이 없을 확실할 경우에 최소한의 범위에서 쓰는 것이 좋다. 그렇지 않으면 경고 메세지를 놓칠 수가 있다.

 

---

peek() 메소드 구현

1. peek() 메소드

@SuppressWarnings("uncheked")
@Override
public E peek() {

    // 삭제할 요소가 없다면 Stack 이 비었다는 것이므로 예외 발생
    if (size == 0) {
        throw new EmptyStackException();
    }

    return (E) array[size - 1];
}

 

---

search, size, isEmpty, clear 메소드 구현

1. search(Object o) 메소드

 

Java API를 보면 search() 메소드가 있다. 이는 찾으려는 데이터가 상단의 데이터로부터 얼마만큼 떨어져있는지에 대한 상대적 위치 값이다. 쉽게 말하자면 Top으로부터 떨어져있는 거리를 의미한다. (단, 1부터 시작) 수식으로 표현하면 size - index 값이 된다. 다만 일치하는 데이터가 없다면 -1 을 반환한다.

 

@Override
public int search(Object value) {

    // value 가 null 일 때는 equals(null)이 되어 NullPointerException 이 발생할 수 있다.
    // == 로 null 값을 비교한다.
    if (value == null) {
        for (int idx = size - 1; idx >= 0; idx--) {
            if (array[idx] == null) {
                return size - idx;
            }
        }
    } else {
        for (int idx = size - 1; idx >= 0; idx--) {

            // 같은 객체를 찾았을 경우 size - idx 를 반환
            if (array[idx].equals(value)) {
                return size - idx;
            }
        }
    }

    return -1;
}

 

 

2. size() 메소드

@Override
public int size() {
    return size;
}

 

 

3. isEmpty() 메소드

 

@Override
public boolean isEmpty() {
    return size == 0;
}

 

4. clear 메소드

 

clear()는 모든 요소들을 비워버리는 작업이다. 예를 들어 리스트에 요소를 담아두었다가 초기화가 필요할 때 쓸 수 있는 유용한 메소드이다. 모든 요소를 비워버린다는 것은 요소가 0개라는 말이므로 size 또한 0으로 초기화하고 배열의 용량 또한 현재 용량의 절반으로 줄일 수 있도록 한다.

 

@Override
public void clear() {
    for (int i = 0; i < size; i++) {
        array[i] = null;
    }
    size = 0;
    resize();
}

모든 배열을 명시적으로 null로 처리하는 것이 좋다.

 

---

<부가 기능>

1. clone() 메소드

 

항상 자료구조를 복사를 할때는 '얕은 복사', '깊은 복사'를 생각해야 한다. 단순히 주소값만 복사되어 완전히 값까지 복사가 되지는 않았는지 확인을 해야한다는 것이다. 그래서 깊은 복사를 해야하는데 이때 필요한 것이 clone() 이다. Object에 있는 메소드이지만 접근제어자가 protected라서 Cloneable 인터페이스를 implement를 해야 구현이 가능하다.

 

@Override
public Object clone() throws CloneNotSupportedException {

    // 새로운 스택 객체 생성
    Stack<?> cloneStack = (Stack<?>) super.clone();

    // 새로운 스택의 배열도 생성해주어야 함 (내부 객체는 깊은 복사가 되지 않는다.)
    cloneStack.array = new Object[size];

    // 현재 배열을 새로운 스택의 배열의 값을 복사함
    System.arraycopy(array, 0, cloneStack.array, 0, size);
    return cloneStack;
}

 

 

2. toArray() 메소드

 

toArray()는 두 가지가 있다. 하나는 아무 인자 없이 Stack의 리스트를 객체 배열로 반환 해주는 Object[] toArray()가 있고 다른 하나는 이미 생성된 다른 배열에 복사하고자 할 때 쓰는 T[] toArray(T[] a)가 있다.

 

public Object[] toArray() {
    return Arrays.copyOf(array, size);
}

@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size) {
        return (T[]) Arrays.copyOf(array, size, a.getClass());
    }

    System.arraycopy(array, 0, a, 0, size);

    return a;
}

 

Object[] toArray()는 Stack에 있는 요소의 수만큼 정확하게 배열의 크기가 할당되어 반환이 된다.

T[] toArray(T[] a)은 객체 클래스로 상속관계에 있는 타입이거나, Wrapper같이 데이터 타입을 유연하게 캐스팅할 여지가 있을때 유용하다. 또한 스택에 원소가 5개 있고 복사하려는 대상 배열에 10개가 있다면 대상 배열 앞쪽에 (0~4 인덱스) 원소가 복사되고, 그 뒤는 원래 배열에 있던 원소가 그대로 남는다.

 

 

3. sort() 메소드

 

 

public void sort() {
    /**
     * Comparator 를 넘겨주지 않는 경우 해당 객체의 Comparable 에 구현된 정렬 방식을 사용한다.
     * 만약 구현되어 있지 않다면 cannot be cast to class java.lang.Comparable 에러가 발생한다.
     * 만약 구현되어 있다면 null 로 파라미터를 넘기면
     * Arrays.sort() 가 객체의 compareTo 메소드에 정의된 방식으로 정렬한다.
     */
    sort(null);
}

@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
    Arrays.sort((E[]) array, 0, size, c);
}

 

---

ArrayList를 상속한 Stack

Stack은 Vector를 상속받는다고 했다. 또한 Vector는 ArrayList와 구조가 유사하다. (차이점은 동기화 지원 여부이다.)

그래서 ArrayList를 상속한 Stack을 구현해볼 것이다.

 

public class StackExtendsArrayList extends ArrayList<E> implements StackInterface<E> {
    
    // 초기 용량 할당 X
    public StackExtendsArrayList() {
        super();
    }
    
    public StackExtendsArrayList(int capacity) {
        super(capacity);
    }
}

 

Stack에서 구현해야 할 것은 크게 push, pop, peek, search, size, isEmpty 였다. size와 같은 경우는 ArrayList와 같기 때문에 size만 제외하고 5개만 구현하면 된다.

 

public class StackExtendsArrayList<E> extends ArrayList<E> implements StackInterface<E> {

    // 초기 용량 할당 X
    public StackExtendsArrayList() {
        super();
    }

    public StackExtendsArrayList(int capacity) {
        super(capacity);
    }


    @Override
    public E push(E item) {
        addLast(item); // ArrayList 의 addLast()
        return item;
    }

    @Override
    public E pop() {
        int length = size();
        E obj = remove(length - 1); // ArrayList 의 remove()
        
        return obj;
    }

    @Override
    public E peek() {
        
        int length = size();
        if (length == 0) {
            throw new EmptyStackException();
        }
        
        E obj = get(length - 1); // ArrayList 의 get()
        
        return obj;
    }

    @Override
    public int search(Object value) {
        int idx = lastIndexOf(value); // ArrayList 의 lastIndexOf()
        
        if (idx >= 0) {
            return size() - idx;
        }
        
        return -1;
    }

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }
}

 

ArrayList에 구현되어 있던 메소드를 활용하여 아주 간단하게 스택을 구현한 코드이다. 코드도 훨씬 간결한 것을 볼 수 있다.