[Stack] Stack 구현해보기

 

스택 정리해놓은 글 

바로가기

 

 

근데 이제 기본제공하는 구조체 안쓰고 해보기

 

 

public class MyStack {

    private int[] stack;
    private int top;

    /**
     * 기본 생성자
     * stack 크기 = 10
     */
    public MyStack() {
        stack = new int[10];
        top=-1;
    }
    /**
     * 기본 생성자 2
     * stack 크기 받아서 생성
     */
    public MyStack(int size) {
        stack = new int[size];
        top=-1;
    }

    /** stack에 값 넣기 = push
     *  정수를 stack에 넣음
     *
     *  top에 1을 더하고
     *  stack의 길이 이상으로 push 하려하면 배열 늘려주고 push
     *
     * @param x
     */
    public void push(int x) {
        top = top+1;
        if(size() < stack.length) {
            stack[top] = x;
        } else {
            increaseStack();
            stack[top] = x;
        }
    }

    /** stack에서 값 빼기  = pop
     *  제일 마지막에 push된 정수를 반환
     * top 위치의 정수를 빼고 top을 -1 해주고 해당값 반환
     * @return
     */
    public int pop() {

        if(size() >= 0) {
            int temp = stack[top];
            stack[top--]=0;
            return temp;
        }
        else return -1;
    }
    /** stack이 비었는지 확인
     *  top이 0보다 작으면 비어있는것 return true
     *  top이 0보다 크거나 같으면 비어있지 않은것 return false
     * @return
     */
    public boolean isEmpty() {
        return top < 0;
    }

    /** stack의 크기 확인
     *  크기를 int로 반환
      * @return
     */
    public int size() {
        return top;
    }

    /**
     * 스택의 내용을 출력해주는 함수
     */
    public void print() {
        System.out.println("┌─────┐");
        for(int i=top; i>=0; i--) {
            System.out.println("│  "+stack[i]+"  │");
            if (i == 0) {
                System.out.println("└─────┘");
            } else {
                System.out.println("├─────┤");
            }
        }
    }

    /**
     * stack 꽉차면 한칸 늘리는 함수
     */
    public void increaseStack() {
        int[] temp = new int[stack.length+1];
        System.arraycopy(stack, 0, temp, 0, stack.length);
        stack = temp;
    }

}

 

 

스택 활용

 

중위표기식 -> 후위표기식 전환

후위표기식 계산

문자열 뒤집기

 

 

메인함수

public class Main {
    public static void main(String[] args) {
        // 계산식 넣기
        String str = "((9-(2*1))-8)+4";

        // String을 stack으로
        MyStack myStack = UseStack.stringToStack(str);

        // 뒤집기
        myStack = UseStack.resverseStack(myStack);
        // 뒤집은거 출력
        myStack.print();
        // postfix 변환
        myStack = UseStack.convert(myStack);
        // 변환된 스택 출력
        myStack.print();

        // 변환된거 뒤집기
        myStack = UseStack.resverseStack(myStack);

        // string으로 옮기기
        StringBuilder sb = new StringBuilder();
        while(!myStack.isEmpty()) {
            char temp = (char) myStack.pop();
            System.out.print(temp+ " ");
            sb.append(temp);
        }

        // string으로 옮긴 계산식 계산하기
        System.out.println();
        System.out.println(UseStack.calc(sb.toString()));
    }
}

 

MyStack.javaint가 아닌 char stack으로 변경

public class MyStack {

    private char[] stack;
    private int top;

    /**
     * 기본 생성자
     * stack 크기 = 10
     */
    public MyStack() {
        stack = new char[10];
        top=-1;
    }
    /**
     * 기본 생성자 2
     * stack 크기 받아서 생성
     */
    public MyStack(int size) {
        stack = new char[size];
        top=-1;
    }

    /** stack에 값 넣기 = push
     *  정수를 stack에 넣음
     *
     *  top에 1을 더하고
     *  stack의 길이 이상으로 push 하려하면 배열 늘려주고 push
     *
     * @param x
     */
    public void push(char x) {
        top = top+1;
        if(size() < stack.length) {
            stack[top] = x;
        } else {
            increaseStack();
            stack[top] = x;
        }
    }

    /** stack에서 값 빼기  = pop
     *  제일 마지막에 push된 문자를 반환
     * top 위치의 정수를 빼고 top을 -1 해주고 해당값 반환
     * 뺄수없으면 null 반환
     * @return
     */
    public Object pop() {

        if(size() >= 0) {
            char temp = stack[top];
            top = top - 1;
            return temp;
        }
        else return null;
    }

    /**
     *  stack top 확인 = peek
     *  비어있지않다면 top의 값 보여줌 실제 pop X
     */
    public Object peek() {
        if(size() >= 0) {
            return stack[top];
        }
        else {
            return null;
        }
    }


    /** stack이 비었는지 확인
     *  top이 0보다 작으면 비어있는것 return true
     *  top이 0보다 크거나 같으면 비어있지 않은것 return false
     * @return
     */
    public boolean isEmpty() {
        return top < 0;
    }

    /** stack의 크기 확인
     *  크기를 int로 반환
      * @return
     */
    public int size() {
        return top;
    }

    /**
     * 스택의 내용을 출력해주는 함수
     */
    public void print() {
        System.out.println("┌─────┐");
        for(int i=top; i>=0; i--) {
            System.out.println("│  "+stack[i]+"  │");
            if (i == 0) {
                System.out.println("└─────┘");
            } else {
                System.out.println("├─────┤");
            }
        }
    }

    /**
     * stack 꽉차면 한칸 늘리는 함수
     */
    public void increaseStack() {
        char[] temp = new char[stack.length+1];
        System.arraycopy(stack, 0, temp, 0, stack.length);
        stack = temp;
    }

}

 

 

UseStack.java

 

import java.util.ArrayList;
import java.util.List;

public class UseStack {

    /**
     * String을 stack으로
     * String을 charArray로 바꾸고 stack에 넣기
     * @param str
     * @return
     */
    static public MyStack stringToStack(String str) {
        MyStack stack = new MyStack();
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            stack.push(chars[i]);
        }
        return stack;
    }

    /**
     * 스택 뒤집기
     * 새로운 스택 하나 생성해서
     * 기존 스택 pop한걸 새로운 스택에 push
     * @param stack
     * @return
     */
    static public MyStack resverseStack(MyStack stack) {
        MyStack newStack = new MyStack(stack.size());
        for (int i = stack.size(); i >= 0; i--) {
            newStack.push((char) stack.pop());
        }
        return newStack;
    }

    /**
     * 중위표기식을 후위표기식으로 변환
     *
     * @param stack
     * @return
     */
    static public MyStack convert(MyStack stack) {
        // 결과 스택
        MyStack newStack = new MyStack(stack.size());
        // 연산자 스택
        MyStack opStack = new MyStack(stack.size());

        // 후위표기식으로 변환
        for(int i = stack.size(); i >= 0; i--) {
            char c = (char) stack.pop();
                switch (c) {
                    // 피연산자는 바로 결과배열에 추가
                    // 연산자는 경우에 따라 달라짐
                    case '(' -> {
                        opStack.push(c);
                    }
                    case ')' -> {
                        // ( 가 나올때까지 연산자스택에서 pop해서 결과스택에 push
                        while(!opStack.isEmpty()) {
                            char temp = (char) opStack.pop();
                            if(temp == '(') {
                                break;
                            }
                            newStack.push(temp);
                        }
                    }
                    case '+', '-' -> {
                        // 자기보다 낮은거 만날때까지 연산자스택에서 pop 해서 결과스택에 push
                        while(!opStack.isEmpty()) {
                            char temp = (char) opStack.peek();
                            if(temp == '(' ) {
                                break;
                            } else {
                                newStack.push((char) opStack.pop());
                            }
                        }
                        opStack.push(c);
                    }
                    case '*', '/' -> {
                        // 자기보다 낮은거 만날때까지 연산자스택에서 pop 해서 결과스택에 push
                        while(!opStack.isEmpty()) {
                            char temp = (char) opStack.peek();
                            if(temp == '+' || temp == '-' || temp == '(') {
                                break;
                            } else {
                                newStack.push((char) opStack.pop());
                            }
                        }
                        opStack.push(c);
                    }

                    // c가 알파벳이면 바로 결과스택에 추가
                    default -> {
                        newStack.push(c);
                    }
                }

        }
        // 남은 연산자가 있으면 다 pop해서 결과스택에 넣어주고 결과스택을 return
        while(!opStack.isEmpty()) {
            newStack.push((char)opStack.pop());
        }
        return newStack;
    }

    /**
     * 후위표기식을 계산
     * 피연산자는 stack에 저장
     * 연산자가 나오면 stack에서 피연산자 2개 빼서 연산하고 다시 stack에 저장
     * 마지막 stack에 남은 숫자가 계산결과이므로 return
     * @param str
     * @return
     */
    static public int calc(String str) {
        List<Character> op = new ArrayList<Character>();
        op.add('+');
        op.add('-');
        op.add('*');
        op.add('/');
        char[] chars = str.toCharArray();
        MyStack stack = new MyStack();
        for (char aChar : chars) {
            if (op.contains(aChar)) {
                int b = (char) stack.pop() - '0';
                int a = (char) stack.pop() - '0';

                switch (aChar) {
                    case '+' -> {
                        stack.push((char) ((a + b) + '0'));
                    }
                    case '-' -> {
                        stack.push((char) ((a - b) + '0'));
                    }
                    case '*' -> {
                        stack.push((char) ((a * b) + '0'));
                    }
                    case '/' -> {
                        stack.push((char) ((a / b) + '0'));
                    }
                }
            } else {
                stack.push(aChar);
            }
        }
        return (char)stack.pop() - '0';
    }
}