LinkedList

ref: Googling based on chatGPT's response (There could be some errors)

In Java, the LinkedList class implements the Deque interface which in turn extends the Queue interface.

Java LinkedList Hierarchy

큐2

https://www.acmicpc.net/problem/18258

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

push X: 정수 X를 큐에 넣는 연산이다.
pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 큐에 들어있는 정수의 개수를 출력한다.
empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

Queue 인터페이스의 경우 큐의 가장 뒤에 있는 원소를 출력하는 메서드가 내장되어 있지 않으므로
LinkedList 클래스의 peekLast() 메서드를 사용하여 문제의 back을 표현해 준다.

한편 매 루프마다 출력하는 경우 시간 초과가 되므로 StringBuilder를 사용하여 루프 후 한번만 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
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());

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            String command = st.nextToken();

            switch (command) {
                case "push":
                    int X = Integer.parseInt(st.nextToken());
                    queue.offer(X);
                    break;
                case "pop":
                    if (queue.isEmpty())
                        sb.append(-1).append("\n");
                    else
                        sb.append(queue.poll()).append("\n");
                    break;
                case "size":
                    sb.append(queue.size()).append("\n");
                    break;
                case "empty":
                    if (queue.isEmpty())
                        sb.append(1).append("\n");
                    else
                        sb.append(0).append("\n");
                    break;
                case "front":
                    if (queue.isEmpty())
                        sb.append(-1).append("\n");
                    else
                        sb.append(queue.peek()).append("\n");
                    break;
                case "back":
                    if (queue.isEmpty())
                        sb.append(-1).append("\n");
                    else
                        sb.append(queue.peekLast()).append("\n");
                    break;
            }
        }

        System.out.println(sb.toString());
        br.close();
    }
}

회전하는 큐

https://www.acmicpc.net/problem/1021

N개의 원소를 포함하고 있는 양방향 순환 큐에서 M개의 원소를 뽑아내려고 한다.
회전 연산의 최솟값을 출력하는 프로그램을 작성하시오.

최소 회전수는 Math.min을 활용하거나, 루프마다 각 분기에서 count++하여 회전수를 셀 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.LinkedList;
import java.lang.Math;

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

		// Let's implement Circular Queue with LinkedList
        LinkedList<Integer> cq = new LinkedList<>();
        int N = Integer.parseInt(firstLine.split(" ")[0]);
        int M = Integer.parseInt(firstLine.split(" ")[1]);

        // Initialize cq
        for (int i = 1; i <= N; i++) cq.offer(i);
        
        String secondLine = br.readLine();
        //둘째 줄에는 뽑아내려고 하는 수의 위치가 순서대로 주어진다.
        //수의 위치를 배열에 순서대로 저장
        int[] p = new int[M]; 
        String[] splited = secondLine.split(" ");
        for (int i = 0; i < M; i++) {
            p[i] = Integer.parseInt(splited[i]);
        }

        int minRsum = 0;
        for (int i = 0; i < M; i++) {
            int left = cq.indexOf(p[i]); // 숫자 위치의 인덱스 값 = 왼쪽 회전수
            int right = cq.size() - left; // 오른쪽 회전수
			minRsum += Math.min(left, right);
				
            if (left <= right) { // 왼쪽 회전
                for (int j = 0; j < left; j++) {
                    int temp = cq.pollFirst();
                    cq.addLast(temp);
                }
            } else { // 오른쪽 회전
                for (int j = 0; j < right; j++) {
                    int temp = cq.pollLast();
                    cq.addFirst(temp);
                }
            }
            cq.pollFirst(); // 회전 후 해당 값 뽑아내기
        }
        System.out.println(minRsum);
    }
}