스택(Stack)

배열(Array)과 연결리스트(LinkedList)를 잘 이해했으면 스택을 이해하고 구현하는데 어렵지 않다.  

위키백과(https://ko.wikipedia.org/wiki/%EC%8A%A4%ED%83%9D)에 보면 스택에 대해 이렇게 설명하고 있다.

 

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이이다.
그 접근 방법은 언제나 목록의 끝(last)에서만 일어난다. (자료접근시 중간에 접근하는 일이 없고 항상 끝에서만 일어난다는 소리다.)스택은 한 쪽 끝에서만 자료를 넣거나(push) 뺄 수(pop) 있는 구조로 되어 있고 이런 걸 선형 구조(LIFO - Last In First Out)으로 되어 있다라고 말한다. 자료를 넣는 것을 '밀어넣는다' 하여 푸시(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 보관한 자료부터 나오게 된다.
즉 , 가장 늦게 들어간 자료가 가장 빨리 나온다는 말이다. 

 

글로는 감이 안올수 있으니 예를들어 보자.

 

• 처음 빈 스택에 1을 넣는다(PUSH).  stack = { 1 } 
• 스택에 2를 넣는다.(PUSH) statck = { 1, 2} 
• 스택에 3을 넣는다.(PUSH) statck = { 1, 2, 3}  
• 이제 스택에서 하나를 뺀다(POP). 스택에 가장 늦게 들어간 것이(Last In)이 3이니 3이 스택에서 빠진다.(First Out) . stack = { 1, 2 }
• 하나를 더 뺀다.(POP). 2가 빠지면서 stack = {1}
• 하나를 더 뺀다.(POP) 1이 빠지면서 statck = {} 이 된다. 

구현은 보통 배열이나 연결리스트로 쉽게 구현할수 있고 자바 컬렉션에 Stack<> 클래스가 built-int 되어 있다. C++ 은 stl:statck 이 있음.

그럼 프로그래밍시 스택이 유용하게 사용될 만한 것은 무엇이 일을까? 고민하다가 백준 코딩테스트 문제중 스택에 관련된것을 풀어보면서 

스택에 대해서 좀더 이해하도록 하자.

 

---

백준 9012 - 괄호 문제 : 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”를 한 줄에 하나씩 차례대로 출력해야 한다. 

입력	출력
6 (())()) (((()())() (()())((())) ((()()(()))(((())))() ()()()()(()()())() (()((())()(	NO NO YES NO YES NO

해설

문제를 해결하기위한 키는 ( 열린 괄호는 항상  닫힌 괄호 ) 와 쌍을 이루어야 한다는 것이고 나중에 열린(PUSH딘) 괄호 ( 가 정상적인 문법이라고 하면 가장 먼저 닫힌 괄호 ) 가 나와야(POP) 되어야 올바른 괄호 문자열(Valid PS, VPS)이 성립되어 YES가 된다는것이다.

VPS를 판단하기위해 어떤 자료구조가 가장 잘 어울릴까 ? 바로 스택이다. 

입력된 문자열 캐릭터를 하나씩 비교해가면서 열린 괄호는 ( 가 나타나면 스택에 PUSH해주고 닫힌 괄호 )가 나타나면 스택에서 POP하여 최종적으로 스택이 비워져(empty)있으면 YES를 그렇치 않으면 NO를 출력하면된다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        final Stack<Character> stack = new Stack<>();
        int N = Integer.parseInt(br.readLine()); // test case 가 몇개인지 읽어온다.
 
        // test case 만큼 루프를 돌면서 VPS를 판단한다.
        for(int i = 0 ; i < N ; i++) {
            stack.clear();
            boolean VPS = true;
            String testCase = br.readLine();
            int length = testCase.length();
            for(int c = 0 ; c < length ; c++) {
                char ch = testCase.charAt(c);
                if(ch == '(') {
                    stack.push(ch);
                }
                else if(ch == ')') {
                    // 만약 닫힌괼호인데 pop 할게 없으면 NOT VPS 이다.
                    if(stack.isEmpty()) {
                        VPS = false;
                        break;
                    }
                    stack.pop();
                }
            }
 
            // VPS가 true 이면 최종적으로 스택이 empty 상태이여야 한다.
            if(VPS) {
                VPS = stack.isEmpty() == true;
            }
            System.out.println(VPS ? "YES" : "NO");
 
        }
 
    }
}

 

레퍼런스

• 백준 9012 - 괄호 문제 : https://www.acmicpc.net/problem/9012