[알고리즘] 스택, 큐 적용 문제(풀이X)

💡알고리즘은 입력, 출력, 유한성, 명백성, 효과성을 만족해야 한다.

개념 정리는 [자료구조]와 겹침
👉 문제로 직접 풀어보고 링크 남겨 둠

스택

2023.02.21 - [D • A/DataStructure] - [자료구조] 선형 자료구조 - 2. 랜덤 접근 불가능 - 스택(Stack)

▶ 정의

먼저 들어간 자료가 나중에 나오는 LIFO 자료구조.
한쪽 끝에서만 데이터 삽입 삭제 가능

▶ 연산자(java)

Stack<Integer> st = new Stack<Integer> ();  
Deque<Integer> st = new ArrayDeque<Integer>();

• push(item) : item 하나를 스택의 가장 윗부분에 추가
• pop() : 스택에서 가장 위에 있는 항목 제거
• peak(), top() : 스택의 가장 위에 있는 항목 반환
• empty() : 스택이 비어 있을 때 true 반환
• search(Object o) : 해당 obj의 위치 반환. top이면 1, 없으면 -1
• size() : 스택에 있는 요소 수 반환
  
  

🔗백준 10828 (구현 문제)

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int[] stack = new int[10000];
        int top=-1;

        int len = sc.nextInt();
        String order = "";

        for(int i=0; i<len; i++){
            order = sc.next();
            if(order.equals("push")){
                stack[++top] = sc.nextInt();
            }
            else if(order.equals("pop")){
                if(top!=-1)
                    sb.append(stack[top--]+"\n");
                else
                    sb.append("-1\n");
            }
            else if (order.equals("size")){
                sb.append((top+1)+"\n");
            }
            else if (order.equals("empty")) {
                if(top==-1)
                    sb.append(1+"\n");
                else
                    sb.append(0+"\n");
            }
            else if (order.equals("top")) {
                if(top!=-1)
                    sb.append(stack[top]+"\n");
                else
                    sb.append(-1+"\n");
            }
        }
        System.out.println(sb);
    }
}

🔗스택 문제집

🔗너무 어려웠던 문제 - 6549번 히스토그램에서 가장 큰 직사각형

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true){
            String test = br.readLine();
            if(test.equals("0")) break;
            Stack<long[]> st = new Stack<>();
            long maxA = 0;
            StringTokenizer token = new StringTokenizer(test," ");
            int len = Integer.parseInt(token.nextToken());
            for(int idx = 0; idx < len; idx++){
                long in = Long.parseLong(token.nextToken());
                long[] rac = {idx, in}; //0:index, 1:height
                while(!st.isEmpty() && st.peek()[1] >= in ){
                    long[] pop = st.pop();
                    long width = st.isEmpty() ? idx : idx-1-st.peek()[0];
                    maxA = Math.max(maxA, width*pop[1]);
                }
                st.push(rac);
            }
            while(!st.isEmpty()) {
                long[] pop = st.pop();
                long width = st.isEmpty() ? len: len - 1 - st.peek()[0];
                maxA = Math.max(maxA, width * pop[1]);
            }
            sb.append(maxA).append('\n');
        }
        System.out.println(sb);
    }
}

큐

2023.02.21 - [D • A/DataStructure] - [자료구조] 선형 자료구조 - 2. 랜덤 접근 불가능 - 큐(Queue)

▶ 정의

먼저 들어간 자료가 먼저 나오는 FIFO 자료구조.
스택과 반대

▶연산자

Deque<String> qu = new ArrayDeque<String>();

• add(item) : item을 큐의 맨 뒤쪽에 추가. 성공 시 true, 공간이 없어 실패하면 예외 발생
• offer(item) :  item을 큐의 맨 뒤쪽에 추가.
• peek() : 큐의 맨 앞 데이터를 반환. 큐가 비어있으면 null반환 
• element() : 큐의 맨 앞 데이터를 반환
• poll() : 큐의 맨 앞쪽의 데이터 삭제. 해당 요소 반환. 큐가 비어있으면 null 반환
• remove() : 큐의 맨 앞쪽의 데이터 삭제. 해당 요소 반환
  
  

🔗백준 10845 (구현 문제)

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int len = Integer.parseInt(br.readLine());
        int[] que = new int[10000];
        int front = 0, back = 0;
        for(int i=0; i<len; i++){
            String order = br.readLine();
            if(back >=0 && order.contains("push")){
                String[] spl = order.split(" ");
                que[back++] = Integer.parseInt(spl[1]);
            }else if(back>=front && order.equals("pop")){
                if(back==front){
                    sb.append(-1).append('\n');
                }else{
                    sb.append(que[front++]).append('\n');
                }
            }else if(order.equals("size")){
                if(back-front<0)
                    sb.append(0).append('\n');
                else
                    sb.append(back-front).append('\n');
            }else if(order.equals("empty")){
                if(back-front<=0)
                    sb.append(1).append('\n');
                else
                    sb.append(0).append('\n');
            }else if(order.equals("front")){
                if(back-front<=0)
                    sb.append(-1).append('\n');
                else
                    sb.append(que[front]).append('\n');
            }else if(order.equals("back")){
                if(back-front<=0)
                    sb.append(-1).append('\n');
                else
                    sb.append(que[back-1]).append('\n');
            }
        }
        System.out.println(sb);
    }
}

🔗 큐 문제집