[Do it] 알코테 자바 4일차

Do it! 알코테 자바

[Do it] 알코테 자바 4일차

namerong 2026. 2. 26. 19:57

04-5 스택과 큐

1. 스택 (Stack)

스택은 삽입과 삭제가 한쪽 끝에서만 이루어지는 자료구조이다.
구조적으로 후입선출(LIFO, Last In First Out) 방식을 따른다.

동작 방식

push : 데이터 삽입
pop : 데이터 제거
peek : 가장 위 데이터 확인

가장 나중에 들어온 데이터가 가장 먼저 나간다.

특징

한 방향(Top)에서만 연산 수행
구현이 단순함
재귀 구조와 동일한 원리

활용 분야

깊이 우선 탐색 (DFS)
백트래킹
재귀 함수 호출 구조
괄호 검사 문제
되돌리기(Undo) 기능

재귀 함수와 스택

재귀 함수는 내부적으로 **호출 스택(Call Stack)**을 사용한다.

함수 호출 시 스택에 쌓임
함수 종료 시 스택에서 제거

따라서 재귀는 스택 구조와 동일한 원리로 동작한다.

시간 복잡도

push : O(1)
pop : O(1)
peek : O(1)

2. 큐 (Queue)

큐는 삽입과 삭제가 서로 다른 방향에서 이루어지는 자료구조이다.
구조적으로 선입선출(FIFO, First In First Out) 방식을 따른다.

동작 방식

offer(enqueue) : 뒤에 삽입
poll(dequeue) : 앞에서 제거
peek : 맨 앞 데이터 확인

먼저 들어온 데이터가 먼저 나간다.

특징

앞(front)과 뒤(rear) 두 방향 존재
순차적인 처리에 적합

활용 분야

너비 우선 탐색 (BFS)
대기열 처리
작업 스케줄링
캐시 구현

시간 복잡도

삽입 : O(1)
삭제 : O(1)

3. 덱 (Deque)

Deque는 Double Ended Queue의 줄임말로,
양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조이다.

특징

스택처럼 사용 가능
큐처럼 사용 가능
슬라이딩 윈도우 문제에서 자주 활용

4. 우선순위 큐 (Priority Queue)

우선순위 큐는 데이터가 들어간 순서와 관계없이 우선순위가 높은 값이 먼저 나오는 자료구조이다.

즉, FIFO 구조가 아니다.

내부 구현

일반적으로 힙(Heap) 자료구조를 이용해 구현
Java에서는 기본적으로 최소 힙(Min Heap) 구조

동작 방식

삽입 : 우선순위 기준으로 재정렬
삭제 : 항상 우선순위가 가장 높은 값 제거

활용 분야

다익스트라 알고리즘
최소 신장 트리
작업 스케줄링
이벤트 처리 시스템

시간 복잡도 (Heap 기준)

삽입 : O(log N)
삭제 : O(log N)
최상위 값 조회 : O(1)

스택 vs 큐 비교

구분	스택	큐
구조	LIFO	FIFO
삽입 위치	한쪽	뒤
삭제 위치	한쪽	앞
대표 알고리즘	DFS	BFS
내부 원리	재귀 호출 구조	순차 처리 구조

정리

스택은 후입선출 구조이며 DFS, 재귀에 사용된다.
큐는 선입선출 구조이며 BFS에 사용된다.
덱은 양쪽 연산이 가능하다.
우선순위 큐는 힙 기반으로 동작하며 우선순위가 높은 데이터가 먼저 나온다.

__[011] 스택으로 수열 만들기

백준 온라인 져지 1874번 https://www.acmicpc.net/problem/1874

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {

        // 1. 입력 및 출력 준비
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 2. 수열 길이 입력
        int n  = Integer.parseInt(br.readLine());

        // 3. 스택 생성 및 시작 숫자 초기화
        Stack<Integer> stack = new Stack<>();
        int start = 1;

        // 4. 목표 수열을 한 개씩 처리
        for(int i = 0; i < n; i++){

            // 4-1. 현재 만들어야 할 숫자 입력
            int num = Integer.parseInt(br.readLine());

            // 5. 아직 넣지 않은 숫자라면 start부터 num까지 push
            if(num >= start){
                for(int j = start; j <= num; j++){
                    stack.push(j);
                    sb.append("+\n");
                }
                start = num + 1;
            }
            // 6. 이미 지난 숫자인데 스택 top과 다르면 불가능
            else if(num != stack.peek()){
                System.out.println("NO");
                System.exit(0);
            }

            // 7. 원하는 숫자가 나올 때까지 pop
            while(!stack.empty()){
                sb.append("-\n");
                if(stack.pop() == num) break;
            }
        }

        // 8. 결과 출력
        System.out.println(sb.toString());
    }
}

__[012] 오큰수 구하기

백준 온라인 져지 17298번 https://www.acmicpc.net/problem/17298

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {
        // 1. 값 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] A = new int[N];
        int[] ans = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
            ans[i] = -1;
        }

        // 2. 스택으로 오큰수 구하기 (인덱스 저장)
        int[] stack = new int[N];
        int top = -1;

        for (int i = 0; i < N; i++) {
            while (top >= 0 && A[stack[top]] < A[i]) {
                ans[stack[top]] = A[i];
                top--;
            }
            stack[++top] = i;
        }

        // 3. 출력 만들기
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            sb.append(ans[i]);
            if (i + 1 < N) sb.append(' ');
        }

        // 4. 출력
        System.out.print(sb.toString());
    }
}

__[013] 카드 게임

백준 온라인 져지 2164번 https://www.acmicpc.net/problem/2164

import java.io.*;
import java.util.*;

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

        int n = Integer.parseInt(br.readLine());
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++){
            list.add(i);
        }

        while (list.size() > 1){
            for (int i = 0; i < 2; i++){
                if (i == 0){
                    list.remove();
                } else {
                    list.add(list.remove());
                }
            }
        }

        sb.append(list.get(0));
        System.out.println(sb);
    }
}

__[014] 절댓값 힙 구현하기

백준 온라인 져지 11286번 https://www.acmicpc.net/problem/11286

import java.io.*;
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();

				// 1. 연산 개수
        int n = Integer.parseInt(br.readLine());	

        // 2. 람다식 사용해보기
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> {
            int absA = Math.abs(a);
            int absB = Math.abs(b);
            if (absA == absB) {
                return a - b; 
            }
            // 3. 절대값 기준으로 정렬
            return absA - absB; 
        });

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

            if (num == 0) {	
            // 4. 0입력시 값이 없으면 0출력
                if (minHeap.isEmpty()) {	
                    sb.append("0\n");
                } else {
                    sb.append(minHeap.poll()).append('\n');	 
                }
            } else {
            // 5. 0이 아닐시 값 입력
                minHeap.offer(num);
            }
        }

        System.out.print(sb);
    }
}

'Do it! 알코테 자바' 카테고리의 다른 글

[Do it] 알코테 자바 6일차 (0)	2026.03.02
[Do it] 알코테 자바 5일차 (0)	2026.02.27
[Do it] 알코테 자바 3일차 (0)	2026.02.25
[Do it] 알코테 자바 2일차 (0)	2026.02.24
[Do it] 알코테 자바 1일차 (1)	2026.02.23

현재글[Do it] 알코테 자바 4일차

namerong 님의 블로그