0x06 Queue

스택과 마찬가지로 시험기간 겹침 이슈로 비슷하고 쉬운 유형의 기초문제들만 반복해서 푼 것으로 보입니다..
시험기간도 끝나고 스택, 큐, 덱 파트를 끝냈으니 BFS, DFS 파트의 더 어려운 문제에 도전해봐야겠습니다 ^-^

* P10845 - 큐

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Queue<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        int rear=0;
        for(int i=0;i<n;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            switch (st.nextToken()) {
                case "push" :
                    rear = Integer.parseInt(st.nextToken());
                    q.offer(rear);
                    break;
                case "pop" :
                    if(!q.isEmpty()) {sb.append(q.poll()).append('\n');}
                    else{sb.append(-1).append('\n');}
                    break;
                case "size" :
                    sb.append(q.size()).append('\n');
                    break;
                case "empty" :
                    if(q.isEmpty()) {sb.append(1).append('\n');}
                    else {sb.append(0).append('\n');}
                    break;
                case "front" :
                    if(q.isEmpty()) {sb.append(-1).append('\n');}
                    else {sb.append(q.peek()).append('\n');}
                    break;
                case "back" :
                    if(q.isEmpty()) {sb.append(-1).append('\n');}
                    else {sb.append(rear).append('\n');}
                    break;
            }
        }
        System.out.println(sb);
    }
}

---

* P2161 - 카드1

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); int l=0;
        Queue<Integer> q = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=n;i++) {q.offer(i);}
        while(true) {
            if(q.size()==1) { l=q.poll(); break;}
            sb.append(q.poll()).append(' ');
            q.offer(q.poll());
        }
        sb.append(l);
        System.out.println(sb);
    }
}

• head에서 카드를 뽑아 tail에 삽입 : FIFO : push와 pop을 다른 곳에서 : queue 사용

---

* P11866 - 요세푸스 문제 0

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder().append("<");
        Queue<Integer> q = new LinkedList<>();
        int n = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken());
        for(int i=1;i<=n;i++) {q.offer(i);}
        while(true) {
            if(q.isEmpty()) {sb.append(">"); break;}
            for(int i=1;;i++) {
                if(i%k==0) { sb.append(q.poll()); break;}
                else { q.offer(q.poll()); }
            }
            if(!q.isEmpty()) {sb.append(", ");}
        }
        System.out.println(sb);
    }
}

• 요세푸스문제 : 연결리스트 or 큐로 풀이 가능
• 연결리스트 : 직접 k만큼 next로 탐색하며 삭제
• 큐 : queue.push(queue.pop()) : tail에서 pop한 걸 그대로 head에 push하면 순서는 그대로 유지하며 탐색 가능
  : %k == 0 : 매 k번째마다 pop
  : queue가 빌 때까지 반복

---

* P2164 - 카드2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Queue<Integer> q = new LinkedList<>();
        for(int i=1;i<=n;i++) {  q.offer(i);   }
        while(true) {
            if(q.size()==1) {break;}
            q.poll();
            q.offer(q.poll());
        }
        System.out.println(q.poll());
    }
}

---

* P15828 - 라우터

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

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());
        Queue<Integer> q = new LinkedList<>();
        while(true) {
            int t = Integer.parseInt(br.readLine());
            if(t ==-1) {break;}

            if(t==0) {q.poll();}
            else if(q.size()<n) {q.offer(t);}
        }
        if(q.size()==0) {sb.append("empty");}
        while(!q.isEmpty()) {sb.append(q.poll()).append(" ");}
        System.out.println(sb);
    }
}

** 버퍼 **
: "입력한 순서대로" 처리한다 => 큐 사용

• 큐의 길이와 버퍼크기 비교하여 -> 넘치지 않으면 push
• 0이 나오면 pop