Stack/Queue, Array/LinkedList

Kim Dong Kyun·2023년 4월 4일

1. Stack

Stack은 Last In First Out (LIFO) 원칙에 따라 데이터를 저장하고 처리합니다. 가장 최근에 추가된 데이터가 가장 먼저 처리되는 구조를 가지며, push() 메서드를 사용하여 데이터를 삽입하고 pop() 메서드를 사용하여 데이터를 제거합니다.

예시 코드

프로그래머스 "같은 숫자는 싫어"

배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.

    public int[] solution(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        for (int num : arr) {
            if (stack.isEmpty() || stack.peek() != num) {
                stack.push(num);
            }
        }
        int[] resultArr = new int[stack.size()];
        for (int i = stack.size() - 1; i >= 0; i--) {
            resultArr[i] = stack.pop();
        }
        return resultArr;
    }

입출력 예

Stack은 위와 같이 Java에서 Class로 정의되어 있습니다. (그 자체가 구현체입니다)

2. Queue

Queue는 First In First Out (FIFO) 원칙에 따라 데이터를 저장하고 처리합니다. 가장 먼저 추가된 데이터가 가장 먼저 처리되는 구조를 가지며, offer() 메서드를 사용하여 데이터를 삽입하고 poll() 메서드를 사용하여 데이터를 제거합니다.

예시 코드

프로그래머스 "기능 개발"

    public int[] solution(int[] progresses, int[] speeds) {
        Queue<Integer> queue = new LinkedList<>(); 
        int n = progresses.length;
        for (int i = 0; i < n; i++) {
            int days = (100 - progresses[i] + speeds[i] - 1) / speeds[i]; 
            queue.offer(days); 
        }

        List<Integer> answerList = new ArrayList<>();
        while (!queue.isEmpty()) {
            int cnt = 1; 
            int cur = queue.poll();
            while (!queue.isEmpty() && queue.peek() <= cur) { 
                cnt++;
                queue.poll();
            }
            answerList.add(cnt);
        }

        int[] answer = new int[answerList.size()];
        for (int i = 0; i < answerList.size(); i++) {
            answer[i] = answerList.get(i);
        }

        return answer;
    }