데이터 구조 - 4 - 스 택

창고
1. 개념
스 택 과 대기 열 이 유사 합 니 다. 다른 것 은 스 택 이 LIFO last-in-first-out 의 원칙, 즉 마지막 스 택 에 들 어간 요 소 를 가장 먼저 꺼 내 는 것 입 니 다.
오다
2. 상용 방법

push。창고 에 넣다

pop。출고

peek。창고 꼭대기 의 원소 보기

3. 예시
【 1 】 배열 창고

class ArrayStack<T> {
    private final int length;
    private Object[] array;
    private int top; //           

    public ArrayStack(int length) {
        this.length = length;
        this.array = new Object[this.length];
        this.top = -1;
    }

    public void push(T element) {
        if (isFull()) {
            return;
        }

        array[++top] = element;
    }

    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) {
            return null;
        }

        return (T)array[top--];
    }

    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            return null;
        }

        return (T)array[top];
    }

    public boolean isFull() {
        return top == length - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }

        StringBuilder sBuilder = new StringBuilder("[");
        for (int i = top; i > 0; i--) {
            sBuilder.append(array[i]).append(',').append(' ');
        }
        sBuilder.append(array[0]).append(']');
        return sBuilder.toString();
    }

}

【 2 】 링크 스 택

class LinkedStack<T> {
    private final int length;
    private Node<T> top;
    private int size;

    public LinkedStack(int length) {
        this.length = length;
        this.top = null;
        this.size = 0;
    }

    public void push(T element) {
        if (isFull()) {
            return;
        }

        Node<T> add = new Node<T>(element);
        add.next = top;
        top = add;
        this.size++;
    }

    public T pop() {
        if (isEmpty()) {
            return null;
        }

        Node<T> node = this.top;
        this.top = node.next;
        this.size--;
        return node.element;
    }

    public T peek() {
        if (isEmpty()) {
            return null;
        }

        return this.top.element;
    }

    public boolean isFull() {
        return size == length;
    }

    public boolean isEmpty() {
        return this.top == null;
    }

    private static class Node<T> {
        private T element;
        private Node<T> next;

        public Node(T element) {
            this.element = element;
        }

        @Override
        public String toString() {
            return (null != element) ? element.toString() : "null";
        }
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        }

        StringBuilder sBuilder = new StringBuilder("[");
        Node<T> node = this.top;
        while (true) {
            sBuilder.append(node.element);
            if (null == node.next) {
                break;
            }
            node = node.next;
            sBuilder.append(',').append(' ');
        }
        sBuilder.append(']');
        return sBuilder.toString();
    }

}

4. 응용
【 1 】 접미사 식
접미사 표현 식 은 우리 가 일상적으로 계산 할 때 사용 하 는 표현 식 알고리즘 이다. 예 를 들 어 1 + 2 * (3 / 4.5)
즉 연산 자 는 연산 량 의 중간 에 있다.인간 에 게 는 계산 이 편리 하지만 컴퓨터 로 계산 할 때 는 비교적 번거롭다.
계산 방식:

2 개의 스 택 구 조 를 사용 하고 하 나 는 숫자 (스 택) 를 저장 하 며 다른 하 나 는 연산 자 (부적 스 택)

를 저장 합 니 다.

왼쪽 에서 오른쪽으로 접미사 표현 식 을 옮 겨 다 니 며 숫자 를 만 났 을 때 스 택 에 넣 습 니 다

연산 자 를 만 났 을 때 기호 스 택 이 비어 있 으 면 기호 스 택 에 직접 들어간다

기호 스 택 이 비어 있 지 않 으 면 기호 스 택 꼭대기 의 연산 자 와 현재 연산 자의 우선 순위 (왼쪽 작은 괄호 우선 순위 가 가장 낮 음) 를 판단 해 야 합 니 다. 현재 연산 자의 우선 순위 가 스 택 꼭대기 의 기호 보다 크 면 현재 연산 자 를 기호 스 택 에 두 고 이전 연산 자의 우선 순위 가 스 택 꼭대기 의 기호 보다 작 거나 같 으 면 스 택 꼭대기 기 호 를 꺼 냅 니 다.동시에 스 택 에서 두 개의 숫자 를 꺼 내 고 첫 번 째 숫자 는 (가 / 감 / 승 / 제) 수로 하고 두 번 째 숫자 는 피 (가 / 감 / 승 / 제) 수로 계산 결 과 를 스 택 에 넣 는 동시에 현재 연산 자 를 기호 스 택

에 넣 습 니 다.

작은 괄호 를 만 났 을 때 왼쪽 작은 괄호 라면 기호 스 택 에 직접 들 어가 고 오른쪽 작은 괄호 라면 연산 자 하나 와 숫자 두 개 를 차례대로 꺼 내 계산 한 다음 에 결 과 를 스 택 에 넣 고 왼쪽 괄호 를 만 나 서 스 택 에서 나 올 때 까지 반복 합 니 다

.

마지막: 기호 스 택 에서 스 택 의 맨 위 기 호 를 꺼 내 는 동시에 스 택 에서 두 개의 숫자 를 꺼 냅 니 다. 첫 번 째 숫자 는 (가 / 감 / 승 / 제) 수로 하고 두 번 째 숫자 는 피 (가 / 감 / 승 / 제) 수로 계산 결 과 를 스 택 에 넣 고 이 조작 을 반복 합 니 다. 기호 스 택 이 비 어 있 을 때 까지 합 니 다.최종 스 택 은 계산 결과

라 는 요 소 를 남 길 것 이다.
예시:

import java.util.Stack;

class InfixExpression {

    public static double calc(String expression) {
        if (null == expression || 0 == expression.length()) {
            return 0;
        }

        //       ，    、   、    
        expression = expression.replaceAll("\\s", "");
        if (0 == expression.length()) {
            return 0;
        }

        return split(expression);
    }

    private static double split(String expression) {
        Stack<String> digitStack = new Stack<String>();
        Stack<String> operatorStack = new Stack<String>();

        String digit = "";
        for (int i = 0, len = expression.length(); i < len; i++) {
            char ch = expression.charAt(i);
            if (isOperator(ch)) {
                if (!"".equals(digit)) { //         
                    digitStack.push(digit);
                    digit = "";
                }

                if (operatorStack.isEmpty()) { //      
                    operatorStack.push(String.valueOf(ch));
                } else {
                    if ('(' == ch) {
                        operatorStack.push(String.valueOf(ch));
                    } else if (')' == ch) {
                        char operator = operatorStack.pop().charAt(0);

                        while ('(' != operator) {
                            String digit1 = digitStack.pop();
                            String digit2 = digitStack.pop();
                            double calc = calc(digit1, digit2, operator);
                            digitStack.push(Double.toString(calc));

                            operator = operatorStack.pop().charAt(0);
                        }
                    } else {
                        char pop = operatorStack.pop().charAt(0);

                        //                              
                        if (getPriority(ch) > getPriority(pop)) {
                            operatorStack.push(String.valueOf(pop));
                        } else {
                            String digit1 = digitStack.pop();
                            String digit2 = digitStack.pop();
                            double calc = calc(digit1, digit2, pop);
                            digitStack.push(Double.toString(calc));
                        }

                        operatorStack.push(String.valueOf(ch));
                    }
                }

            } else {
                digit += ch;
            }
        }

        if (!"".equals(digit)) { //           
            digitStack.push(digit);
        }

        return result(digitStack, operatorStack);
    }

    /**
     *                
     */
    private static boolean isOperator(char ch) {
        return '+' == ch || '-' == ch || '*' == ch || '/' == ch || '(' == ch || ')' == ch;
    }

    private static double calc(String digit1, String digit2, char operator) {
        switch (operator) {
            case '+':
                return Double.valueOf(digit2) + Double.valueOf(digit1);
            case '-':
                return Double.valueOf(digit2) - Double.valueOf(digit1);
            case '*':
                return Double.valueOf(digit2) * Double.valueOf(digit1);
            case '/':
                return Double.valueOf(digit2) / Double.valueOf(digit1);
            default:
                return 0;
        }
    }

    private static int getPriority(char operator) {
        switch (operator) {
            case '(':
                return 0;
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                throw new IllegalArgumentException("      ！");
        }
    }

    private static double result(Stack<String> digitStack, Stack<String> operatorStack) {
        while (!operatorStack.isEmpty()) { //       
            String digit1 = digitStack.pop();
            String digit2 = digitStack.pop();
            char operator = operatorStack.pop().charAt(0);
            double calc = calc(digit1, digit2, operator);
            digitStack.push(Double.toString(calc));
        }
        return Double.valueOf(digitStack.pop()); //            ：    
    }

}

[2] 접두사 표현 식 (폴란드 표현 식)
접두사 표현 식 은 연산 자가 연산 량 의 앞 에 있 습 니 다. 예 를 들 어 + 1 * 2 / 3 4.5 입 니 다.
접두사 식 접두사 식:

2 개의 스 택 구 조 를 사용 하고 하 나 는 숫자 (스 택) 를 저장 하 며 다른 하 나 는 연산 자 (부적 스 택)

를 저장 합 니 다.

오른쪽 에서 왼쪽으로 접미사 표현 식 을 옮 겨 다 니 며 숫자 를 만 났 을 때 스 택 에 넣 습 니 다

연산 자 를 만 났 을 때 기호 스 택 이 비어 있 으 면 기호 스 택 에 직접 들어간다

기호 스 택 이 비어 있 지 않 으 면 기호 스 택 꼭대기 의 연산 자 와 현재 연산 자의 우선 순위 (오른쪽 작은 괄호 우선 순위 가 가장 낮 음) 를 판단 해 야 합 니 다. 현재 연산 자의 우선 순위 가 스 택 꼭대기 의 기호 보다 크 거나 같 으 면 현재 연산 자 를 기호 스 택 에 두 고 현재 연산 자의 우선 순위 가 스 택 꼭대기 의 기호 보다 작 으 면 기호 스 택 꼭대기 의 기 호 를 꺼 냅 니 다.스 택 에 넣 는 동시에 현재 연산 자 를 기호 스 택 에 넣 습 니 다

작은 괄호 를 만 났 을 때 오른쪽 작은 괄호 라면 바로 기호 스 택 에 들 어가 고 왼쪽 작은 괄호 라면 기호 스 택 꼭대기 의 기 호 를 꺼 내 서 스 택 에 넣 고 오른쪽 괄호 를 만 나 서 스 택 에서 나 올 때 까지 반복 합 니 다

마지막 으로 기호 창고 의 기 호 를 순서대로 창고 에서 꺼 내 고 창고 에 넣는다

계산 방식:

반전 스 택 의 요소

임시 창고 구조 1 개 사용

스 택 폴란드 표현 식 의 요 소 를 순서대로 나 누고 숫자 라면 임시 스 택 에 들 어 갑 니 다

기호 라면 임시 스 택 에서 두 개의 숫자 를 꺼 내 고 첫 번 째 숫자 는 피 (가 / 감 / 승 / 제) 수, 두 번 째 숫자 는 (가 / 감 / 승 / 제) 수 로 계산 결 과 를 임시 스 택 에 넣 고 모든 요소 가 스 택 에서 나 올 때 까지 반복 합 니 다.최종 임시 스 택 은 계산 결과

라 는 요 소 를 남 깁 니 다.
예시:

import java.util.Stack;

class PrefixExpression {

    public static double calc(String expression) {
        if (null == expression || 0 == expression.length()) {
            return 0;
        }

        expression = expression.replaceAll("\\s", "");
        if (0 == expression.length()) {
            return 0;
        }

        return split(expression);
    }

    private static double split(String expression) {
        Stack<String> digitStack = new Stack<String>();
        Stack<String> operatorStack = new Stack<String>();

        String digit = "";
        for (int i = expression.length() - 1; i >= 0; i--) { //       
            char ch = expression.charAt(i);
            if (isOperator(ch)) {
                if (!"".equals(digit)) { //         
                    digitStack.push(digit);
                    digit = "";
                }

                if (operatorStack.isEmpty()) { //      
                    operatorStack.push(String.valueOf(ch));
                } else {
                    if (')' == ch) {
                        operatorStack.push(String.valueOf(ch));
                    } else if ('(' == ch) {
                        char operator = operatorStack.pop().charAt(0);

                        while (')' != operator) {
                            digitStack.push(String.valueOf(operator));
                            operator = operatorStack.pop().charAt(0);
                        }
                    } else {
                        char pop = operatorStack.pop().charAt(0);
                        if (getPriority(ch) >= getPriority(pop)) {
                            operatorStack.push(String.valueOf(pop));
                        } else {
                            digitStack.push(String.valueOf(pop));
                        }

                        operatorStack.push(String.valueOf(ch));
                    }
                }

            } else {
                digit = ch + digit; //                
            }
        }

        if (!"".equals(digit)) { //           
            digitStack.push(digit);
        }

        while (!operatorStack.isEmpty()) { //          
            digitStack.push(operatorStack.pop());
        }

        return result(digitStack);
    }

    /**
     *                
     */
    private static boolean isOperator(char ch) {
        return '+' == ch || '-' == ch || '*' == ch || '/' == ch || '(' == ch || ')' == ch;
    }

    private static double calc(String digit1, String digit2, char operator) {
        switch (operator) {
            case '+':
                return Double.valueOf(digit1) + Double.valueOf(digit2);
            case '-':
                return Double.valueOf(digit1) - Double.valueOf(digit2);
            case '*':
                return Double.valueOf(digit1) * Double.valueOf(digit2);
            case '/':
                return Double.valueOf(digit1) / Double.valueOf(digit2);
            default:
                return 0;
        }
    }

    private static int getPriority(char operator) {
        switch (operator) {
            case ')':
                return 0;
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                throw new IllegalArgumentException("      ！");
        }
    }

    private static double result(Stack<String> digitStack) {
        printNotation(digitStack);

        Stack<String> temp = new Stack<String>();
        while (!digitStack.isEmpty()) { //        
            temp.push(digitStack.pop());
        }

        Stack<String> tempDigitStack = new Stack<String>();
        while (!temp.isEmpty()) {
            String pop = temp.pop();
            char first = pop.charAt(0);
            if (isOperator(first)) {
                String digit1 = tempDigitStack.pop();
                String digit2 = tempDigitStack.pop();
                double calc = calc(digit1, digit2, first);
                tempDigitStack.push(Double.toString(calc));
            } else {
                tempDigitStack.push(pop);
            }
        }

        return Double.valueOf(tempDigitStack.pop());
    }

    private static void printNotation(Stack<String> digitStack) {
        for (int i = digitStack.size() - 1; i >= 0; i--) {
            System.out.print(digitStack.get(i) + "  ");
        }
        System.out.println();
    }

}

【 3 】 접미사 표현 식 (역 폴란드 표현 식)
역 폴란드 식 (reverse Polish notation, RPN) 은 연산 량 을 앞 에 쓰 고 연산 자 를 뒤에 쓴다.
예: 1, 2, 3, 4.5 / * +
접미사 표현 식 역 폴란드 표현 식:

2 개의 스 택 구 조 를 사용 하고 하 나 는 숫자 (스 택) 를 저장 하 며 다른 하 나 는 연산 자 (부적 스 택)

를 저장 합 니 다.

왼쪽 에서 오른쪽으로 접미사 표현 식 을 옮 겨 다 니 며 숫자 를 만 났 을 때 스 택 에 넣 습 니 다

연산 자 를 만 났 을 때 기호 스 택 이 비어 있 으 면 기호 스 택 에 직접 들어간다

기호 스 택 이 비어 있 지 않 으 면 기호 스 택 꼭대기 의 연산 자 와 현재 연산 자의 우선 순위 (왼쪽 작은 괄호 우선 순위 가 가장 낮 음) 를 판단 해 야 합 니 다. 현재 연산 자의 우선 순위 가 스 택 꼭대기 의 기호 보다 크 면 현재 연산 자 를 기호 스 택 에 두 어야 합 니 다. 만약 에 앞의 연산 자의 우선 순위 가 스 택 꼭대기 의 기호 보다 작 거나 같 으 면 기호 스 택 꼭대기 의 기 호 를 꺼 냅 니 다.스 택 에 넣 는 동시에 현재 연산 자 를 기호 스 택 에 넣 습 니 다

작은 괄호 를 만 났 을 때 왼쪽 작은 괄호 라면 바로 기호 스 택 에 들 어가 고 오른쪽 작은 괄호 라면 기호 스 택 꼭대기 의 기 호 를 꺼 내 서 스 택 에 넣 고 왼쪽 괄호 를 만 나 서 스 택 에서 나 올 때 까지 반복 합 니 다

마지막 으로 기호 창고 의 기 호 를 순서대로 창고 에서 꺼 내 고 창고 에 넣는다

반전 스 택 의 요소

계산 방식:

임시 창고 구조 1 개 사용

스 택 역 폴란드 표현 식 의 요 소 를 순서대로 나 누고 숫자 라면 임시 스 택

에 들 어 갑 니 다.

기호 라면 임시 스 택 에서 두 개의 숫자 를 꺼 내 고 첫 번 째 숫자 는 (가 / 감 / 승 / 제) 수로 하고 두 번 째 숫자 는 피 (가 / 감 / 승 / 제) 수로 계산 결 과 를 임시 스 택 에 넣 고 모든 요소 가 스 택 에서 나 올 때 까지 반복 합 니 다.최종 임시 스 택 은 계산 결과

라 는 요 소 를 남 깁 니 다.
예시:

import java.util.Stack;

class RPN {

    public static double calc(String expression) {
        if (null == expression || 0 == expression.length()) {
            return 0;
        }

        expression = expression.replaceAll("\\s", "");
        if (0 == expression.length()) {
            return 0;
        }

        return split(expression);
    }

    private static double split(String expression) {
        Stack<String> digitStack = new Stack<String>();
        Stack<String> operatorStack = new Stack<String>();

        String digit = "";
        for (int i = 0, len = expression.length(); i < len; i++) {
            char ch = expression.charAt(i);
            if (isOperator(ch)) {
                if (!"".equals(digit)) { //         
                    digitStack.push(digit);
                    digit = "";
                }

                if (operatorStack.isEmpty()) { //      
                    operatorStack.push(String.valueOf(ch));
                } else {
                    if ('(' == ch) {
                        operatorStack.push(String.valueOf(ch));
                    } else if (')' == ch) {
                        char operator = operatorStack.pop().charAt(0);

                        while ('(' != operator) {
                            digitStack.push(String.valueOf(operator));
                            operator = operatorStack.pop().charAt(0);
                        }
                    } else {
                        char pop = operatorStack.pop().charAt(0);
                        if (getPriority(ch) > getPriority(pop)) {
                            operatorStack.push(String.valueOf(pop));
                        } else {
                            digitStack.push(String.valueOf(pop));
                        }

                        operatorStack.push(String.valueOf(ch));
                    }
                }

            } else {
                digit += ch;
            }
        }

        if (!"".equals(digit)) { //           
            digitStack.push(digit);
        }

        while (!operatorStack.isEmpty()) { //          
            digitStack.push(operatorStack.pop());
        }

        Stack<String> temp = new Stack<String>();
        while (!digitStack.isEmpty()) { //     
            temp.push(digitStack.pop());
        }

        return result(temp);
    }

    /**
     *                
     */
    private static boolean isOperator(char ch) {
        return '+' == ch || '-' == ch || '*' == ch || '/' == ch || '(' == ch || ')' == ch;
    }

    private static double calc(String digit1, String digit2, char operator) {
        switch (operator) {
            case '+':
                return Double.valueOf(digit2) + Double.valueOf(digit1);
            case '-':
                return Double.valueOf(digit2) - Double.valueOf(digit1);
            case '*':
                return Double.valueOf(digit2) * Double.valueOf(digit1);
            case '/':
                return Double.valueOf(digit2) / Double.valueOf(digit1);
            default:
                return 0;
        }
    }

    private static int getPriority(char operator) {
        switch (operator) {
            case '(':
                return 0;
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            default:
                throw new IllegalArgumentException("      ！");
        }
    }

    private static double result(Stack<String> digitStack) {
        printNotation(digitStack);

        Stack<String> tempDigitStack = new Stack<String>();
        while (!digitStack.isEmpty()) {
            String pop = digitStack.pop();
            char first = pop.charAt(0);
            if (isOperator(first)) {
                String digit1 = tempDigitStack.pop();
                String digit2 = tempDigitStack.pop();
                double calc = calc(digit1, digit2, first);
                tempDigitStack.push(Double.toString(calc));
            } else {
                tempDigitStack.push(pop);
            }
        }

        return Double.valueOf(tempDigitStack.pop());
    }

    private static void printNotation(Stack<String> digitStack) {
        for (int i = digitStack.size() - 1; i >= 0; i--) {
            System.out.print(digitStack.get(i) + "  ");
        }
        System.out.println();
    }

}