스택

자바에서 stack, ArrayList를 이용할 수 있으나 문제에선 입력수가 많기 때문에 ArrayDeque를 이용해준다.

스택에서 중요한 매서드는 push, pop, get, size가 있다. 그 중 push, pop이 중요한데 당연히 ArrayDeque에 구현이 되어 있다.

백준(스택2) 문제를 통해 스택의 매서드를 구현해보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(br.readLine());
        ArrayDeque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int command = Integer.parseInt(st.nextToken());

            switch (command) {
                case 1:
                    int num = Integer.parseInt(st.nextToken());
                    stack.push(num);
                    break;
                case 2:
                    if (stack.isEmpty()) {
                        sb.append(-1).append("\n");
                    } else {
                        sb.append(stack.pop()).append("\n");
                    }
                    break;
                case 3:
                    sb.append(stack.size()).append("\n");
                    break;
                case 4:
                    sb.append(stack.isEmpty() ? 1 : 0).append("\n");
                    break;
                case 5:
                    sb.append(stack.isEmpty() ? -1 : stack.peek()).append("\n");
                    break;
            }
        }

        System.out.println(sb);
        br.close();
    }
}

빠른 실행 속도를 위해서 Bufferredeader, StringBuilder, StringTokenizer를 이용해준다.

스택은 후입선출로 군필자들은 탄창을 생각하면 된다. 탄창에 총알을 집어 넣으면 마지막에 삽입된 총알이 제일 먼저 발사된다. 탄창에 총알을 집어 넣을 때 마다 총알은 제일 위쪽에 저장되고 발사도 탄창의 제일 위 총알이 발사된다. 그리고 총이 탄창에 접근할 때 탄창의 제일 아래쪽에서 접근못하고 무조건 제일 위쪽의 총알에만 접근가능 하다. 이 동작원리를 메서드로 구현한게 push(), pop()이다.

다르게 생각하면 정상적으로 꼬치요리를 먹는다고 생각하면 꼬치를 굽기전에 마지막으로 꽂은걸 제일 먼저 먹는다. 손잡이쪽부터 먹는 변태가 아니라면 아래쪽부터 순차적으로 식재료를 꽂고 제일 위쪽부터 먹으니 꼬치는 스택구조라고 볼 수 있다.

scanner
n = 100
[1][2]
[3]

[4] 백준 시스템 자체 입력 -> 하나씩 입력

n = 10000000
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ... 1000000000] 시스템이 한꺼번에 입력
저희가 "," 기준으로 split(",")