자바[JAVA] 자료구조 구현 6 - Stack

들어가기 전.

 

스택에 관해서는 이전 자료구조 수업 정리에서 충분히 설명했다고 생각하기 때문에 자세한 설명은 생략하겠습니다.

2024.04.11 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 5 - Queue and Stack

 

Stack 은 ArrayList 와 비슷하게 실제 JAVA 에서는 vector 를 기반으로 구현합니다. 이는 자료의 크기가 동적으로 변할 수 있음을 의미하고, 이에 관한 기능은 ArrayList 와 매우 유사합니다.

2024.04.26 - [자바[JAVA]/자바[JAVA] 자료구조 구현] - 자바[JAVA] 자료구조 구현 2 - ArrayList

 

Stack 코드

 

import Interfaces.Istack;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;
import java.util.EmptyStackException;

public class Stack<E> implements Istack<E>{

    private static final int DEFAULT_CAPACITY = 10; // 최소 용적 크기
//    private static final Object[] EMPTY_ARRAY = {}; // 빈 배열

    private Object[] array; // 요소를 담을 배열
    private int size; // 요소 개수

    // 생성자 1 (초기 공간 할당x 따라서 기본 용적으로 배열 생성)
    public Stack(){
        this.array = new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }

    // 생성자 2 (초기 공간 할당o)
    public Stack(int capacity){
        this.array = new Object[capacity];
        this.size = 0;
    }

    private void resize(){

        int arrayCapacity = array.length;

        // 용적이 꽉 찬 경우
        // 용적을 2 배로 늘려준다.
        if(size == arrayCapacity){

            int newsSize = arrayCapacity * 2;

            // Arrays.copyof 를 쓰면 반복문하고 주소 반환 해주는것을 한 번에 할 수 있다.
            array = Arrays.copyOf(array, newsSize);
            return;
        }
        // 용적이 너무 큰 경우
        // 용적을 1/2 로 줄여준다.
        if(size < (arrayCapacity / 2)){

            int newSize = arrayCapacity / 2;

            // 줄어드는 용적이 기본 용적보다 작아지는 경우
            // 기본 용적까지만 줄인다.
            if(newSize < DEFAULT_CAPACITY) {
                array = Arrays.copyOf(array, DEFAULT_CAPACITY);
                return;
            }

            // 그렇지 않은 경우
            array = Arrays.copyOf(array, newSize);
            return;

            // 아래 코드와 동일하다.
            // array = Arrays.copyOf(array, Math.max(DEFAULT_CAPACITY, newCapacity));
        }
    }

    @Override
    public E push(E item) {

        // 용적이 꽉 찼다면 용적 재할당을 해준다.
        if(size == array.length)
            resize();

        // 배열의 마지막 위치에 요소를 넣어준다.
        array[size] = item;
        // size 를 늘려준다.
        size++;

        return item;
    }

    @SuppressWarnings("unchecked")
    @Override
    public E pop() {

        // pop 할 것이 하나도 없다면 예외 반환
        if(size == 0)
            throw new EmptyStackException();

        // 삭제 요소의 반환을 위한 임시 저장
        E data = (E) array[size - 1];
        // 요소 삭제
        array[size - 1] = null;

        // size 감소
        size--;
        // 용적 재할당
        resize();

        // 삭제하는 요소 반환
        return data;
    }

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

        // peek 할 것이 하나도 없다면 예외 반환
        if(size == 0)
            throw new EmptyStackException();

        // 해당 요소 반환, 삭제를 일어나지 않음
        return (E) array[size - 1];
    }

    @Override
    public int search(Object value) {

        // value 가 null 인 경우 equals(null) 이 되어 null pointer exception 이 발생
        // value 가 null 인 경우를 따로 생각해주어야 한다.
        if(value == null){
            for(int i=0; i<size; i++){
                if(array[i] == null)
                    return (size - i);
            }
        }
        else {
            // 해당 요소들을 탐색
            for (int i = 0; i < size; i++) {
                // 해당 요소 발견
                if (array[i].equals(value)) {
                    // top 에서 부터의 index 를 반환
                    return (size - i);
                }
            }
        }

        // 해당 요소가 아에 없으면 -1 반환
        return -1;
    }

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

    @Override
    public void clear() {

        // 저장되어있던 모든 요소를 null 처리, 삭제
        for(int i=0; i<size; i++){
            array[i] = null;
        }

        // capacity 를 절반만 줄이는 이유는
        // clear 를 하고 다음에 들어오는 데이터, 요소의 개수가
        // 이전까지 담고있었던 요소의 개수와 비슷하다는 점을 가정하기 때문이다.
        size = 0;
        resize();
    }

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

    @SuppressWarnings("unchecked")
    public Stack<E> clone() throws CloneNotSupportedException {

        // 얕은 복사
        Stack<E> clone = (Stack<E>) super.clone();

        // 배열을 size 만큼 copy
        clone.array = Arrays.copyOf(array, size);
        // 클론 배열의 용적 재할당
        clone.resize();

        // 클론 반환
        return clone;
    }

    public Object[] toArray(){

        // array 를 그냥 복사해서 넘겨준다.
        return Arrays.copyOf(array, size);
    }

    /*
     계속 말하지만 이런 식으로 제너릭 타입 배열을 만드는 것은
     타입 안정성을 무너뜨릴 수 있다.
     해당 toArray 는 Wrapper 같이 기본 타입들과 상호 호환이 되는 제네릭에 대해서만 가능하다.
     
     만약 타입 안정성을 유지하고 싶다면 제네릭 타입 배열을 만들지 말고
     타입을 특정한 후,
     Stream 을 이용하여 Array 를 만들면 된다.
     
     SomeClass[] = Stream.generate(() -> new SomeClass(data)).limits(size).toArray(new::SomeClass[]);
     
     로 생성 가능하다.
     */
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a){

        // a 의 길이가 짧아서 다시 할당함
        if(a.length < size){
            a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
        }

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

        return a;
    }
    
    public void sort(){
        
        // 만약 Comparable 을 구현 한 E 클래스라면
        // Comparator 에 null 이 들어가도 상관없다.
        sort(null);
    }
    
    @SuppressWarnings({"unchecked", "rawtypes"})
    public void sort(Comparator<? super E> c){
        
        // array 의 타입은 object 이기 때문에 그냥 Comparator 로 타입 캐스팅이 필요하다. 
        // 이는 타입 안정성을 무너뜨린다.
        
        // 따라서 애초에 array 를 E 타입 배열로 만든 다음에
        // c 를 타입 캐스팅 하지 않고 정령하는 것이 바람직하다.
        
        // 하지만 E 타입 배열을 만드는 것 자체가 타입 안정성을 무너뜨리기에
        // 제네릭 배열을 만들때는 vector 와 같이 STL 을 사용하는 것이 바람직하다.
        Arrays.sort(array, (Comparator) c);
    }
}