Stack 스택 / 괄호검사 / DFS / 후위표기법

1. Stack 개요

Stack이란?

: 물건을 쌓아올린 형태의 자료구조. 자료가 일렬로 놓인 선형 자료구조.

- 마지막에 추가된 자료가 먼저 나오는 후입선출 자료구조 (Last In First Out)

• ** top : 스택의 꼭대기가 배열의 어디에 해당하는지를 판단하기 위한 변수 (초기값 -1)
• 스택에 데이터를 추가 : push(a) >> top의 크기를 하나 증가시킨 뒤 arr[top]에 a 할당.
• 스택에서 데이터 회수 : pop() >> arr[top]의 값을 반환, top의 크기 하나 감소.
• 스택이 비어있는지 확인 : isEmpty >> 빈스택인 경우 -1.
• 스택의 제일 위의 데이터 확인 : peek() >> top을 감소시키지 않고 arr[top]의 값 반환.
• 스택이 가득 차 있는지 확인 (고정된 배열을 사용하는 경우) : isFull

 

- 스택 코드

// int 데이터를 스택의 형태로 관리할 수 있는 클래스 만들어보기
public class MyStack {
    public static void main(String[] args) {
        MyStack intStack = new MyStack();
        System.out.println(intStack.isEmpty());
        intStack.push(10);
        intStack.push(20);
        intStack.push(30);
        System.out.println(intStack.isEmpty());
        System.out.println(intStack.isFull());
        System.out.println(intStack.pop());
        System.out.println(intStack.pop());
        System.out.println(intStack.peek());
        System.out.println(intStack.pop());
        System.out.println(intStack.isFull());
    }
    // top
    private int top=-1;
    // 배열
    private final int[] arr = new int[3];

    // 데이터 넣기
    // x를 스택의 제일 위에 넣는다.
    public void push(int x) {
        if (top < arr.length) {
            this.top++;
            arr[this.top] = x;
        } else {
            throw new RuntimeException("stack is full");
        }
    }

    // 데이터 회수
    public int pop() {
        if (this.isEmpty()) {
            throw new RuntimeException("stack is empty");
        }
        int value = arr[top];
        top--;
        return value;
    }

    public int peek() {
        if (this.isEmpty()) {
            throw new RuntimeException("stack is empty");
        }
        int value = arr[top];
        return value;
    }

    // 비어있는지 확인
    // top이 -1이면 true 비어있다는 뜻
    public boolean isEmpty() {
        return top==-1;
    }

    // 가득 차있는지 확인
    public boolean isFull() {
        return top==arr.length-1;
    }

}

 

-Call Stack

: 프로그래밍 언어의 함수 호출 및 복귀 순서 관리.

1) 프로그램 실행 중 함수 (or 메서드)를 호출하게 될 경우, 해당 함수에 필요한 지역변수, 매개변수 및 수행 후 복귀할 주소를 스택 프레임의 형태로 시스템 스택에 저장한다.

2) 함수 호출이 끝날 경우 스택 프레임이 pop()되고, 저장되어 있 복귀 주소로 복귀.

- main() 호출 -> 복귀지점(A) + firstMethod() 호출 -> 복귀지점(B) + secondMethod() 호출 -> secondMethod()로 갔다가 호출 끝난 후 pop하면서 복귀지점(B)로 이동. -> 다시 firstMethod() 호출 끝난 후 pop하면서 복귀지점(A)로 이동. -> main호출 끝.

 

** StackOverflow 발생 이유 : 재귀함수를 호출하는 과정에서 정상적인 종료를 하지 못하고 무한히 재귀하게 될 경우... Call stack이 너무 높이 쌓여 프로그램에 할당된 메모리 영역을 벗어날 때 발생하는 에러.

 

2. 괄호 검사

: 주어진 수식의 괄호가 알맞게 작성되었는지 확인하는 괄호 검사.

> 제일 앞에서부터 문자 확인하며

 

1) 여는 괄호가 나올 경우 스택에 push

2) 닫는 괄호가 나올 경우

- 스택이 비어있을 경우 -> 실패

- 스택이 비어있지 않을 경우 -> 스택에서 pop.

3) 모든 문자를 조사했을 때

- 스택이 비어있지 않을 경우 -> 실패

- 스택이 비어있는 경우 -> 성공 

 

 

 

 

3.  DFS (Depth First Search) 깊이 우선 탐색

: 그래프를 비롯한 비선형 자료구조에서 모든 자료를 빠짐없이 검색하는 방법 중 하나.

>> 한쪽 갈림길을 택하면서 갈 수 있는 최대한 깊이 들어가면서 그래프를 탐색. ~ 더이상 갈 길이 없는 상황에서 마지막으로 갈림길이 나왔던 지점으로 돌아간다.... >> 마지막 지점이니까! 스택을 활용해야 한다.

 

1) 시작 지점을 결정하고 스택에 push.

2) 이동할 때마다 pop (즉, 시작점 방문했다라는 표시)

3) 시작 지점의 인접점들을 스택에 push.

4) 다음 이동할 때 pop

6) pop한 점의 인접점들을 스택에 push.

7) 계속 반복 

8) 인접점들이 이미 방문했으면 그냥 pop.

9) 반복하다보면 스택이 비게 된다.

>> pop한 순서가 방문 순서.

 

즉,

> 방문할 데이터 자체를 표시할 곳이 필요하고, (int[][] 2차원 배열 혹은 인접행렬 리스트)

    얘네를 push하고, pop할 stack이 필요하고,

    pop한 점을 담을 곳이 필요하고, 

    push했다가 pop한 결과를 방문했다고 표시할 수 있는 boolean[] 배열이 필요하다. (방문 확인용)

 

- DFS 코드

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// 깊이우선탐색
public class DepthFirstSearch {
    public static void main(String[] args) {
        String[] edges = { // 연결 정보
                "1 2",
                "1 3",
                "2 4",
                "2 5",
                "3 7",
                "4 6",
                "5 6",
                "6 7"
        };

        // 총 점의 개수
        int nodeCount = 7;
        // 각 점이 연결되었는지를 판단하기 위한 배열
        int[][] map = new int[nodeCount+1][nodeCount+1];

        //  주어진 연결 정보를 바탕으로 map을 채워 넣는다. 연결되어 있다면 1
        // 1. 주어진 선의 갯수만큼 반복
        for (int i=0; i< edges.length; i++) {
            // 하나의 정보를 나누어서 출발 종점을 구분해 각각 변수에 할당
            String[] edgeInfo = edges[i].split(" ");

            int leftNode = Integer.parseInt(edgeInfo[0]);
            int rightNode = Integer.parseInt(edgeInfo[1]);

            // 각각의 정점의 map[left][right] = 1로 넣어줌
            map[leftNode][rightNode] = 1;
            map[rightNode][leftNode] = 1;
        }

        // 다음 방문할 곳을 기록하기 위한 스택 하나
        Stack<Integer> toVisit = new Stack<>();

        // 방문한 순서를 살펴보기 위한 리스트 하나 (pop한점)
        List<Integer> visitOrder = new ArrayList<>();

        // 내가 방문했는지를 파악하기 위한 배열 하나 (방문 확인용)
        boolean[] visited = new boolean[nodeCount+1];

        // DFS 시작
        // 1. 가장 먼저 방문할 곳을 넣어둔다.
        toVisit.push(1);

        // 2. 반복한다. 스택이 빌 때까지 (더이상 방문할 곳이 없을 때)
        while(!toVisit.empty()) {
            // 3. 다음 방문할 곳을 pop한다.
            int next = toVisit.pop();
            // 4. 방문했는지를 visited로 확인해서 방문했다면 다음 곳으로 넘어간다.
            if (visited[next]) continue;

            // 미방문이면 이제 표시한다.
            visited[next] = true;

            // 5. 방문 순서 기록
            visitOrder.add(next);

            // 6. 다음 방문 대상을 stack에 push
            for(int i=nodeCount; i>=0; i--){
                // 만약 방문했다면 추가하지 않고,
                // 도달할 수 있다면 추가한다.
                if (visited[i]) continue;
                if (map[next][i] == 1) {
                    toVisit.push(i);
                }
            }
        }

        // 방문 순서 확인
        System.out.println(visitOrder);
    }
}

 

 

 

4. 후위표기법

- 일단 평소에 피연산자 사이에 연산자가 오는 형태가 중위 표기법이다. > 인간 중

ex. 5 + 3 * 1 + (4 - 9) * 3

 

컴퓨터 입장에서는 입력을 순서대로 받아서 순서대로 해석하기 때문에 중위 표기법을 후위 표기법으로 변환하는 것이 좋다.

> 스택을 활용해 후위 표기법으로 표현된 식을 계산한다.

ex. 531*+49-3*+

 

>> 이제 이 식을 스택을 활용해 계산해보자.

1) 수식의 문자를 하나씩 검색해보며

2) 문자가 피연산자(숫자)면 스택에 push

3) 이 결과를 다시 스택에 push.

4) 반복 > 마지막에 스택에 남은 것이 연산 결과

 

 

1)피연산자(숫자) stack에 push()

push(5)

push(3)

push(1)

 

 

2) 연산자(*)를 만나 pop() 두번

pop1 > 결과 1

pop2 > 결과 3

(3*1) 연산하기 > 연산 결과를 스택에 push

push(3)

 

3) 다시 연산자(+)를 만나 pop() 두번

pop1 > 결과 3

pop2 > 결과 5

(5+3) 연산하기 > 연산결과를 스택에 push

push(8)

 

 

4) 피연산자(숫자) stack에 push

push(4)

push(9)

 

 

 

5) 연산자(-)를 만나 pop() 두번 > 결과 9와 4

(4-9) 연산하기 > push(-5)

 

6) 다음 피연산자 push

push(3)

 

 

7) 연산자(*)를 만나 pop() 두번 > 결과 3과 -5

(-5*3) 연산 > push(-15)

 

8) 연산자(+)를 만나 pop() 두번 > 결과 -15와 8

(-15+8) 연산 > push(-7)

 

 

9) 마지막에 스택에 남은 것이 연산 결과

 

 

 

 

 

 

- 코드 짜보기

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

// 후위표기법
public class SuffixCalculation {
    // 연산자에 따라 값을 계산하는 메서드
    public int calculate (int left, int right, char operator) {
        switch (operator) {
            case '+': return left+right;
            case '-': return left-right;
            case '*': return left*right;
            case '/': return left/right;
            default: throw new IllegalArgumentException("invalid operator");
        }
    }

    public void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();

        Stack<Integer> numStack = new Stack<>();

        for(int i=0; i<input.length(); i++) {
            char next = input.charAt(i);

            // 현재 문자가 숫자면?
            if (Character.isDigit(next)) {
                //스택에 넣어준다.
                numStack.push(next-'0'); // 여기서 숫자 0을 빼면 char를 Integer로 바꿔준다.
            } else { // 숫자가 아니라 연산자라면 pop 두번
                int rightNum = numStack.pop();
                int leftNum = numStack.pop();

                // 그 후 계산하고 push
                int calculatedResult = calculate(leftNum, rightNum, next);
                numStack.push(calculatedResult);
            }
        }
        System.out.println(numStack.pop());
    }

    public static void main(String[] args) throws IOException{
        new SuffixCalculation().solution();
    }
}