Stack, Queue - (1)

📍 섹션5.스택, 큐 (Stack, Queue) 자료구조

Stack, Queue - (1)

• 스택과 큐는 배열에서 발전된 형태의 자료구조

🟨스택 Stack 후입선출(LIFO : Last-In-First-Out) 삽입과 삭제 연산이 ‘한 쪽’에서만 일어난다 top ← 삽입과 삭제 일어날 위치 지칭 push : 데이터 삽입 연산 pop : 데이터 삭제 후 확인 연산 peek : top 데이터 단순 확인용 ⇒ 스택은 ‘DFS (깊이우선탐색)’ 과 백트랙킹 에서 多 사용 🟨큐 Queue 선입선출(FIFO : First-In-First-Out) 삽입과 삭제 연산 ‘양방향’에서 일어난다 먼저 들어온 데이터가 먼저 나감 rear ← 큐의 가장 끝 데이터 지칭 (데이터 삽입) front ← 큐의 가장 앞 데이터 지칭 (데이터 삭제) 가장 먼저 들어온 데이터가 가장 먼저 삭제되기 때문 offer : 데이터 삽입 poll : 데이터 삭제 peek : 맨 앞 데이터 확인용 ⇒ 큐는 ‘BFS (너비우선탐색)’ 에서 多 사용 💡 cf. **‘우선순위 큐’**는 값이 들어간 순서와 상관없이 우선순위 높은 데이터가 먼저 나오는 자료구조‘우선순위 큐’ 는 일반적으로 힙(Heap)에 多 사용

---

5-1. 올바른 괄호 | 스택 사용

• [올바른 괄호] : 괄호의 쌍이 맞아야 함
• 스택 사용
• 1) 여는 괄호 만나면 push()
• 2) 닫는 괄호 만나면 pop()

⇒ 닫는 괄호 만나서 스택 pop 하기 전 비어있으면 X (닫는 괄호 多)

⇒ 끝났는데도 스택 데이터 남아있으면 X (여는 괄호 多)

⇒ 탐색이 끝나서 스택이 비었을 때만 쌍이 일치하는 거임

import java.util.Scanner;
import java.util.Stack;

/* 5-1. 올바른 괄호 // 스택 사용 
[입력]
첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 30이다.
[출력]
첫 번째 줄에 YES, NO를 출력한다.
*/
public class Main1 {
    //솔루션 함수
    public String solution(String str) {
        String answer = "YES";

        Stack<Character> stack = new Stack<>();
        //str 내부 탐색
        for(char x : str.toCharArray()) {
            if(x == '(') { //여는 괄호이면 
                stack.push(x);
            }else { //닫는 괄호인데 
                //pop 전에도 현 스택이 비어있는 상황이면 X
                if(stack.isEmpty()) return "NO";
                //아니면 현재 스택 top 데이터 pop
                stack.pop(); 
            }
        }
        //for 탐색 모두 돌고도 남아있는 것이 있으면 여는 괄호가 더 많은상태라 안됨 
        if(!stack.isEmpty()) return "NO";

        return answer;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main1 T = new Main1();
        Scanner kb = new Scanner(System.in);
        String str = kb.next();
        System.out.println(T.solution(str));
    }
}

5-2. 괄호 문자 제거 | 스택 사용

• 입력된 문자열 안에서 소괄호( ) 사이에 있는 모든 문자 제거하고 남은 문자만 출력하는 프로그램 작성
• 1) 여는 괄호, 알파벳 → push()
• 2) 닫는 괄호 → 스택 속 내용물이 여는 괄호 나올 때까지 pop()
• 3) for 탐색 빠져나온 후 남은 애들 answer에 stack.get(i) 시키면 답

import java.util.Scanner;
import java.util.Stack;

/* 5-2. 괄호문자 제거
[설명]
입력된 문자열에서 소괄호 ( ) 사이에 존재하는 모든 문자를 제거하고 
남은 문자만 출력하는 프로그램을 작성하세요.
*/
public class Main2 {
    //솔루션 함수
    public String solution(String str) {
        String answer = "";
        Stack<Character> stack = new Stack<>();
        //탐색
        for(char x : str.toCharArray())    {
            if(x == ')') { //닫는 괄호이면 여는 괄호 나올 때까지 pop
                while(stack.pop() != '('); //
            }else { //알파벳 , 여는 괄호이면 무조건 push
                stack.push(x);
            }
        }

        //for 탐색 모두 돌고 나와서 남아있는 애들이 살아남은 애들임 
        for(int i = 0; i<stack.size(); i++) {
            answer+=stack.get(i);//answer에 누적시킴
        }
        return answer;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main2 T = new Main2();

        Scanner kb = new Scanner(System.in);

        String str =kb.next();
        System.out.println(T.solution(str));
    }

}

5-3. 크레인 인형뽑기 (카카오 기출) | 스택 사용

🟨 2차원 배열 행크기, 열크기

1) 행 크기 : 배열.length

2) 열 크기 : 배열[0].length

import java.util.Scanner;
import java.util.Stack;

/* 5-3. 크레인 인형뽑기 (카카오 기출)*/
public class Main3 {
    //솔루션 함수 
    public int solution(int[][] board, int[] moves) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();

        //moves 탐색 : 크레인 위치
        for(int pos : moves) {
            //2차원 배열의 행크기만큼 돌면서 
            for(int i = 0; i<board.length; i++) {
                if(board[i][pos-1] != 0) { //인형 존재하는 경우, 뽑고 0으로 세팅
                    int tmp = board[i][pos-1];
                    board[i][pos-1] = 0;
                    //현재 인형이 기존 스택 top 데이터와 동일한 경우 터뜨려야 함
                    if(!stack.isEmpty() && tmp == stack.peek()) {
                        answer += 2; 
                        stack.pop();//꺼냄
                    }
                    else { //다른 인형이면 그냥 push
                        stack.push(tmp);
                    }
                    //담았든 터뜨렸든 
                    //각 크레인 내부 도는 i는 break 벗어나서 다음 크레인으로 이동
                    break;
                }
            }
        }
        return answer;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main3 T = new Main3();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int[][] board = new int[n][n];
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<n; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        int m = kb.nextInt();
        int[] moves = new int[m];

        for(int i = 0; i<m; i++) {
            moves[i] = kb.nextInt();
        }

        //출력
        System.out.println(T.solution(board, moves));
    }
}

5-4. 후위식 연산 (postfix) | 스택 사용

• 1) 숫자 만나면 push()
• 2) 연산자 만나면 pop() 2번
  • i) rt ← 먼저 pop() 한 값
  • ii) lt ← 나중 pop() 한 값
  • iii) lt 연산자 rt 의 결과값을 다시 push()
• 3) 모두 탐색 끝나면 stack.get()으로 answer 반환

import java.util.Scanner;
import java.util.Stack;

/* 5-4. 후위식 연산 (postfix)  */
public class Main4 {
    //솔루션 함수
    public int soluiton( String str) {
        int answer = 0;
        Stack<Integer> stack = new Stack<>();
        //탐색
        for(char x : str.toCharArray()) {
            if(Character.isDigit(x)) { //숫자 만나면
                stack.push(x-48); //숫자 변형 후 push
            }else { //연산자 만나면 
                int rt = stack.pop();
                int lt = stack.pop();
                if(x == '+') stack.push(lt + rt);
                else if(x == '-') stack.push(lt - rt);
                else if(x == '*') stack.push(lt * rt);
                else if(x == '/') stack.push(lt/rt);
            }
        }
        //탐색 끝나면 결과만 스택에 남아있다.
        answer = stack.get(0);    
        return answer;
    }

    //실행 메인 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Main4 T = new Main4();
        Scanner kb = new Scanner(System.in);

        String str = kb.next();
        System.out.println(T.soluiton(str));
    }
}