참고링크

Stack

• Last In First Out 구조 : 나중에 넣은 데이터가 먼저 나옴

import java.util.Stack; //스택 import

public class Practice {
    public static void main(String[] args){

        //스택 선언 및 초기화
        Stack<Integer> stack = new Stack<>();

        //스택에 값 추가
        stack.push(1);
        stack.push(2);
        stack.push(3);

        //스택에서 값 삭제, 삭제한 값을 반환함
        stack.pop();
        System.out.println(stack.pop());

        //스택의 전체 값 삭제
        stack.clear();

        stack.push(1);
        stack.push(2);
        stack.push(3);

        //스택의 최상단 값 반환 (반환은 하지만 pop 처럼 값을 삭제하는 것은 아님)
        stack.peek();

        //스택의 크기 반환
        stack.size();

        //스택이 비어있으면 true 아니면 false 반환
        stack.empty();

        //값이 스택에 있으면 true 아니면 false 반환
        stack.contains(1);
        
        //스택 최상단 원소 반환 (삭제하는것은 아님)
        stack.peek();

    }
}

Queue

• Fisrt In First Out 구조 : 먼저 넣은 데이터가 먼저 나옴
• 앞이 front, 뒤가 rear
• enqueue 연산 : rear 가 이동 후 해당 자리 데이터 추가
• dequeue 연산 : front가 이동 후 해당 자리의 데이터 반환

import java.util.LinkedList;
import java.util.Queue; //큐 import

//자료를 만들어서 사용 가능
class Node{
    int x;
    int y;

    public Node(int x, int y){
        this.x = x;
        this.y = y;
    }

    @Override
    public String toString() {
        return "Node{" +
                "x=" + x +
                ", y=" + y +
                '}';
    }
}


public class Practice {



    public static void main(String[] args){

        //큐는 LinkedList로 선언해야함
        Queue<Integer> queue = new LinkedList<>();

        //스택에 enqueue하기 : offer 또는 add
        queue.offer(1);
        queue.add(2);

        //프론트 갑 반환(삭제는 하지 않음)
        queue.peek();

        //프론트 값 반환하고 삭제 : poll 또는 remove 
        System.out.println(queue.poll());
        System.out.println(queue.remove());

        //비우기
        queue.clear();

        //비었는지확인
        queue.isEmpty();

        //정의한 객체타입으로 사용가능
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(1,2));
        q.add(new Node(3,4));

        System.out.println(q.remove().toString());
        
        //큐에 값이 있는지 확인 
        q.contains(3);

    }
}

다시풀어볼 문제

• 프린터

• 다리를 지나는 트럭 - 필요한 클래스를 만들어서 활용

import java.util.Queue;
import java.util.LinkedList;


class Truck{
    
    int weight;
    int move;
    
    public Truck(int weight){
        this.weight = weight;
        move = 1;
    }
    
    public void moving(){
        this.move +=1;
    }
}

class Solution {
    public int solution(int bridge_length, int weight, int[] truck_weights) {
        int answer = 0;
        
        Queue<Truck> bridge = new LinkedList<>();
        Queue<Truck> wait = new LinkedList<>();
        
        
        // wait 큐에 트럭들 추가 
        for (int truck : truck_weights){
            wait.add(new Truck(truck));
        }
        
        
        int totalWeight = 0;
        
        // bridge나 wait 큐가 전부 비면 중단
        while (!bridge.isEmpty()||!wait.isEmpty()){
            
            answer+=1;
            
            if (bridge.isEmpty()){
                Truck t = wait.remove();
                bridge.add(t);
                totalWeight+=t.weight;
                continue;
            }
            
            
            if (!bridge.isEmpty()){
                
                 //bridge에 있는 모든 트럭이 1칸씩 이동함
                for (Truck truck : bridge){
                    truck.moving();
                }

                //다리에 맨앞에 있는 트럭이 다리를 나갈만큼 움직였는지 확인해서 처리함 
                if (bridge.peek().move>bridge_length){
                    Truck t = bridge.remove();
                    totalWeight -= t.weight;
                    }
            }
            
            
            if (!wait.isEmpty()){
                if (weight>=totalWeight+wait.peek().weight){
                Truck t = wait.remove();
                bridge.add(t);
                totalWeight += t.weight;
                }
            }
           
        
        }
        
        
        
        return answer;
    }
}

큐나 스택은 반드시 iterator로 순회해야 하는줄 알았는데 그냥 for문을 이용해서도 순회가 가능하다.

• 주식가격

class Solution {
    public int[] solution(int[] prices) {
        
        int length = prices.length;
        int[] answer = new int[length];
        
        
        for (int i=0;i<length;i++){
            for (int j=i+1;j<length;j++){
                answer[i]++;
                if (prices[i]>prices[j]){
                    break;
                }
            }
        }
        
        
        return answer;
    }
}

나는 굉장히 복잡하게 생각했는데 다른 사람 풀이를 보니까 너무 간단하다

PriorityQueue

        //오름차순
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        //내림차순
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());

• 우선순위에 따라 정렬되는 큐