Queue란?
큐... 어디선가 많이 들어본 것 같다.
그렇다. 아마 롤에서 많이 사용했을 것이다.
큐 돌리자. 큐 잡혔다. 등등
물론 롤에는 티어와 MMR이 있기 때문에 조금 다르게 작동하겠지만, 근본적으로 자료구조의 Queue와 같은 원리를 가지고 있다.
롤의 큐는 먼저 돌려야 먼저 잡히는 게 일반적이다. 즉 선입선출(FIFO, First In First Out)이라고 할 수 있다.
마찬가지로 이번에 설명할 Queue도 먼저 삽입한 것이 먼저 나오는 선입선출이다.
너비 우선 탐색(BFS, Breadth First Search) 이라는 알고리즘에 사용되고, 그밖에도 많이 활용되므로 꼭!!!! 익혀두자.
들어가기 전에
Stack에는 push(), pop(), peek()를 활용해서 값을 추가, 삭제, 조회를 했다.
Queue에서는 offer(), poll(), peek()를 통해 추가, 삭제, 조회가 가능하다.
우선 간단한 움직임을 먼저 살펴보자.
감이 조금 오나? 생각보다 어렵지 않다.
add를 통해 값을 삽입한다. 그리고 poll을 통해 값을 제거한다.
이때 제거되는 것은 가장 먼저 삽입한 요소!!!
이것만 알면 오늘 수업 끝이다.
라고 했지만, 진짜로 끝낼 수는 없다.
사용 방법
Queue 선언
큐를 사용하기 위해서는 큐를 먼저 선언해야만 한다.
import java.util.LinkedList;
import java.util.Queue;
public class Main { // 큐를 사용하기 전에 꼭 선언해야 한다.
public static void main(String[] args) {
// <Charater>는 queue에 Character 값만 추가하겠다는 의미
Queue<Character> queue = new LinkedList<>();
}
}
<Character> 만 넣을 수 있는 queue를 선언했다.
Stack 편에서 배웠던 것처럼 만약 숫자를 넣고 싶다면 <Integer> 또는 <Long>, 문자열을 넣고 싶다면 <String>으로 변경해주면 된다.
Queue에 값 넣기 - offer(값)
큐에 값을 넣는 방법은 크게 add()와 offer() 이 두 가지 방법이 있다.
둘 다 같은 동작을 하지만, 일반적인 큐가 아닌 크기 제한이 있는 큐에 삽입할 때 add()는 에러가 발생할 수도 있다.
그래서 나는 offer()를 추천하고 싶다. (그런데 상단 이미지에는 add()로 해버림...)
사실 Java에서 쓰는 일반적은 큐는 add()를 사용해도 문제가 없다... 왜냐하면 크기에 제한이 없기 때문.
반면 실무에서는 서버 과부화를 막기 위해 크기가 제한된 큐를 많이 사용하며, 이때 offer()로 값을 넣다 실패하면 에러가 아닌 false가 반환된다.
이제 다음 코드 확인해 보자.
Queue<Character> queue = new LinkedList<>();
queue.offer('A'); // queue에 문자 A 추가. add('A')도 가능.
<Character>로 선언했기 때문에 char 타입의 'A'를 넣어보았다.
정말 쉽다.
Queue에서 값 제거 - poll()
지금 queue에는 'A'라는 값이 딱 하나 존재한다.
그것을 제거하기 위해서는 poll() 이라는 메서드를 사용하면 된다.
다음 코드를 보자
Queue<Character> queue = new LinkedList<>();
queue.offer('A'); // 큐에 'A' 추가
char value = queue.poll(); // 큐의 맨 앞을 뽑아서 value에 저장
System.out.println(value); // 'A' 출력
단순히 queue.poll()을 하게 되면 맨 앞의 값이 제거되고, 변수명을 선언해서 값을 저장하는 것도 가능하다.
지금은 'A' 하나만 넣고, 바로 뽑았지만, A 다음에 B, C, D ... 를 넣어도 가장 처음에 poll()을 하면 'A'가 뽑히게 된다.
왜냐하면 아까 설명했듯이 큐는 선입선출이기 때문!!!!
Queue 값 조회 - peek()
이제 offer()와 poll()을 통해 삽입, 삭제가 가능해졌다.
이제부터는 stack과 비슷하다.
peek()... 이 녀석은 큐에서 바로 뽑아서 쓸 수 있는 값을 조회할 때 쓸 수 있다.
값은 삭제되지 않고, 조회만 한다.
그렇기 때문에 poll() 과는 다른 용도로 많이 쓰인다.
다음 코드를 보자.
Queue<Character> queue = new LinkedList<>();
queue.offer('A');
queue.offer('B'); // 이번에는 'A'와 'B'를 넣었다.
char value1 = queue.peek(); // 조회
char value2 = queue.poll(); // 삭제
System.out.println(value1 + ", " + value2); // 과연 정답은...?value1에는 맨 앞의 값을 조회만 했기 때문에 'A'가 저장된다.
value2에는 맨 앞의 값을 뽑았기 때문에 마찬가지로 'A'가 저장된다.
이것이 peek()의 특징!!! 조회만 하고 값을 그대로 둔다!!!!
그래서 출력은 A, A가 된다.
참 쉽다.
Queue 추가 활용 - size(), isEmpty()
이것도 stack에서 배웠다. 더 볼 것도 없다.
일단 이름부터가 어떤 기능을 하는지 다 알려주고 있다.
size() > 큐의 사이즈는?
isEmpty() > 큐가 비었나?
다음 코드를 보자.
Queue<Character> queue = new LinkedList<>();
boolean check1 = queue.isEmpty(); // 값을 넣기 전에 확인
int size1 = queue.size();
queue.offer('A');
queue.offer('B');
boolean check2 = queue.isEmpty(); // 값을 넣은 후에 확인
int size2 = queue.size(); // 사이즈는?
System.out.println(check1 + ", " + check2);
System.out.println(size1 + ", " + size2); // 과연 출력 결과는?
여기까지 온 여러분이라면 벌써 결과를 알아냈을 것 같다.
true, false
0, 2
아마 결과는 이렇게 나올 것이다.
왜냐??
값을 넣기 전에는 비어있기 때문에 isEmpty()는 true를 반환하고, size()는 당연히 0이 된다.
값을 넣은 후에는 queue가 isEmpty()가 아니게 되므로, false를 반환, size()는 2가 된다.
와.... 진짜 너~~무 쉽다.
이걸로 stack이랑 queue까지 정복했다.
그런데 이전에 stack 대신에 Deque를 쓰면 좋다고 했던 말 기억나나?
놀랍게도 큐도 LinkedList 대신에 Deque를 사용하는 것이 더 효율적이다.
왜냐하면 두 개의 원리가 동작 원리가 다르기 때문이다.
(그리고 Deque보다도 배열에 투포인터를 쓰는 것이 더 빠르다...)
이것에 대해서는 나중에 더 알아보도록 하자. 혹시 선행을 하게 된다면 댓글로 정리 부탁.