얼거스 개발 일지

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

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

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

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

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

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

스택에서 사용하는 용어

• void push( data ); : stack에 data 입력
• Object peek() : 스택의 top 위치에 존재하는 값을 보여줌.
  -> top 위치의 값을 복사해온다고 생각하면 좋을것 같다.
• Object pop() : 스택의 top 위치에 있는 데이터를 빼냄. stack에서 제거
  
• boolean contains( data ); : data가 stack에 들어있는지 유무를 boolean 자료형으로 알려줌
• void clear() : 스택의 모든 데이터를 지워줌
• boolean empty() : 스택이 비어있는 상태인지를 boolean 자료형으로 알려줌
• int 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();
    }
 
}

실행결과