11 to 9, Day 22 23

Today, ToDoList

• 스택 자료구조
• 큐 자료구조

---

스택 자료구조

package stack;

import java.util.Stack;

public class PostFix {

    //포스트픽스 계산식 - 스택/순회
    //시간복잡도 O(N), 공간복잡도 O(N)
    public int solution(String expression) {

        Stack<Integer> stack = new Stack<>();
        char[] chars = expression.toCharArray();

        for (int i = 0; i < chars.length; i++) {
            int rNum;
            int lNum;
            switch ( chars[i] ) {
                case '+':
                    rNum = stack.pop();
                    lNum = stack.pop();
                    stack.push(lNum+rNum);
                    break;
                case '-':
                    rNum = stack.pop();
                    lNum = stack.pop();
                    stack.push(lNum-rNum);
                    break;
                case '*':
                    rNum = stack.pop();
                    lNum = stack.pop();
                    stack.push(lNum*rNum);
                    break;
                case '/':
                    rNum = stack.pop();
                    lNum = stack.pop();
                    stack.push(lNum/rNum);
                    break;
                default:
                    stack.push(Integer.valueOf(String.valueOf(chars[i])));
            }
        }
        return stack.pop();
    }

    //포스트픽스 변환식 - 스택/순회
    //시간복잡도 O(N), 공간복잡도 O(N)
    public String infixToPostfix(String expression) {

        Stack<Character> stack = new Stack<>();
        char[] chars = expression.toCharArray();
        String result = "";

        for (int i = 0; i < chars.length; i++) {
            if ( Character.isDigit(chars[i]) ) {
                result = result.concat(String.valueOf(chars[i]));
            } else if ( stack.isEmpty() || chars[i] == '(' ) {
                stack.push(chars[i]);
            } else {

                switch (chars[i]) {
                    case ')':
                        int length =  stack.size();
                        for ( int j = 0; j<length; j++) {
                            if (stack.peek() != '(') {
                                result = result.concat(String.valueOf(stack.pop()));
                            } else {
                                stack.pop();
                                break;
                            }
                        }
                        break;
                    case '+': case '-':
                        if ( stack.peek() == '*' || stack.peek() == '/' ) {
                            result = result.concat(String.valueOf(chars[i]));
                        } else {
                            stack.push(chars[i]);
                        }
                        break;
                    case '*': case '/':
                        stack.push(chars[i]);
                        break;
                    default:
                        return "invalid";
                }
            }
        }
        int length =  stack.size();
        for ( int i = 0; i<length; i++) {
            result = result.concat(String.valueOf(stack.pop()));
        }
        return result;
    }

    public static void main(String[] args) {
        PostFix postFix = new PostFix();
        System.out.println(postFix.solution("521+-9*"));
        System.out.println(postFix.solution("52/"));
        System.out.println(postFix.solution("123+-5*"));
        System.out.println(postFix.solution("5123+-*"));

        System.out.println(postFix.infixToPostfix("1+2*3"));
        System.out.println(postFix.infixToPostfix("(1+2)*3"));
    }

}

package stack;

import java.util.Arrays;
import java.util.Stack;

public class Span {

    //스팬 찾기 - 이중 순회
    //시간복잡도 O(N^2), 공간복잡도 O(N)
    public int[] getSpan1(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            int count=0;
            for (int j = 0; j <= i; j++) {
                if ( nums[i] >= nums[j] ) {
                    count++;
                } else {
                    count = 0;
                }
            }
            result[i] = count;
        }
        return result;
    }

    //스팬 찾기 - 스택
    //인덱스에서 최고점 인덱스 빼기
    //시간복잡도 O(N), 공간복잡도 O(N)
    public int[] getSpan2(int[] nums) {
        int[] result = new int[nums.length];
        Stack<Integer> stack = new Stack<>();
        result[0] = 1;
        stack.push(0);

        for (int i = 1; i < nums.length; i++) {
            while ( !stack.isEmpty() && nums[i] >= nums[stack.peek()] ) {
                stack.pop();
            }

            if ( stack.isEmpty() ) {
                result[i] = i+1;
            } else {
                result[i] = i - stack.peek();
            }
            stack.push(i);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums1 = new int[] {5,3,2,4,7,1};
        int[] nums2 = new int[] {2,3,4,5,6,7};
        int[] nums3 = new int[] {4,6,5,3,8,5,5,7};
        int[] nums4 = new int[] {7,3,4,8,4,7};

        Span span = new Span();
        System.out.println(Arrays.toString(span.getSpan1(nums1)));
        System.out.println(Arrays.toString(span.getSpan1(nums2)));
        System.out.println(Arrays.toString(span.getSpan1(nums3)));
        System.out.println(Arrays.toString(span.getSpan1(nums4)));

        System.out.println(Arrays.toString(span.getSpan2(nums1)));
        System.out.println(Arrays.toString(span.getSpan2(nums2)));
        System.out.println(Arrays.toString(span.getSpan2(nums3)));
        System.out.println(Arrays.toString(span.getSpan2(nums4)));
    }
}

---

큐 자료구조

• FIFO / LILO
• Inqueue, Dequeue 모두 시간복잡도 O(1)
• 자바의 Queue 인터페이스
  • add() : 넣고 true, 넣을 수 없으면 예외처리
  • offer() : 넣고 true, 넣을 수 없으면 false
  • remove() : 꺼내기, 비어있으면 예외처리
  • poll() : 꺼내기, 비어있으면 null
  • element() : head 값 반환, 비어있으면 예외처리
  • peek() : head 값 반환, 비어있으면 null
  • ArrayDequeue, LinkedList를 구현체로 사용하자.

package queue;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class QueueFactory {

    //큐 뒤집기 - 순회/스택
    //스택에 넣었다가 다시 큐로 꺼내기
    //시간복잡도 O(N), 공간복잡도 O(N)
    public void reverseQueue1(Queue<Integer> queue) {
        Stack<Integer> stack = new Stack<>();
        while ( !queue.isEmpty() ) {
            stack.push(queue.poll());
        }
        while ( !stack.isEmpty() ) {
            queue.offer(stack.pop());
        }
    }

    //큐 뒤집기 - 재귀
    //시간복잡도 O(N), 공간복잡도 O(N)
    public Queue<Integer> reverseQueue2(Queue<Integer> queue) {
        if ( queue.isEmpty() ) {
            return queue;
        } else {
            Integer tempNum = queue.poll();
            queue = reverseQueue2(queue);
            queue.offer(tempNum);
            return queue;
        }
    }


    public static void main(String[] args) {
        QueueFactory queueFactory = new QueueFactory();

        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        queue.add(5);
        queue.add(6);

        System.out.println(queue);
//        queueFactory.reverseQueue1(queue);
//        System.out.println(queue);
        queueFactory.reverseQueue2(queue);
        System.out.println(queue);
    }
}