🗄️[자료구조] Stack

1. Stack

LIFO : 마지막으로 들어간 것, 가장 먼저 나옴
pop()
push()
peak() : 마지막 데이터를 확인
isEmpty()

import java.util.EmptyStackException;

class Stack<T> {//객체를 만들 때 데이터 타입을 명시
    class Node<T> { //같은 타입을 갖는 노드 선언
        private T data; //데이터 선언
        private Node<T> next; //다음 노드 선언

        public Node(T data){
            //생성자에서 해당 타입의 데이터를 받아 내부변수에 저장
            this.data = data;
        }
    }

    private Node<T> top;

    public T pop() {//top에서 데이터를 가져옴
        if (top==null) {
           throw new EmptyStackException();
        }
        T item = top.data;
        top = top.next; //pop 이후 다음 데이터를 top으로 바꿔줌
        return item;
    }

    public void push(T item) {
        Node<T> t = new Node<T>(item); //받은 item으로 노드 생성
        t.next = top; //이전의 top 내려주기
        top = t;
    }

    public T peek() {//마지막 데이터를 확인
        if( top == null ){
            throw new EmptyStackException();
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null; 
    }
}
public class stackJava {
    public static void main(String[] args) {
        //코드확인
        Stack<Integer> s = new Stack<Integer>();
        s.push(1);
        s.push(2);
        s.push(3);
        s.push(4);
        System.out.println(s.pop());
    }
}

2. Multi Stack

1) 고정길이

stack2_easy.java

import java.util.EmptyStackException;
import java.lang.Exception;

/**
 * Innerstack2_easy
 */
class FullStackException extends Exception {
    public FullStackException() {
        super();
    }
    public FullStackException (String msg){
        super(msg);
    }
}

class FixedMultiStacks { //고정길이 multi Stack
    private int numOfStacks = 3; //stack을 3분할
    private int stackSize;
    private int[] values; //실제 데이터
    private int[] sizes; //각 스택의 데이터 size

    public FixedMultiStacks (int stackSize){ //생성자
        this.stackSize = stackSize; //stackSize 를 받고, 내부변수에 저장
        this.sizes = new int[numOfStacks]; //스택의 개수만큼 데이터 사이즈를 저장할 배열 생성
        this.values = new int[numOfStacks * stackSize]; //실제 데이터를 저장할 공간 생성
    }

//내부함수
    public boolean isEmpty(int stackNum) {
        //stack에 데이터가 있는지 확인; 각 stack별로 따로 알려줘야함
        // < 인자로 몇 번째 stcak인지 받아야 함
        return sizes[stackNum] == 0; 
        //데이터를 저장한 공간= sizes, size에서 stackNum이 0인지 확인
    }
    public boolean isFull(int stackNum){
        //stack이 다 찼는지
        return sizes[stackNum] == stackSize;
    }
    public int getTopIndex(int stackNum){
        //stack 가장 위의 데이터와 방번호를 가져옴
        int offset = stackSize * stackNum;
        int size = sizes[stackNum]; //현재 데이터가 얼마나 차있는지
        
        return offset + size -1; //방번호는 0부터 시작하니까~
    }

    public void push(int stackNum, int data) throws FullStackException
    {
        if (isFull(stackNum) ){//다 차있으면 예외
            throw new FullStackException();
        }
        //공간이 남아있음 +1 후 데이터 추가
        values[getTopIndex(stackNum) + 1] = data;
        sizes[stackNum]++;
    }
    public int pop(int stackNum){
        if (isEmpty(stackNum) ){//비어있는지 확인
            throw new EmptyStackException();
        }
        int top = getTopIndex(stackNum); //몇 번 방에서 데이터를 가져와야 하는지 방 번호 획득
        int data = values[top];
        values[top] = 0;//공간 비워줌
        sizes[stackNum]--;
        return data;
    }
    public int peek(int stackNum){//확인
        if (isEmpty(stackNum)){
            throw new EmptyStackException();
        }
        return values[getTopIndex(stackNum)];
    }
}
public class stack2_easy {
    public static void main(String[] args) {
        FixedMultiStacks ms = new FixedMultiStacks(5); //stacksize=5
    
        //데이터를 push할 때 FullstackException 발생 가능
        try {
            ms.push(0, 1);
            ms.push(0, 2);
            ms.push(0, 3);
            ms.push(0, 4);
            ms.push(0, 5);
            ms.push(0, 5);//fullStackException으로..
        } catch (FullStackException e) {//5개 이상 넣으면 exception
            System.out.println("It's full.");
        }

        try {
            System.out.println(ms.pop(0)); //5
            System.out.println(ms.peek(0));
            System.out.println(ms.pop(0));//4
            System.out.println(ms.isEmpty(0));
            System.out.println(ms.pop(0)); //3
            System.out.println(ms.pop(0));//2
            System.out.println(ms.pop(0));//1
            System.out.println(ms.isEmpty(0));//True
            
        } catch (EmptyStackException e) {
            System.out.println("It's empty.");
        }
    }
    
}

2) 가변길이

유동적.. 코드가 조금 더 어려워용
고정길이 분할: 스택에 자리가 다 차버리면, 다른스택에 자리가 많아도 데이터를 추가 못함

데이터를 shift 하는 방식으로 진행
0️⃣-- 1️⃣1️⃣1️⃣ 2️⃣2️⃣-
0️⃣-- 1️⃣1️⃣1️⃣1️⃣ 2️⃣2️⃣
← 2데이터를 오른쪽으로 복사,복사해서 stack1 자리를 넓힘
← stack1의 크기 +1, 3→4
← stack2의 시작점+1, 크기 -1


여기서 더 추가하고 싶다면??
방을 원형 Que처럼 돌려서! stack0에 추가
0️⃣-- 1️⃣1️⃣1️⃣1️⃣ 2️⃣2️⃣
2️⃣0️⃣- 1️⃣1️⃣1️⃣1️⃣ 2️⃣2️⃣
← stack2의 크기+1
← stack0의 시작점 +1, 크기 -1

배열[방번호] = 배열[방번호-1] ← 앞의 데이터를 뒤로 밀도록, 자기 스택의 시작점 만나기까지 게속 돌림
❗️이 때, 2번방의 데이터를 어떻게 0번방에 넣는지?

✓ Modulo 의 Wrapping Around

Modulo : mod() 함수나 % 연산자 ← 정해진 영역을 벗어나지 못하게 하는 특성
0 1 2 3 4 방이 있을 때 5번방에 넣고싶은데 없음. 5%5(방갯수)=0 ← 0번 방에서 실행

가상의 index -1을 사용, max: stack 전체길이
-1 % max

stack2_dynam.java

3. 10828 문제풀이

//java로 stack 문제풀이
import java.util.EmptyStackException;
import java.util.Scanner;
import java.util.Stack;

//push X: 정수 X를 스택에 넣는 연산이다.
//pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
//size: 스택에 들어있는 정수의 개수를 출력한다.
//empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
//top: 스택의 가장 위에 있는 정수를 출력한다. 정수가 없는 경우에는 -1을 출력한다.



// class Stack<T> {//클래스 선언
// }

public class stack_10828 {
    public static void main(String[] args) {
//첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 
//둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다.

        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        Stack<Integer> stack = new Stack<Integer>();
        //push, pop, add, clear, peek, isEmpty, search
        int size=0;
        for (int i=0; i<N; i++){ //명령 받기
            String cmd = sc.next(); //단어만 입력받는다
            int cmdInt;
            
            if ("push".equals(cmd)) {
                cmdInt = sc.nextInt();
                stack.push(cmdInt);
                size++;
            }
            if ("pop".equals(cmd)) {
                if (stack.isEmpty() == true) {//스택이 비어있으면
                    System.out.println("-1");
                }
                System.out.println(stack.pop());
                size--;
            }
            if ("size".equals(cmd)) {
                System.out.println(size);
            }
            if ("empty".equals(cmd)) {
                if (stack.isEmpty() == true) {//스택이 비어있으면
                    System.out.println("-1");
                }
                else System.out.println("0");
            }
            if ("top".equals(cmd)) {
                System.out.println(stack.peek());
            }

        }

        sc.close();
    }
}

한번에 넣으면 실행이 안되구.. 런타임 에러가 뜬다..

[자료구조 알고리즘] Stack 구현하기 in Java https://youtu.be/whVUYv0Leg0?si=G_FnJjdjpXH8Bdk1
백준 자료구조 10828_Stack문제 https://www.acmicpc.net/problem/10828