Stack 스택

자료구조 첫 번째 학습 주제 : 스택 Stack

후입 선출 형식으로 데이터를 관리하는 자료형이다.

• First In Last Out : 첫번째로 들어오면 마지막으로 나감

• Last In First Out : 마지막에 들어오면 첫번째로 나감

  마지막에 들어온 사람이 자리가 없어서 문 앞에 앉아있다가 제일 첫번째로 나감 🤣

Stack은 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용한다.

• ex : 함수 콜 스택, 수식 계산, 인터럽트 처리 등등

스택에서 사용하는 용어

• Stack stack = new Stack(); : 스택 자료형의 사용을 위한 인스턴스화

• stack.push( data ); : stack에 data 입력

• bottom : stack의 bottom 위치.
  -> 이게 의미가 있나.. .싶었는데 역시 Java에 내장된 Stack 클래스에는 구현되어있지 않았다
  왜그렇게 생각했느냐면 스택은 바닥이 무조건 0이라고 생각했기 때문이다.

• top : stack의 최 상위 데이터 위치.
  -> 이것은 구현되어 있을 줄 알았는데 구현 되어있지 않았다...!!

• stack.peek() : 스택의 top 위치에 존재하는 값을 보여줌.
  -> top 위치의 값을 복사해온다고 생각하면 좋을것 같다.

• stack.pop() : 스택의 top 위치에 있는 데이터를 빼냄. stack에서 제거
  -> 스택에서 최상위에 존재하는 데이터를 빼내면서 값을 들고있기 때문에,
  이 값을 사용하려면 stack.pop() 을 적당한 변수에 담아주면 된다.
  -> String data = stack.pop();

• stack.contains( data ); : data가 stack에 들어있는지 유무를 boolean 자료형으로 알려줌

• stack.clear() : 스택의 모든 데이터를 지워줌

• stack.empty() : 스택이 비어있는 상태인지를 boolean 자료형으로 알려줌

• stack.size() : 스택의 크기가 얼마인지(= 데이터가 몇개 들어가있는지) 알려줌

만약 스택이 비어있는데, pop() 명령어를 날린다면?

java.util.EmptyStackException 에러를 만날 수 있게 된다.
이 상황을 방지하기 위해 방어 코드를 구현해두어야 한다.

---

배열로 Stack 구현해보기!

class Stackk<T> {
    private Object[] arr;
    private int maxSize;
    private int top;

    private Stackk() {}
    public Stackk(int maxSize) {
        this.maxSize = maxSize;
        arr = new Object[maxSize];
        topInit();
    }

    private void topInit() {
        top = -1;
    }

    public boolean isFull() {
        return (top + 1) == maxSize;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public void push(T data) {
        if (isFull()) {
            System.out.println("[ push 실패 : " + data + " ] Stackk이 가득 찼습니다.");
            return;
        }

        arr[++top] = data;
    }

    public T pop() {
        if (isEmpty()) {
            System.out.println("[ pop 실패 ] Stackk이 비어있습니다.");
            return null;
        }

        T value = (T) arr[top];
        arr[top--] = null;

        return value;
    }

    public T peek() {
        return (T) arr[top];
    }

    public int size() {
        return top + 1;
    }

    public boolean contains(T data) {
        for (Object t: arr)
            if (t.equals(data))
                return true;

        return false;
    }

    public void clear() {
        for (int i = 0; i <= top; i++)
            arr[i] = null;

        topInit();
    }

	// 편의를 위해 작성!
    public void print() {
        System.out.println(this);
    }

    @Override
    public String toString() {
        return "Stackk : " + Arrays.toString(arr) + "\n" +
                "  Size : " + size() + "\n" +
                "   top : " + top + "\n";
    }
}

Stackk 클래스 테스트

public class MyStack {

    static final int STACK_SIZE = 10;

    public static void main(String[] args) {

        Stackk<Integer> s = new Stackk<>(STACK_SIZE);

        // stack 상태 조회
        s.print();

        // 1~10 입력
        IntStream.range(1, 11).forEach(s::push);
        s.print(); // stack 상태 조회

        // stack 가득찼을 때 값 추가 시도
        s.push(11);

        // 방금 추가 시도한 값 들어갔는지 확인
        System.out.println();
        System.out.println("contains 11 : " + s.contains(11));

        // 값 1개 pop
        System.out.println();
        System.out.println("pop : " + s.pop());
        s.print(); // stack 상태 조회

        // stack 초기화
        s.clear();

        // stack 상태 조회
        s.print();

        // stack 비어있을 때 pop 시도
        s.pop();
    }

}

실행결과