스택

스택이란?

◽  데이터를 일시적으로 저장하기 위해 사용하는 자료구조

◽  데이터의 입력과 출력 순서는 후입선출(LIFO)

 

스택 구현하기

본체 만들기

class IntStack {
    int max;    // 스택 용량
    int ptr;    // 스택 포인터
    int[] stk;  // 스택의 본체
    
    // 실행 시 예외 : 스택이 비어 있음
    public class EmptyIntStackException extends RuntimeException {
        public EmptyIntStackException() { }
    }
    
    // 실행 시 예외 : 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException {
        public OverflowIntStackException() { }
    }
    
    // 생성자
    public IntStack(int capacity) {
        ptr = 0;
        max = capacity;
        try {
            stk = new int[max];  // 스택 본체용 배열을 생성
        } catch (OutOfMemoryError e) {
            max = 0;
        }

}

◽  스택 용량 (max) : 스택에 쌓을 수 있는 최대 데이터 수

◽  스택 포인터 (ptr) : 스택에 쌓여 있는 데이터 수

 

푸시 메서드 push

// 스택에 x를 푸시
public int push(int x) throws OverflowIntStackException {
    if (ptr >= max)
        throw new OverflowIntStackException();
    return stk[ptr++] = x;
}

◽  스택에 데이터를 푸시하는 메서드

◽  스택이 가득 차서 푸시할 수 없는 경우에는 예외처리를 한다.

 

팝 메서드 pop

// 스택에서 데이터를 팝 (정상에 있는 데이터를 꺼냄)
public int pop() throws EmptyIntStackException {
    if (ptr <= 0)
        throw new EmptyIntStackException();
    return stk[--ptr];
}

◽  스택의 꼭대기에서 데이터를 제거하고 그 값을 반환한다.

◽  스택이 비어 있어 팝을 할 수 없는 경우 예외처리를 한다.

 

피크 메서드 peek

// 스택에서 데이터를 피크(정상에 있는 데이터를 들여다봄)
public int peek() throws EmptyIntStackException {
    if (ptr <= 0)
        throw new EmptyIntStackException();
    return stk[ptr - 1];
}

◽  가장 꼭대기에 있는 데이터가 무엇인지 반환만 해준다.

 

검색 메서드 indexOf

// 스택에서 x를 찾아 인덱스(없으면 -1)를 반환
public int indexOf(int x) {
    for (int i = ptr - 1; i >= 0; i--)  // 정상 쪽에서 선형 검색
        if (stk[i] == x)
            return i;  // 검색 성공
    return -1;         // 검색 실패
}

◽  스택 본체의 배열 stk에 x와 같은 값의 데이터가 포함되어 있는지, 포함되어 있다면 배열의 어디에 들어 있는지를 조사하는 메서드이다.

◽  배열 인덱스가 큰 쪽에서 작은 쪽으로 스캔하며, 검색에 성공하면 찾아낸 요소의 인덱스를 반환하고, 실패하면 -1을 반환한다.

 

스택의 모든 요소를 삭제하는 메서드 clear

// 스택을 비움
public void clear() {
    ptr = 0;
}

 

용량을 확인하는 메서드 capacity

// 스택의 용량을 반환
public int capacity() {
    return max;
}

 

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

// 스택에 쌓여 있는 데이터 수를 반환
public int size() {
    return ptr;
}

 

스택이 비어 있는지 검사하는 메서드 isEmpty

// 스택이 비어 있는가?
public boolean isEmpty() {
    return ptr <= 0;
}

 

스택이 가득 찼는지 검사하는 메서드 isFull

// 스택이 가득 찼는가?
public boolean isFull() {
    return ptr >= max;
}

 

스택 안에 있는 모든 데이터를 표시하는 메서드 dump

// 스택 안에 있는 데이터를 바닥에서 꼭대기 순서로 출력
public void dump() {
    if (ptr <= 0)
        System.out.println("스택이 비어 있습니다.");
    else {
        for (int i = 0; i < ptr; i++)
            System.out.print(stk[i] + " ");
        System.out.println();
    }
}