스택(Stack)

" FILO : First In Last Out " 

 

어디선가 본거 같은 문구 아닌가요 ?

소방관 분들 존경스럽습니다! 존멋탱!

네! 소방서에서 볼 수 있는 문구죠! 

소방관 분들 항상 감사하게 생각하고 있습니다. 지금 이시간에도 열심히 일해주시는 소방관 분들 화이팅!

 

자료구조에도 이 말이 통하는 것이 있는데 바로 스택(Stack) 입니다!

스택은 아래 그림과 같은 형태의 선형자료구조입니다.

 

스택(Stack)

깊숙한 통에 책을 쌓아 올린다고 생각하면 좋습니다.

먼저 들어간 책이 가장 아래 놓이고, 그 위로 책이 차근차근 쌓이겠지요.

그 책을 꺼낸다면 맨위 책부터 하나하나 꺼내야 할 것이구요 

그래서 후입선출구조 (LIFO : Last In First Out)의 구조라 합니다.

 

이 자료구조에는 넣는 함수 Push , 꺼내는 함수 Pop를 구현합니다.

우선 스택을 구현하기 위해 통이 될 배열과 현재위치 그리고 통의 사이즈를 선언합니다.

0. 선언

public class Stack {
     int [] STACK = null;
     int IDX;
     int MAX_SIZE;

    public Stack(){

        STACK = new int[10];
        IDX = -1;
        MAX_SIZE = 9;
    }
 
}

STACK 배열이 통이 될 것이고, IDX가 현재 책이 어디까지 쌓여 있는지를 나타낼 것입니다.

MAX_SIZE가 책을 최대한 쌓아올릴수 있을때의 마지막 위치 입니다.

 

1. Push 함수 

 통에 책을 넣을 함수입니다.

    /**
     * push
     *
     * @param value
     * @return 성공 : 0 / 실패 : -1
     */
    int push(int value){
        if(IDX == MAX_SIZE){
            return -1 ;
        }

        IDX++;
        STACK[IDX] = value;
        return 0;
    }

 우선 현재 책이 쌓인 높이와 최대 쌓여야 하는 위치가 같은지 확인하여, 더이상 쌓을 수 없을 시 -1를 리턴하게 되어 있습니다.

 책을 쌓을 수 있다면 IDX를 하나 증가한 후 그곳에 value 값을 넣습니다.

 

2.Pop 함수

 책을 꺼내는 함수입니다.

    /**
     * pop
     *
     * @return 성공 : value / 실패 : -1
     */
    int pop(){
        if(IDX == -1){
            return -1 ;
        }

        return STACK[IDX--];

    }

 우선, 현재 책이 쌓인 것이 없다면 -1를 리턴하게 되어 있습니다.

 책을 꺼낼 수 있다면 책(value)를 리턴합니다.

 

0. 전체 소스 

 비어있는지, 꽉 찼는지 확인 하는 부분을 isEmpty(), isFull() 함수로 만들어 구현 하였습니다.

public class Stack {
     int [] STACK = null;
     int IDX;
     int MAX_SIZE;

    public Stack(){

        STACK = new int[10];
        IDX = -1;
        MAX_SIZE = 10;
    }

    /**
     * push
     *
     * @param value
     * @return 성공 : 0 / 실패 : -1
     */
    int push(int value){
        if(isFull()){
            return -1 ;
        }

        IDX++;
        STACK[IDX] = value;
        return 0;
    }

    /**
     * pop
     *
     * @return 성공 : value / 실패 : -1
     */
    int pop(){
        if(isEmpty()){
            return -1 ;
        }

        return STACK[IDX--];

    }

    /**
     *  isEmpty
     *
     * @return isEmpty : true / not isEmpty : false
     */
    boolean isEmpty(){
        if(IDX == -1){
            return true;
        }
        return false;
    }

    /**
     *  full
     *
     * @return full : true / not full : false
     */
    boolean isFull(){

        if(IDX == MAX_SIZE-1){
            return true ;
        }

        return false;
    }

    public static void main(String[] args) {
        Stack stack = new Stack();

        for(int i = 12 ; i >0 ; i--){
            if(!stack.isFull())
                stack.push(i);
            else
                System.out.println("Stack is Full !!");
        }



        System.out.println("-- Stack Confirm --");

        for(int i = 0 ; i < stack.MAX_SIZE ; i++){
            System.out.println(stack.STACK[i]);
        }

        System.out.println("-- Stack Confirm End  --");


        for(int i = 12 ; i >0 ; i--){
            if(!stack.isEmpty())
                System.out.println(stack.pop());
            else
                System.out.println("Stack is Empty !!");
        }
    }

}

 

실행 결과