[JAVA] 자료구조 - 스택(Stack)

---

(1) 스택(Stack)

• 후입 선출(Last In First Out, LIFO) 자료구조: 마지막에 들어온 데이터가 먼저 나감
• == (First In Last Out, FILO)
• 데이터가 입력된 순서의 역순으로 처리되어야 할 때 사용
• ex) 함수 콜 스택, 수식 계산, 인터럽트(interrupt) 처리

함수 콜 스택

---

(2) 스택 기본 구조

• 후입 선출 구조
• 기본적으로 데이터 추가, 꺼내기, 스택 공간 확인으로 이루어짐
  • 데이터 추가(push): 스택의 가장 마지막 위치에 데이터 추가
  • 데이터 꺼내기(pop): 스택의 가장 마지막 위치에서 데이터 꺼냄

---

(3) JAVA 코드로 학습하기

---

(1) JAVA에서 제공하는 java.util.Stack 사용

// 선형 자료구조 - 스택
public class Main {
    public static void main(String[] args){
        Stack stack = new Stack();

        stack.push(1);  // (1) stack에 데이터 추가
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack);
        line();  // (+)line()함수는 static으로 만든 구분선 출력하는 함수

        System.out.println(stack.pop());  // (2) stack에서 데이터 한 개 꺼내기
        System.out.println(stack);
        line();

        stack.pop();
        System.out.println(stack);
        line();

        System.out.println("top을 출력해주지만 Pop은 하지않음(peek): "+stack.peek());  //(3) 데이터를 출력하지만 꺼내지 않음
        System.out.println(stack);
        line();

        System.out.println("contains: "+stack.contains(1));  // (4) stack에서 1을 포함하고 있는지 확인
        line();

        System.out.println("size: "+stack.size());  // (5) stack의 사이즈 출력
        line();

        System.out.println("empty: "+stack.empty());  // (6) stack이 비어있는지 확인
        line();

        stack.clear();  // null -> EmptyStackException
        System.out.println(stack);
    }
}

---

(2) ArrayList를 이용한 Stack 구현

//ArrayList를 이용한 스택 구현
class MyStack1{
    ArrayList list;  //저장할 리스트 공간 선언

    MyStack1(){
        this.list = new ArrayList();  //생성
    }

    // stack이 비어있는지 확인하는 함수
    public boolean isEmpty(){
        if(this.list.size() == 0){  //리스트의 사이즈가 0일 경우
            return true;
        }else {
            return false;
        }
    }

    // stack에 data 저장
    public void push(int data){
        this.list.add(data);  // MyStack1의 list 변수에 data 저장
    }

    // Stack에서 데이터 꺼내기
    public Integer pop(){
        if(this.isEmpty()){  //만약 비어있어서 꺼낼 데이터가 없는 경우
            System.out.println("stack is Empty");
            return null;
        }
        
        int data = (int) this.list.get(this.list.size() -1);  //현재 리스트의 총 사이즈-1(가장 뒤의 원소)
        this.list.remove(this.list.size()-1); // 지우고
        return data;  // 가장 뒤의 데이터 반환
    }
    
    // 가장 뒤의 원소를 가져오지만 삭제하지는 않음
    public Integer peek(){
        if(this.isEmpty()){  //리스트가 비어있을 경우
            System.out.println("stack is Empty");
            return null;
        }
        
        int data = (int) this.list.get(this.list.size() -1);  //현재 리스트의 총 사이즈-1(가장 뒤의 원소)
        return data;  //삭제하지는 않고 반환해줌
    }

    // 모든 원소를 출력하는 함수
    public void printStack(){
        System.out.println(this.list);
    }
}

---

(3) 배열을 이용한 Stack 구현

//배열을 이용한 기본 스택 직접 구현
class MyStack2{
    int[] arr;  //저장할 배열 선언
    int top = -1;  //배열의 마지막 부분의 위치를 체크하기 위한 변수

    MyStack2(int size){
        arr = new int[size];  //원하는 Stack 사이즈 만큼 배열을 생성함
    }

    // 배열이 비어있는지 확인하는 함수
    public boolean isEmpty(){
        if(this.top == -1){  //배열의 원소 중 마지막의 위치가 -1인 경우는 데이터가 존재하지 않는 경우
            return true;
        }else{
            return false;
        }
    }

    // 만든 크기의 배열에 원소가 모두 가득 한 경우를 확인하는 함수
    public boolean isFull(){
        if(this.arr.length-1 == this.top){  //원소의 마지막 위치를 가리키는 변수가 배열의 전체 길이-1을 가리킬 때
            return true;
        }else{
            return false;
        }
    }

    // 배열에 값을 넣는 함수
    public void push(int data){
        if(this.isFull()){  //가득 차있다면
            System.out.println("Stack if Full");
            return;
        }

        this.top +=1;  //위치 업데이트
        this.arr[this.top] = data;  //위치에 데이터 저장
    }

    // 마지막 위치에서 데이터 꺼내기 
    public Integer pop(){
        if(this.isEmpty()){  //데이터가 비어있는 경우
            System.out.println("Stack is Empty");
            return null;
        }

        int data = this.arr[this.top];  //현재 top위치에서 데이터 가져옴
        this.top -=1;  //top의 위치를 하나 아래로 내림
        return data;
    }

    //데이터를 꺼내지만 삭제는 하지 않는 함수
    public Integer peek(){
        if(this.isEmpty()){  //데이터가 비어있는 경우
            System.out.println("Stack is Empty");
            return null;
        }
        
        return this.arr[this.top];  //데이터를 보여주기만 함
    }

    // 배열의 모든 원소를 출력하는 함수
    public void printStack(){
        for (int i = 0; i < this.top+1; i++) {  //처음부터 현재 가리키는 위치까지 출력
            System.out.print(this.arr[i] + " ");
        }
        System.out.println();
    }
}