삽입(enqueue)과 삭제(dequeue)가 각각 다른 쪽에서 이루어지는 구조이다.
가장 먼저 삽입된 데이터부터 삭제된다.
큐의 크기는 동적으로 변경 가능하다.
일반적인 Queue
우선순위 Queue: 우선순위가 높은 데이터를 먼저 처리하는 큐
환형 Queue: 큐의 뒤와 앞이 이어져 있는 구조
삽입(enqueue): O(1)
삭제(dequeue): O(1)
탐색(front, rear): O(1)
데이터 삽입/삭제 방향의 차이: Queue는 뒤에서 삽입, 앞에서 삭제. Stack 뒤에서 삽입, 뒤에서 삭제한다.
데이터 접근 방향의 차이: Queue는 처음과 끝에서 모두 접근 가능. Stack은 끝에서만 접근 가능하다.
대기열, 그래프 알고리즘 등 다양한 분야에서 활용된다.
삽입과 삭제가 각각 다른 쪽에서 이루어지므로, 삽입된 데이터를 모두 삭제하지 않고 일부만 삭제하는 등의 작업이 어려움이 있다.
크기가 동적으로 변경 가능하므로, 큐의 최대 크기를 초과하지 않도록 주의해야 한다.
장점: 데이터 처리의 선입선출 구조를 갖고 있어, 다양한 분야에서 활용 가능하다.
단점: 단점: 중간에 삽입된 데이터를 삭제하는 것이 어렵고, 큐의 최대 크기를 초과하면 데이터를 삽입할 수 없다.
배열을 이용한 구현 방법에서 크기가 고정되어 있으므로, 메모리 낭비가 발생할 수 있다.
큐의 구현 방법에 따라 삽입, 삭제, 탐색 연산의 시간 복잡도가 달라질 수 있다.
문제 : 회전하는 큐 (백준 1021번)
지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.
지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.
첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.
큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
예제 입력 1
10 3
1 2 3
예제 출력 1
0
예제 입력 2
10 3
2 9 5
예제 출력 2
8
예제 입력 3
32 6
27 16 30 11 6 23
예제 출력 3
59
예제 입력 4
10 10
1 6 3 2 7 9 8 4 10 5
예제 출력 4
14
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Queue01 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");// " ", 기준으로 토큰화해서 관리할 수 있다. ex : 입력값 10 3
int size = Integer.parseInt(st.nextToken()); // 데이터를 읽고 int형으로 바꾼다. 첫번째 토큰값 10
int n = Integer.parseInt(st.nextToken()); // 다음 토큰값 3
ArrayList<Integer> numbers = new ArrayList<>(); //n개의 찾을값을 저장할 리스트
st = new StringTokenizer(bf.readLine(), " ");
for (int i = 0; i < n; i++) {
numbers.add(Integer.valueOf(st.nextToken())); // 위와 같이 토큰으로 나눠서 순서대로 넣어준다.
}
ArrayList<Integer> queue = new ArrayList<>(); // size만큼의 리스트, 이 코드에서는 queue처럼 동작시킬 것이다.
queue.addAll(IntStream.rangeClosed(1, size).mapToObj(Integer::valueOf).collect(Collectors.toList())); // queue에 1부터 size까지 수열을 넣어준다. (ex:1, 2, 3 ... size)
int cnt = 0; // 이동한 횟수를 저장할 count변수, 0으로 초기화
for (int j = 0; j < numbers.size(); j++) // 찾을 값만큼 반복한다. (ex:찾을값이 2,9,5 이면 3번 반복)
{
if (queue.indexOf(numbers.get(j)) <= queue.size() / 2) // 찾을값의 인덱스가 queue사이즈/2보다 작거나 같으면 왼쪽으로 이동하는게 더 빠르다.
{
for (int i = 0; i < queue.size() / 2; i++) // queue사이즈에 반만큼만 반복한다.
{
if (queue.get(0) == numbers.get(j)) { // 만약, 찾는 값이 나왔다면 break)
break;
}
Collections.rotate(queue, -1); // 찾는 값이 아니면 왼쪽으로 한칸 이동
cnt++; // 이동한 횟수 +=1
}
} else {
for (int i = 0; i < queue.size() / 2; i++) // 오른쪽으로 이동할 경우
{
if (queue.get(0) == numbers.get(j)) { // 만약, 찾는 값이 나왔다면 break)
break;
}
Collections.rotate(queue, 1); // 찾는 값이 아니면 오른쪽으로 한칸 이동
cnt++; // 이동한 횟수 +=1
}
}
queue.remove(0); // 맨앞에 있는값(찾는 값) 삭제
}
System.out.println(cnt); // 이동한 횟수 출력
}
}
[설명 예시]
list로 만든 queue : [1,2,3,4,5] (인덱스 0번부터 4번까지)
큐의 사이즈 : 5
출발위치(now) : 당연히 0번인덱스 부터
찾을 값 : 3 (인덱스 2번위치(goal==2)에 있다.)
알고리즘 ->
왼쪽으로 이동해야하는 횟수 : |0-2| = 2칸 (출발인덱스에서 찾을값의 인덱스 뺀 값)
오른쪽으로 이동해야하는 횟수 : 반대로 이동하는 거니까 queue사이즈에서 위의 값을 뺀값 == 5-2 == 3칸
둘 중 뭐가 적게 이동하니? => Math.min(왼쪽:2, 오른쪽:3) == 왼쪽! == 2!
그러면 왼쪽값만큼 이동횟수 카운트해줘 => cnt+=2
이제 찾았으니까, 값 3 삭제해줘 remove(goal)
출발위치 0에서, goal부터 시작하게끔 바꾸자 => now=goal
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Queue02 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int size = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int[] input = new int[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
input[i] = Integer.parseInt(st.nextToken());
}
int result = solution(size, n, input);
System.out.println(result);
}
public static int solution(int size, int n, int[] input) {
List<Integer> queue = new ArrayList<>(IntStream.rangeClosed(1, size).boxed().collect(Collectors.toList()));
int now = 0;
int cnt = 0;
for (int i = 0; i < n; i++) {
int goal = queue.indexOf(input[i]); // 찾을 값의 인뎃스
int gap = Math.abs(goal - now); // 왼쪽으로 이동거리
cnt += Math.min(gap, queue.size() - gap); // (왼쪽 vs 오른쪽)
queue.remove(goal); // 찾은값 제거
now = goal; // 출발지점 초기화
}
return cnt;
}
}
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int size = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
int[] numbers = Arrays.stream(bf.readLine().split(" "))
.mapToInt(Integer::valueOf)
.toArray();
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 1; i <= size; i++) {
queue.addLast(i);
}
int cnt = 0;
for (int j = 0; j < numbers.length; j++) {
int targetIndex = -1;
for (int i = 0; i < queue.size(); i++) {
if (queue.toArray()[i].equals(numbers[j])) {
targetIndex = i;
break;
}
}
int mid = queue.size() / 2;
if (targetIndex <= mid) {
for (int i = 0; i < targetIndex; i++) {
int temp = queue.removeFirst();
queue.addLast(temp);
cnt++;
}
} else {
for (int i = 0; i < queue.size() - targetIndex; i++) {
int temp = queue.removeLast();
queue.addFirst(temp);
cnt++;
}
}
queue.removeFirst();
}
System.out.println(cnt);
}
}
import java.io.*;
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Queue01 {
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
int size = Integer.parseInt(st.nextToken());
int n = Integer.parseInt(st.nextToken());
List<Integer> numbers = Arrays.stream(bf.readLine().split(" "))
.boxed()
.collect(Collectors.toList());
List<Integer> queue = IntStream.rangeClosed(1, size)
.boxed()
.collect(Collectors.toList());
int cnt = 0;
for (int j = 0; j < numbers.size(); j++) {
int targetIndex = queue.indexOf(numbers.get(j));
int mid = queue.size() / 2;
boolean isLeft = targetIndex <= mid;
for (int i = 0; i < mid; i++) {
if (queue.get(0) == numbers.get(j)) {
break;
}
Collections.rotate(queue, isLeft ? -1 : 1);
cnt++;
}
queue.remove(0);
}
bw.write(String.valueOf(cnt));
bw.flush();
bw.close();
}
}