자바 Stack 구현

LIFO (Last in firt out) 방식의 Stack을 구현한다.

기본적으로 Stack의 내부에서 최상위 타입 배열인 Object[]배열을 사용하여 데이터들을 관리한다.

상자에 a,b,c가 쌓여있다고 생각해보자 뺄때 무엇을 빼는게 좋겟는가?
c부터빼야 나머지를 뺄 수 있다.이게 스택이다.
Last In Firt Out 마지막에 들어간것이 처음에 나온다.

페이지 뒤로가기, 실행 취소 등등 이 대표적이다.

<필수 목록>

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

클래스 및 생성자

public class MyStack<E> implements StackInterface<E> {
    private static final int DEFAULT_CAPACITY = 10;
    private Object[] array;
    private int capacity;
    private int tos;

    public MyStack(){
        array = new Object[DEFAULT_CAPACITY];
        capacity = DEFAULT_CAPACITY;
        tos = -1;
    }

    public MyStack(int capacity){
        array = new Object[capacity];
        this.capacity = capacity;
        tos = -1;
    }
}

DEFAULT_CAPACITY : 기본 용량이다.
capacity : 용량을 나타내고
tos : top of stack 스택의 최상단을 가리킨다. (비어있다면 -1을 가리킴) 마지막 요소를 가리킨다.

resize 메소드 구현

Stack에는 Object배열이 존재한다. Object의 배열은 자동으로 크기를 늘리고 줄여야 한다.

1. 크기를 늘려야하는 상황
2. 크기를 줄여야 하는 상황

배열이 꽉찼을때 늘려주면되고 배열이 널널하면 크기를 줄여주면된다.
꽉차면 2배 늘려주고 용량의 절반이하로 요소가 들어가있다면 절반 줄여줄것이다.

public void resize(){
        int size = tos+1; // 요소의 수 

        // 부족
        if(capacity == size){
            capacity = capacity * 2;
            array = Arrays.copyOf(array, capacity);
            return;
        }

        // 여유
        if(size < capacity /2){
            array = Arrays.copyOf(array, Math.max(DEFAULT_CAPACITY, capacity/2));
            capacity = array.length;
            return;
        }
    }

push 메소드 구현

Pushes an item onto the top of this stack.

@Override
    public E push(E item) {
        resize();

        array[++tos] = item;
        return item;
    }

용량을 확인해주고 아이템을 넣는다.

pop 메소드 구현

Removes the object at the top of this stack and returns that object as the value of this function.

@Override
    public E pop() {
        if(tos == -1){
            throw new NoSuchElementException();
        }
        // E o = (E) array[tos--];
        @SuppressWarnings("unchecked")
        E data = (E) array[tos];
        array[tos] = null;
        tos--;
        resize();
        return data;
    }

tos == -1이라면 아무것도 들어가 있지 않은 상태이다.데이터를 빼고나서 tos를 하나 줄인다.

peek 메소드 구현

Looks at the object at the top of this stack without removing it from the stack.

@Override
    public E peek() {
        if(tos == -1){
            throw new NoSuchElementException();
        }
        return (E)array[tos];
    }

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

@Override
    public int search(Object o) {
        if(tos == -1){
            throw new NoSuchElementException();
        }

        int index = tos;
        int count = 1;

        for(int i = tos; i > -1; i--){
            if(o.equals(array[i])){
                return count;
            }
            count++;
        }

        return -1;

    }

    @Override
    public boolean empty() {
        return tos == -1;
    }

    @Override
    public int size() {
        return tos + 1;
    }

    @Override
    public void clear() {
        while(tos != -1){
            array[tos--] = null;
        }
        resize();
    }```
    
    
    https://github.com/Hodu-moon/DataStructure