0x05강

Last updated - 2025년 06월 19일 Edit Source

5강에서는 스택이 무엇인지 알아보고 구현하는 시간을 가진다.

생각 정리
스택은 다양한 응용 사례 존재
수식의 괄호쌍
전위/중위/후위 표기법
DFS
Flood Fill

# 정의와 성질

스택 : 한 쪽 끝에서만 빼거나 넣을 수 있는 자료구조

LIFO (Last In First Out)

Restricted Structure
스택, 큐, 덱은 특정 위치에서만 넣거나 뺄 수 있는 제한이 걸려 있어서 Restricted Structure 라고도 함

배열을 이용해서 제일 상단이 아닌 나머지 원소들의 확인/변경이 가능하도록 기능을 만들 수는 있다
그러나, 그건 스택에서 제공하는 기능은 아니다
스택을 응용한 문제를 보면 결국 원소의 추가 / 원소의 제거 / 제일 상단 원소 확인 기능만을 필요로 함

# 기능과 구현

스택은 배열 / 연결리스트를 이용해 구현할 수 있으며, 배열을 이용하는게 더 쉽다

배열, 현재 위치를 가리키는 인덱스 2개만 필요
{13, 21, 30}을 표현하기 위해 dat[0], dat[1], dat[2]에 숫자를 썼고 pos는 3이라는 값을 가짐
pos의 값이 곧 스택의 길이, 스택 내의 원소의 수를 의미

뭐 pos가 0보다 커야한다 이런건 일단 생략했음
어차피 나중에 값이 들어오면 바꿔치기 할거니까 추가적인 연산없이 그냥 pos만 이전 위치로 이동시켰음

# BOJ 10828 (sol)

너무 쉬워서 패스

# BOJ 10773 (sol)

10773

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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));  
        int n = Integer.parseInt(br.readLine());  
  
        Stack<Integer> stack = new Stack<>();  
  
        while (n-- > 0) {  
            int target = Integer.parseInt(br.readLine());  
  
            if (target == 0 && !stack.isEmpty()) {  
                stack.pop();  
                continue;  
            }  
  
            stack.push(target);  
        }  
  
        int sum = 0;  
        int stackSize = stack.size();  
  
        while (stackSize-- > 0) {  
            sum += stack.pop();  
        }  
  
        System.out.println(sum);  
    }  
}

Comment