[🧠 Do it! 알고리즘] 2-5. 스택과 큐

배열에서  발전된 형태의 자료구조, 스택과 큐

---

🧠 목차

1. 스택 (Stack)
2. 큐 (Queue)
3. [실전 문제] 스택 수열 (백준 1874)
4. [실전 문제] 카드2 (백준 2164)
5. [실전 문제] 절댓값 힙 (백준 11286)

---

스택 (Stack)

스택(Stack)

• 삽입과 삭제 연산이 후입선출(LIFO: Last-in First-out)로 이뤄지는 자료구조
• 후입선출
  • 삽입과 삭제가 한쪽에서만 일어나는 특징이 있다.
  • 재귀 함수 알고리즘 원리와 비슷하다.
• 깊이 우선 탐색(DFS), 백트래킹 종류의 코딩테스트에 효과적이다.

 

스택 용어

• 위치
  • top: 삽입과 삭제가 일어나는 위치
• 연산
  • push: top 위치에 새로운 데이터를 삽입하는 연산
  • pop: top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
  • peek: top 위치에 현재 있는 데이터를 단순 확인하는 연산이다.

 

---

2. 큐 (Queue)

큐 (Queue)

• 삽입과 삭제 연산이 선입선출(FIFO: First-in First-out)로 이뤄지는 자료구조
• 선입선출
  
  • 삽입과 삭제가 양방향에서 이뤄진다.
• 너비 우선 탐색(DFS)에서 자주 사용한다.

 

큐 용어

• 위치
  • front: 큐에서 가장 앞의 데이터를 가리키는 위치
  • rear: 큐에서 가장 끝 데이터를 가리키는 위치
• 연산
  • add: rear 부분에 새로운 데이터를 삽인하는 연산
  • poll: front 부분에 있는 데이터를 삭제하고 확인하는 연산
  • peek: 큐의 맨 앞(font)에 있는 데이터를 확인할 때 사용하는 연산

 

 

 

* 우선순위 큐

• 값이 들어간 순서와 상관없이 수선순위가 높은 데이터가 먼저 나오는 자료구조
• 힙을 이용해 구현
• 이후 자세히 다룰 예정

---

3. [실전 문제] 스택 수열 (백준 1874)

문제: 스택 수열 (백준 1874) https://www.acmicpc.net/problem/1874

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();

        int N = sc.nextInt();
        sc.nextLine();

        Stack<Integer> stack = new Stack<>();

        int j = 1;
        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();

            while (j <= num) {
                stack.push(j++);
                sb.append("+\n");
            }

            if(stack.peek() == num){
                stack.pop();
                sb.append("-\n");
            } else {
                sb.setLength(0);
                sb.append("NO\n");
                break;
            }
        }
        System.out.println(sb);
    }
}

---

4. [실전 문제] 카드2 (백준 2164)

문제: 카드2 (백준 2164) https://www.acmicpc.net/problem/2164

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        Queue<Integer> queue = new LinkedList<>();

        int N = scanner.nextInt();
        scanner.nextLine();

        for (int i = 1; i <= N; i++) {
            queue.add(i);
        }

        while (queue.size() > 1) {
            queue.poll();
            queue.add(queue.poll());
        }

        System.out.println(queue.poll());
    }
}

---

5. [실전 문제] 절댓값 힙 (백준 11286)

문제: 절댓값 힙 (백준 11286) https://www.acmicpc.net/problem/11286

 

우선 순위 큐 사용

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N = scanner.nextInt();
        scanner.nextLine();

        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b)
                -> Math.abs(a) == Math.abs(b) ? a.compareTo(b) : Math.abs(a) - Math.abs(b)
        );

        for (int i = 0; i < N; i++) {
            int x = scanner.nextInt();
            scanner.nextLine();

            if(x == 0){
                if(queue.isEmpty()){
                    System.out.println(0);
                } else {
                    System.out.println(queue.poll());
                }
                continue;
            }

            queue.add(x);
        }
    }
}

 

위 코드는 시간 초과가 발생했다.... ㅎ

 

변경된 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> queue = new PriorityQueue<>((a, b)
                -> Math.abs(a) == Math.abs(b) ? a.compareTo(b) : Math.abs(a) - Math.abs(b)
        );

        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(br.readLine());

            if(x == 0){
                if(queue.isEmpty()){
                    sb.append(0).append("\n");
                } else {
                    sb.append(queue.poll()).append("\n");
                }
                continue;
            }

            queue.add(x);
        }

        System.out.println(sb);
    }
}

 

Scanner 는 좀 쓰게 해주면 안되나 .... ㅜㅜㅜㅜㅜㅜㅜ