스택

아침을 감기약 먹고 시작했다.
졸리다

---

자료구조 - 스택

특성

후입선출(LIFO) 구조를 갖는 자료구조
들어온 순서의 역순으로 출력하는 구조.
가장 대표적인 LIFO 구조이다.

또한, 자료 간 1대1 관계를 갖는 선형 구조를 가지고 있다.

주요 연산

• push : 저장소에 자료를 저장.(삽입)
• pop : 저장소에서 자료를 꺼냄. (삭제)
  • 꺼낸 자료는 삽입한 자료의 역순으로 꺼냄
  • 꺼냄과 동시에 스택에서 삭제됨.
• peek : 스택의 top에 있는 item을 반환. (삭제 X)

삽입/삭제 과정

관련 문제 #1

https://www.acmicpc.net/problem/9012
괄호라는 실버4 문제다.
여는 괄호는 스택에 넣고 닫는 괄호는 스택의 top과 비교하며 다르면 실패 같으면 pop하는 전형적인 스택문제.

코드

import java.io.*;
import java.util.Stack;

/**
 * (())())
 * (((()())()
 * (()())((()))
 * ((()()(()))(((())))()
 * ()()()()(()()())()
 * (()((())()(
 */

public class Main {

    static int T;
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        while(T > 0){
            // 괄호
            String brackets = br.readLine();

            // 로직
            search(brackets);
            T--;
        }
        System.out.println(sb);
    }

    public static void search(String brackets){
        Stack<Character> stack = new Stack<>();

        boolean flag = true;

        for (int i = 0; i < brackets.length(); i++) {
            // 여는 괄호
            if (brackets.charAt(i) == '(') stack.push(brackets.charAt(i));
            // 닫는 괄호
            else{
                // 0. 스택이 비어있냐
                if(!stack.isEmpty()){
                    // 1. 제일 위에 있는 괄호와 비교한다.
                    // 짝이 맞다.
                    if(stack.peek() == '(') stack.pop();
                    // 짝이 아니다.
                    else{
                        flag = false;
                        break;
                    }

                }else{
                    flag = false;
                    break;
                }
            }
        }
        if(stack.isEmpty() && flag) sb.append("YES").append("\n");
        else sb.append("NO").append("\n");
    }
}

관련 문제 #2

괄호 외에도 후위 표기식을 계산하는 방법에도 스택을 활용할 수 있다.

후위 표기식이란, 연산자를 제일 뒤에 표기하는 방식이다.
예를 들어, A + B를 후위 표기식으로 변환하면, AB+로 표현할 수 있다. 이러한 식을 계산할 때, 스택을 활용하면 매우 간단하게 계산할 수 있다.

코드

public class PostExpressionTest {
	public static void main(String[] args) {
		String expression = "6528-*2/+"; // 이렇게 후위표기식이 올바르다는 것을 전재로 시행한다.
		System.out.println(expression);
		
		Stack<Integer> stack = new Stack<>();
		for(int i = 0; i < expression.length(); i++) { // 후위 표기식을 돌면서
			char temp = expression.charAt(i);
			
			// 피연산자면 스택에 저장
			if(Character.isDigit(temp)) {
				stack.push(temp - '0');
			} else { // 연산자를 만나면 두 피연산자를 꺼내어 계산 후 다시 스택에 저장
				int n2 = stack.pop();
				int n1 = stack.pop();
				
				if(temp == '+') stack.push(n1 + n2);
				if(temp == '-') stack.push(n1 - n2);
				if(temp == '*') stack.push(n1 * n2);
				if(temp == '/') stack.push(n1 / n2);
			}
		}
		
		
		// 모든 연산이 끝나면, 스택에 값이 저장됨.
		System.out.println(stack.peek());
	}
}