[알고리즘] Stack(스택 알고리즘)_JAVA[자바] 백준-28278번

 

 

스택이란?

 

 

들어가며

데이터를 일시적으로 보관하는 자료구조인 스택에 대해서 알아보도록 하겠습니다.

---

 

스택 이란?

스택은 자료를 일시적으로 보관해 두는 자료구조로써 후입선출(LIFO: Last In First Out)을 통해서 데이터를 일시적으로 보관합니다.

LIFO는 영문자 그대로 나중에 들어간 데이터부터 가장 먼저 꺼내는 방법입니다.

스택에서는 데이터를 넣을때는 PUSH라고 부르며, 데이터를 꺼낼 때는 POP라고 부릅니다.

위그림과 같이 푸쉬와 팝과정을 나타내고 있다. psuh를 할 때에는 데이터를 차곡차곡 쌓아가다가 pop을 하면 제일 최근에 들어온 45 값을 pop며 LIFO 과정을 거치는 자료구조라고 볼 수 있다.

---

 

알고리즘 예제

알고리즘예제에는 백준의 28278번을 보고 풀어볼 예정입니다.

자바에서는 제네렉으로 java.util.Stack 메서드를 지원합니다.
하지만 이번 풀이에서는 스택을 직접 클래스 만들어서 사용해 볼 예정입니다.

Stack클래스에서 지원하는 메서드명을 보면

peek() = 데이터의 최상의 값을 보여준다.

empty() = 스택 배열에 값이 비어있는지 확인하는 메서드 등을 지원합니다.

문제를 한번 확인해 보면 다음과 같이 5개의 메서드를 추출할 수 있는 것을 볼 수 있습니다. pop, push, check, empty, peek이제 이 5개의 값을 가지고 Stack 클래스를 만들어서 직접 문제를 풀어 보도록 하겠습니다.

Stack

public static class Stack {
    private int[] arr;  // 스택용 배열
    private int ptr;    // 스택 현재 위치

    // 생성자
    public Stack(int x) {
        ptr = 0;
        arr = new int[x];   // 스택 배열 생성
    }

    // 스택에 요소를 넣는 메서드
    public int push(int x) {
        return arr[ptr++] = x;
    }

    // 스택에서 요소를 빼는 메서드
    public int pop() {
        if (ptr > 0)
            return arr[--ptr];
        return -1;
    }

    // 스택의 현재 위치를 반환하는 메서드
    public int check() {
        return ptr;
    }

    // 스택이 비어있는지 확인하는 메서드
    public int isEmpty() {
        return ptr <= 0 ? 1 : 0;
    }

    // 스택의 맨 위 요소를 확인하는 메서드
    public int peek() {
        return ptr > 0 ? arr[ptr - 1] : -1;
    }
}

• 스택용 배열을 만들어주고 쉽게 값을 찾을 수 있도록 스택 포인터를 만들어줍니다.
• pop, push는 데이터를 넣고 뺐을때  증감, 후위 연산자를 통해서 prt을 변경합니다.
• check 메서드는  ptr의 크기가 곧 데이터의 수이기 때문에 반환해 줍니다.
• isEmpty와 peek는 삼항 연산자를 통해서 반환해 줍니다.

간단하게 스택 클래스를 만들었습니다. 

 

백준 스택 2

public class 스택2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int max = Integer.parseInt(br.readLine());

        Stack stack = new Stack(max);

        for (int i =0;i<max;i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int token = Integer.parseInt(st.nextToken());
            switch (token){
                case 1:
                    int token1 = Integer.parseInt(st.nextToken());
                    stack.push(token1);
                    break;
                case 2:
                    int pop = stack.pop();
                    sb.append(pop+"\n");
                    break;
                case 3:
                    int check = stack.check();
                    sb.append(check+"\n");
                    break;
                case 4:
                    int empty = stack.isEmpty();
                    sb.append(empty+"\n");
                    break;
                case 5:
                    int peek = stack.peek();
                    sb.append(peek+"\n");
                    break;
            }
        }
        System.out.println(sb);
    }

 

switch문을 통해 첫 번째 입력하는 값을 체크해 switch문안에서 우리가 만든 Stack클래스를 사용해 값을 반환해 줍니다.

결과

 

결과를 실행해 보면 다음과 같이 성공하는 것을 볼 수 있습니다. 자바의 알고리즘 특성상 코드가 길어지고 다른 언어에 비해 속도가 느리기 때문에... 1028ms가 나오네요...ㅜㅜ

암튼 직접 스택알고리즘을 구현해서 문제를 풀어봤습니다.!