[자료구조] Java Stack 이란? (Stack 메서드 정리, 예제 백준 9012 괄호 Java)

[자료구조] Java Stack 이란? (Stack 메서드 정리, 예제 백준 9012 괄호 Java)

Stack 이란?

Stack이란 한쪽 끝에서만 Data의 입출력이 가능한 대표적인 자료구조이다.
LIFO(Last In Firt Out)의 선형 구조이다.
즉, 가장 마지막에 들어간 데이터가 가장 먼저 나가는 구조이다.

즉, 쉽게 생각하면 일상에서 접시 혹은 책 등을 쌓아두는 구조라 생각하면 된다.
접시를 쌓아서 사용할 경우, 가장 나중에 놓여진 접시를 가장 먼저 사용하게 된다.
Stack도 위와 같은 구조처럼, 가장 나중에 들어온 데이터를 가장 먼저 나가게 된다.

Java Stack 사용하기

Java에서는 Stack을 편하게 사용할 수 있도록 java.util.Stack으로 라이브러리를 제공해 준다.

직접구현할 경우 LinkedList 혹은 Array로 구현이 가능하다.
하지만, 직접 구현하여 사용하는 경우가 얼마나 많을지는 잘 모르겠다.

import java.util.Stack;

public class Main{
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        System.out.println("Stack peek :" + stack.peek());
        stack.push(5);
        stack.pop();
        stack.push(6);
        System.out.println("Stack Search value 6 : " + stack.search(6));
        System.out.println("Stack Search value 2 : " + stack.search(2));
        System.out.println("Stack Search value 10 : " + stack.search(10));
        System.out.println(stack);     
    }
}

/* 출력
Stack peek :4
Stack Search value 6 : 1
Stack Search value 2 : 4
Stack Search value 10 : -1
[1, 2, 3, 4, 6]
*/

너무 기본적인 사용방법이다.
java의 Stack 라이브러리에서는 크게 삽입, 삭제, 조회, 검색 을 지원해준다.

Oracle Stack document

Method	content	return
empty()	Stack이 비어있는지 체크	boolean 타입 반환
peek()	Stack의 헤드 data 반환	성공시 return Data 만약 Stack이 비어있을 경우 throw EmptyStackException
push(E data)	Stack에 data 추가	성공시 return data
pop()	Stack의 헤드 데이터 삭제	성공시 return data 만약 Stack이 비어있을 경우 throw EmptyStackException
search(Object o)	Stack의 데이터 검색	성공시 head 부터 시작하여 data의 위치를 반환(int형) 실패시 즉, 데이터가 없을 경우 return -1

백준 9012번 괄호 Java

https://www.acmicpc.net/problem/9012

문제

괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.

여러분은 입력으로 주어진 괄호 문자열이 VPS 인지 아닌지를 판단해서 그 결과를 YES 와 NO 로 나타내어야 한다.

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.

출력

출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.

예제 입력 1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

예제 출력 1

NO
NO
YES
NO
YES
NO

Code

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.io.IOException;

public class Main{
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());

        for(int i = 0; i < T; i++){
            Stack<String> stack = new Stack<>();

            String temp = br.readLine();

            for(char c : temp.toCharArray()){
                if(!stack.isEmpty() && stack.peek().equals("(") && Character.toString(c).equals(")")){
                    stack.pop();
                } else {
                    stack.add(Character.toString(c));
                }
            }

            if(stack.isEmpty()){
                sb.append("YES" +"\n");
            } else{
                sb.append("NO" + "\n");
            }
        }
        System.out.println(sb);
    }
}

Point

그리 어렵지 않은 문제이다.

매우 간단하게 괄호가 닫힌다고 생각하면 된다.

주어지는 괄호의 문자열을 Stack에 집어 넣으면서 stack.peek()를 통해 head와 들어올 괄호를 비교하여,
head가 '(' 이고, 다음 문자열이 ')' 이면 stack.pop()을 해버리면 된다.

그렇게 해당 문자열에 대한 반복문이 끝났을 때, stack.empty()를 통해 stack이 비어있다면 모든 괄호들이 정상적으로 이루어져 있다고 볼 수 있다.