Java: 큐(Queue)의 개념과 사용법, 요세푸스 순열

큐

먼저 들어간 것이 먼저 나가는 구조

FIFO(First In First Out)

 

상황으로 이해한다
a라는 일을 하고 있는데 a가 끝나면 b를 하라는 지시가 왔다
a가 끝나지 않은 상황에서 할 일을 모두 마치면 c를 하라는 지시가 왔다
a가 끝나지 않은 상황에서 할 일을 모두 마치면 d를 하라는 지시가 왔다
a가 끝났다. 다음의 할 일은?

 

 

큐는 보통 관모양으로 설명한다

관은 양쪽이 뚫려있다

a, b, c순으로 들어왔을 때 pop을 두번하면 c만 남는다
투 포인터, 슬라이딩 윈도우를 사용할 때 자주 사용하는 개념이다

 

큐의 활용

요세푸스 순열

요세프스 순열의 기원은 요세프스라는 인물이

유대-로마 전쟁시에 살아 남은 일화를 바탕으로 한다.

제1차 유대-로마 전쟁에서 예루살렘에서 갈릴리로 파견되어 갈릴리의 마을인 요타파타를 지키는 지휘관으로서 로마군에 맞섰으나, 로마군 사령관 베스파시아누스 플라비우스·티투스 부자가 지휘하는 로마군에게 패하고 만다. 이때 이방인에 대한 투항보다 차라리 자결하는 쪽을 택한 다른 유대인 지휘관들은 제비를 뽑아 서로 죽였지만, 마지막으로 요세푸스와 다른 병사 한 명이 남겨졌을 때 요세푸스는 그 병사를 설득해 함께 로마군에 투항하였다. 기원후 67년 7월의 일이었다.

자기가 살기 위해 치열하게 계산했을 요세프스...

n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.
예를 들어 (7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.          <위키백과>

위키백과 예시를 큐로 풀이해보자

1 2 3 4 5 6 7

4 5 6 7 1 2

이렇게 3번과 6번이 빠지게 된다

이미 지나간 수들은 다시 뒤로 들어오는데( 1 2 )

큐를 사용하면 원을 그리지 않고 풀이할 수 있다

 

Java에서 큐(Queue) 사용하기

Stack의 메소드를 비슷하게 사용하지만 달라진 부분들이 존재한다

클래스 연결

Stack과 다르게 2개를 import 해주어야 한다

Queue는 LinkedList를 연결해 사용하기 때문이다

 

import java.util.LinkedList; //Queue를 사용하기 위해 LinkedList를 import해야한다

import java.util.Queue;

 

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

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

 

이렇게 연결하면 Queue 클래스 내부의 메소드를 사용할 수 있다

스택에서 push는 .push()지만 큐에서는 .offer()

스택에서 pop은 .pop()지만 큐에서는 .poll()이다

개념	스택(Stack)	큐(Queue)
push	.push( 값 );	.offer( 값 ); / .add( 값 );
pop	.pop();	.poll(); / .remove();
top	.peek();	.peek();
size	.size();	.size();
empty	.isEmpty();	.isEmpty();

※ .add()와 .remove()는 큐가 꽉 찼거나 비어있을 때 사용하면 Exception 오류를 발생시킨다

※ .offer()은 큐가 비어있을 때 false를 .poll()은 큐가 비어있을 때 null을 반환하기 때문에 오류에서 좀 더 자유롭다