1. 스택

• 데이터를 일시적으로 쌓아 놓는 자료구조
• 데이터의 입출력 순서는 후입선출 방식이다.
  즉, 나중에 넣은 데이터를 가장 먼저 꺼낸다.
• 스택에 데이터를 넣는 작업을 푸시(push)라고 한다.
• 스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다.
• 자바 프로그램에서 메서드를 호출하고 실행할 때 프로그램 내부에서 스택을 사용함.

1) 스택 만들기

• 스택을 생성할 때 용량을 결정하는 고정 길이 스택을 만든다.

package chap4;

public class IntStack {
    private int[] stk; //스택용 배열
    private int capacity; // 스택 용량
    private int ptr; // 스택 포인터
    
    // 실행시 예외: 스택이 비어있음.
    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException() {}
    }
    
    // 실행시 예외: 스택이 가득참.
    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException() {}
    }
    
    // 생성자
    public IntStack(int maxlen) {
        ptr = 0;
        capacity = maxlen;
        try {
            stk = new int[capacity]; // 스택 본체용 배열을 생성
        } catch (OutOfMemoryError e) { // 생성할 수 없음.
            capacity = 0;
        }
    }
    
    // 스택에 x를 푸시
    public int push(int x) throws OverflowIntStackException {
        if (ptr >= capacity) // 스택이 가득참
            throw new OverflowIntStackException();
        return stk[ptr++] = x;
    }

    // 스택에서 데이터를 팝(꼭대기에 있는 데이터를 꺼낸다)
    public int pop() throws EmptyIntStackException {
        if(ptr <= 0) // 스택이 비어있음.
            throw new EmptyIntStackException();
        return stk[--ptr];
    }
}

(1) 분석

• 스택용 배열 stk

- 푸시된 데이터를 저장하는 스택용 배열

• 스택 용량 capacity

- 스택의 용량(스택에 쌓을 수 있는 최대 데이터 수)을 나타냄

• 스택 포인터 ptr

- 스택에 쌓여있는 데이터 수를 나타내는 필드.
- 스택이 비어있으면 0, 가득 차 있으면 capacity값과 동일함.

• 생성자 IntStack

- 스택용 배열 본체를 생성하는 준비작업
- 생성할 때 스택은 비어있어 ptr값은 0으로 전달받는다.
- 매개변수 maxlen은 capacity값에 대입한다.
- 배열 본체의 개별 요소의 인덱스식은 stk[0]~stk[ptr-1]

• 푸시 메서드 push

- 스택에 데이터를 넣음.
- 스택이 가득찰 경우 예외 OverflowIntStackException 내보낸다.

• 팝 메서드 pop

- 스택의 꼭대기에 있는 데이터를 빼는 작업
- 스택이 비어있다면 예외 EmptyIntStackException 내보낸다.

• 피크 메서드 peek

- 데이터를 들여보내는 작업
- 스택이 비어있지 않으면 꼭대기에 있는 요소 stk[ptr-1] 반환
- 연산자 >= 또는 <= 사용

• 모든 요소를 삭제하는 clear 메서드

- 스택에 쌓여있는 모든 데이터들을 삭제하는 작업
- 삭제하게 되면 ptr 값은 0이 할당된다.

• 검색 메서드 indexOf

- 스택 본체의 배열이 stk에 x와 같은 값을 가지고 있는지 
가지고 있다면 어디에 들어있는지 검색하는 메서드

• 용량을 확인하는 메서드 getCapacity

- 스택의 용량 반환

• 데이터 개수 확인하는 메서드 size

- 현재 스택에 쌓여있는 데이터 개수(ptr값) 반환

• 스택이 비어있는지(가득찼는지) 검사하는 메서드 isEmpty(isFull)

- 스택이 비어있(가득찼)다면 true, 그렇지 않으면 false

• 스택 안에 있는 모든 데이터 출력하는 메서드 dump

- 스택에 쌓여있는 모든 데이터를 바닥부터 꼭대기 층까지 출력하는 메서드