[JAVA] Stack 알고쓰자!

*** 자바에서는 기본적으로 Stack클래스를 지원해주지만, 기본적인 Stack의 구조를 알고 쓰고자 작성하였습니다.

1. 스택(Stack)

스택은 사전적인 의미로 "쌓다"라는 의미를 가지고 있습니다. 스택은 선출후입(LIFO)의 자료구조를 가지며, 접근이 목록의 끝(Top 또는 Top Pointer)에서만 일어나기 때문에 Pushdown List 라고도 합니다. 스택에서 입력은 push, 출력은 pop, Top 위치의 데이터 확인은 peek 를 사용합니다.

• LIFO(Last In First Out)
  한쪽에서만 자료를 넣고 뺄수 있는 구조로, 나중에 들어온 데이터가 먼저 나가는 구조로 되어있습니다.

스택이 실제로 사용되는 경우

• 운영체제(OS: Operating System)
  프로그램에서 사용되는 함수들을 스택 자료형에 저장하여 사용합니다.
• 컴파일러(Compiler)
  수학 기호들을 기계어로 변환시 사용합니다. (괄호 등을 매칭하는 경우)
• 자바 가상 머신(JVM: Java Virtual Machine)
  JVM 내에서 메서드가 실행, 종료될 때 스택 프레임을 이용하여 관리합니다.

1.1 스택의 구현

다음은 일반적으로 스택에 사용되는 필수적인 메서드들입니다.

• pop
  스택의 가장 최상위(마지막)에 위치한 데이터를 추출한 후에 스택에서 삭제합니다.
• push
  스택의 가장 최상위(마지막)에 데이터를 삽입합니다.
• isEmpty
  스택이 empty 상태인지 확인합니다.
• clear
  스택에 저장된 모든 데이터를 삭제하고 스택을 초기화합니다.
• peek
  스택의 가장 최상위(마지막)에 위치한 데이터를 추출합니다.
  pop 메서드와는 달리 스택에서 데이터를 삭제하지 않습니다.

• BOJ 10828 (스택) - 배열을 이용한 스택 구현
  https://www.acmicpc.net/problem/10828

import java.io.*;
import java.util.ArrayList;


class Stack{
    private int arr[];
    private int top;
    private int capacity;

    Stack(int size){
        arr = new int[size];
        capacity = size;
        top = -1;
    }

    public int push(int x) {
        if(isFull()){
            System.exit(-1);
        }
        arr[++top] = x;
        return x;
    }

    public int pop(){
        if(isEmpty() == 1){
            return -1;
        }
        return arr[top--];
    }
    public int peek(){
        if(isEmpty() != 1)
            return arr[top];
        else
            return -1;
    }
    public int size(){
        return top + 1;
    }
    public int isEmpty(){
        if(top == -1) {
            return 1;
        }
        else
            return 0;
    }
    public boolean isFull() {
        return top == capacity -1;
    }

    public void clear() {
        arr = null;
        top = -1;
    }
}


class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());

        Stack stack = new Stack(n);



        for(int i=0;i<n;i++){
            String str = br.readLine();
            if(str.contains(" ")){
                int X = Integer.parseInt(str.split(" ")[1]);
                stack.push(X);
            }

            else{
                switch(str) {
                    case "top" :
                        bw.write(stack.peek() + "\n");
                        break;
                    case "size" :
                        bw.write(stack.size() + "\n");
                        break;
                    case "empty" :
                        bw.write(stack.isEmpty() + "\n");
                        break;
                    case "pop" :
                        bw.write(stack.pop() + "\n");
                        break;
                }
            }
        }
        bw.flush();
        bw.close();


    }
}

출처 : https://freestrokes.tistory.com/82