스택(Stack)

스택이란?

데이터를 일시 저장하는 자료구조.

데이터의 입출력순서는 후입선출(나중에 들어온 것이 먼저 나감)이다.

스택에 데이터를 넣는 작업을 푸시(push)

스택에서 데이터를 꺼내는 작업을 팝(pop)이라고 한다.

 

자바에서 메서드를 호출하고 실행할때도 내부적으로 스택을 사용한다.

다음은 스택클래스 IntStack을 구현하고 이를 사용하는 프로그램이다.

각 메서드에 대한 설명은 주석에 적혀있다!

 

import java.util.*;

public class Main {

    static 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;
            }
        }

        //스택에 x를 푸시
        public int push(int x) throws OverflowIntStackException{
            if(ptr >= max)
                throw new OverflowIntStackException();
            return stk[ptr++] = x; //데이터 저장 후 포인터+1
        }

        //스택에서 데이터를 팝
        public int pop() throws EmptyIntStackException{
            if(ptr <= 0)
                throw new EmptyIntStackException();
            return stk[--ptr]; //이미 포인터가 하나 올라가있으므로 포인터-1하고 데이터 팝
        }

        //스택에서 데이터를 피크 (꼭대기에 있는 데이터 엿보기)
        public int peek() throws EmptyIntStackException{
            if(ptr<=0)
                throw new EmptyIntStackException();
            return stk[ptr-1];
        }

        //스택에서 x를 찾아 인덱스를 반환. 없으면 -1을 반환
        public int indexOf(int x){
            for (int i = ptr-1; i >= 0; i--) {
                if(stk[i]==x)
                    return i;
            }
            return -1;
        }

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

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

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

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

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

	//스택 안의 모든 데이터를 바닥>꼭대기 순서로 출력.
        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();
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntStack s = new IntStack(64); //최대용량이 64인 스택

        while (true){
            System.out.println("현재 데이터 수:"+s.size()+"/"+s.capacity());
            System.out.print("(1)푸시 (2)팝 (3)피크 (4)덤프 (0)종료: ");
            int menu = scanner.nextInt();
            if(menu==0)break;;
            int x;
            switch (menu){
                case 1:
                    System.out.print("데이터:");
                    x = scanner.nextInt();
                    try {
                        s.push(x);
                    } catch (IntStack.OverflowIntStackException e) {
                        System.out.println("스택이 가득 찼습니다.");
                    }
                    break;

                case 2:
                    try{
                        x = s.pop();
                        System.out.println("팝한 데이터는 "+x+"입니다.");
                    }catch (IntStack.EmptyIntStackException e){
                        System.out.println("스택이 비어있습니다.");
                    }
                    break;

                case 3:
                    try{
                        x = s.peek();
                        System.out.println("피크한 데이터는 "+x+"입니다.");
                    }catch (IntStack.EmptyIntStackException e){
                        System.out.println("스택이 비어있습니다.");
                    }
                    break;

                case 4:
                    s.dump();
                    break;
            }
        }
    }
}