자료구조) Stack, Queue (스택, 큐)

Stack (스택)

• LIFO (Last In First Out)
• push, pop(반환,제거), peek(반환), search ...

• 배열 or 연결리스트를 이용한 구현 > 자바는 기본 라이브러리로 스택 제공
• 이용) 역순 문자열 만들기, 시스템 스택(함수 호출,복귀 관리), 수식의 괄호검사, 수식의 후위표기법 등 ..

Input	Output
첫 줄에 명령어의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000) 두번째 줄부터 N개의 줄에 걸쳐 아래의 명령어가 입력됩니다. push x : x를 스택에 삽입합니다. pop : 가장 마지막에 들어온 인자를 반환합니다. size : 큐의 크기를 출력합니다. top : 큐의 맨 앞 인자 값을 출력합니다.	각 명령 순서에 따라 값을 출력합니다.

import java.util.*;

public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        Stack<Integer> st = new Stack<>();

        for (int i = 0; i < N; i++) {
            String cmd = scanner.next();
            if (cmd.charAt(0) == 's') {
                System.out.println(st.size());
            } else if (cmd.charAt(0) == 'p') {
                if (cmd.charAt(1) == 'u') {
                    int val = scanner.nextInt();
                    st.push(val);
                } else if (cmd.charAt(1) == 'o') {
                    System.out.println(st.pop());
                }
            } else if (cmd.charAt(0) == 't') {
                System.out.println(st.peek());
            }
        }
    }
}

---

Queue (큐)

• FIFO (First In First Out)
• enqueue, dequeue
• offer/add(삽입), poll(반환,제거), peek/element(반환), remove(제거) ...

• 배열 or 연결리스트를 이용한 구현 > 자바는 기본 라이브러리로 큐 제공
• 이용) OS와 각종 시스템에서의 작업 큐들 ..

Input	Output
첫 줄에 명령어의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000,000) 두번째 줄부터 N개의 줄에 걸쳐 아래의 명령어가 입력됩니다. enqueue x : x를 큐에 삽입합니다. dequeue : 가장 먼저 들어온 인자를 반환합니다. size : 큐의 크기를 출력합니다. front: 큐의 맨 앞 인자 값을 출력합니다.	각 명령 순서에 따라 값을 출력합니다.

import java.util.*;

public class Test {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        Queue<Integer> q = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            String cmd = scanner.next();
            if (cmd.charAt(0) == 's') {
                System.out.println(q.size());
            } else if (cmd.charAt(0) == 'e') {
                int val = scanner.nextInt();
                q.offer(val);
            } else if (cmd.charAt(0) == 'd') {
                q.poll();
            } else if (cmd.charAt(0) == 'f') {
                System.out.println(q.peek());
            }
        }
    }
}

---

Deque (Double-ended Queue) (덱)

양쪽에서 삽입/삭제가 가능한 큐로, 스택과 큐의 성질을 모두 갖고 있다.