스택(STACK)

스택은 데이터를 일시적으로 저장하기 위한 자료구조 중 하나이다.
스택만의 특징은, LIFO(Last In First Out) 의 데이터 입출력 매커니즘을 가지고 있다는 것인데 위의 그림과 같이 데이터를 쌓아넣는 형식으로 입력하고 꺼내올때는 마지막에 넣은 데이터부터 순서대로 꺼내올 수 있게 된다.

스택에서 가장많이 사용하는 기본적인 용어는 PUSH(데이터 입력), POP(데이터 출력), PEEK(마지막 데이터 확인) 등이 있고 스택의 최상단 부분을 TOP, 최하단 부분을 BOTTOM 이라 부른다.

이와같은 스택구조는 JAVA 프로그램에서 메서드를 호출하고 실행할 때 사용하는 구조이기도 하다.
Recursion을 돌렸을때 stackoverflow 를 반갑게 맞이한 적이 있을텐데, 잘못된 설계로 BaseCase 로 빠지지 않고 계속 자기자신을 호출함으로써 stack 에 지속적으로 메서드가 push 되기 때문에 저장한계치를 넘어가면 stackoverflow가 발생하게 되는 것이다.

다음으로 JAVA 코드로 배열을 활용해 스택을 구현해 보자

// 스택 클래스 구현하기
public class IntStack {
    private int max;        // 스택 용량
    private int ptr;        // 스택 포인터
    private 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;
        }
    }

    public int push(int x) throws OverflowIntStackException{
        if( ptr >= max )
            throw new OverflowIntStackException();
        return stk[ptr++] = x;
    }

    public int pop() throws EmptyStackException{
        if( ptr <= 0)
            throw new EmptyStackException();
        return stk[--ptr];
    }

    public int peek() throws EmptyStackException{
        if ( ptr <= 0 )
            throw new EmptyStackException();
        return stk[ptr -1];
    }

    public int indexOf(int x){   // x 값에 해당하는 스택의 index 반환 없다면 -1 
        for (int i = ptr -1; i >= 0 ; i--){
            if(x == stk[ptr])
                return i;
        }
        return -1;
    }

    public void clear(){        // 스택 비우기 
        ptr = 0;
    }

    public int capacity(){      // 스택의 한계 용량치 
        return max;
    }

    public int size(){          // 스택의 크기(데이터가 몇개 들어있는지)
        return ptr;
    }

    public boolean isFull(){    // 스택이 한계 용량치 인지 확인
        return ptr >= max;
    }

    public void dump(){         // 스택을 bottom 부터 top 까지 scan 
        if( ptr <= 0 ){
            System.out.println("스택이 비어 있습니다.");
        }
        else {
            for(int i = 0; i < ptr; i++)
                System.out.print(stk[i] + " ");
            System.out.println();
        }
    }
}

이어서 int 타입이 아닌 다양한 타입으로 스택을 이용할 수 있도록 Generic 을 활용해 스택을 구현해 보자

public class GenStack<T> {
    private int max;
    private int ptr;
    private T[] stk;

    public static class EmptyStackException extends RuntimeException{
        public EmptyStackException(){}
    }

    public static class OverflowStackException extends RuntimeException {
        public OverflowStackException() {}
    }

    public GenStack(int max) {
        this.max = max;
        ptr = 0;
        stk = (T[])new Object[max];
    }

    public T push (T value) throws OverflowStackException{
        if(ptr >= max)
            throw new OverflowStackException();
        return stk[ptr++] = value;
    }

    public T pop() throws EmptyStackException{
        if(ptr <= 0)
            throw new EmptyStackException();
        return stk[--ptr];
    }

    public T peek() throws EmptyStackException{
        if(ptr <= 0 )
            throw new EmptyStackException();
        return stk[ptr-1];
    }