[묘공단] 자바 - Queue 이야기

https://www.geeksforgeeks.org/queue-interface-java/

태초에 Iterable이 계셨고 그 아래에 자식 Collection이 계셨고 그걸 또 Queue가 계승하셨네.

앞으로 Deque도 볼 건데 일단 머릿속에 큐(한 번 영어로 쓴 건 그 뒤로는 다 한글로 쓸 것임.)를 중심에 둬 보자.

왜냐면 덱 인터페이스가 큐 인터페이스를 상속하기 때문이다.

위 그림 상으로는 큐에 대해서 좀 보고 PriorityQueue만 보면 될 거 같지만

LinkedList도 봐야 한다.

왜? 링크드리스트는 List, 큐, 덱을 모두 구현하기 때문이다.

나 같은 범부는 여기까지만 봐도 너무 신기하고 재밌고 이 언어 설계한 사람들이 진짜 천재 같아서 가슴이 두근두근하다.

요즘 세상에 누가 자바 쓰냐고 하지만 나는 이 자바만 해도 너무 재밌을 거 같다! <- 안 해 보기 전엔 정말 자바는 개똥이며 2024년에 이런 걸 왜 하냐라고 생각함.

---

큐(Queue)는 자바에서 컬렉션 프레임워크의 일부로, 데이터를 FIFO (First In First Out) 방식으로 처리하는 추상 데이터 타입입니다. 큐는 요소를 순서대로 처리할 때 사용되며, 여러 구현체를 통해 다양한 방식으로 활용할 수 있습니다.

Queue 인터페이스

기본적인 특징

• FIFO (First In First Out): 큐의 가장 큰 특징은 첫 번째로 추가된 요소가 첫 번째로 제거된다는 것입니다.
• 멀티 스레드 환경에서의 활용: 일부 구현체는 멀티 스레드 환경에서 안전한 동시성을 제공합니다.

이거 밖에 없네? 딱히 딥하게 파야 할 게 없나 보다. 그러면 메서드로 바로 가자.

혹시 ADT로서의 큐에 대해 아무 것도 모르는 분이 있다면 나는 아래와 같이 설명한다.

큐는 빨대 같은 모양인데 무조건 뒤에서만 데이터를 넣을 수 있고 넣은 데이터는 앞으로만 나온다.

따라서 먼저 들어간 데이터가 먼저 나오는 구조를 하고 있다.

정말 이게 끝이다!

---

주요 메서드

1. boolean add(E e):
   1. 지정된 요소를 큐에 추가합니다. 큐에 여유 공간이 없으면 예외(IllegalStateException)를 발생시킵니다.
2. boolean offer(E e):
   1. 지정된 요소를 큐에 추가합니다. 공간이 없을 경우 false를 반환합니다.
3. E remove():
   1. 큐의 헤드를 제거하고 반환합니다. 큐가 비어 있으면 예외(NoSuchElementException)를 발생시킵니다.
4. E poll():
   1. 큐의 헤드를 제거하고 반환합니다. 큐가 비어 있을 경우 null을 반환합니다.
5. E element():
   1. 큐의 헤드를 반환하지만 제거하지는 않습니다. 큐가 비어 있으면 예외(NoSuchElementException)를 발생시킵니다.
6. E peek():
   1. 큐의 헤드를 반환하지만 제거하지는 않습니다. 큐가 비어 있을 경우 null을 반환합니다.

메서드도 간략하다. 그런데 조금 정리는 하자.

add, remove / offer, poll 이렇게 나누면 된다.

add해서 뒤에 데이터 넣고 remove해서 앞에서 데이터 뽑는 뒤 헤드를 제거한다.

큐가 꽉 차 있어 add할 수 없거나 큐가 비어 있어 remove할 수 없으면 예외가 발생한다.

헤드를 제거하면 어떻게 될까?

 

큐에서 데이터를 넣고 빼는 건 Enqueue, Dequeue라고도 한다.

add, remove / offer, poll 다 같은 의미다. 그래서 위 그림을 넣었다.

데이터를 제거했을 때 헤드가 제거되어 헤드가 remove된 다음 요소로 가는 게 보인다.

offer, poll도 동작 방식은 같은데 큐가 꽉 찼거나 비어서 동작을 수행할 수 없을 때 예외가 아닌 false, null을 반환하는 게 특징이다.

큐가 꽉 차 있으니 데이터를 넣는 데 실패해서 false를 반환하고, 큐가 비어서 remove를 할 수 없으니 큐가 비었다고 null을 반환한다.

정말 상식적이다.

element랑 peek도 마찬가지다.

element랑 peek은 데이터를 조회하는 용도라고 생각하면 된다.

큐 사이즈가 0이 아니면 안에는 데이터가 있다.

따라서 element나 peek으로 헤드에 있는 데이터를 조회하면 해당 데이터가 조회되고 헤드는 제거되지 않는다.

만약 큐가 비어 있어서 조회할 헤드가 없으면 element는 예외를 리턴하고 peek은 null을 반환한다. 

---

그런데 큐 사이즈가 0이란 것과 큐가 null이라는 것의 차이가 있을까? 있다면 뭘까?

 

큐 자체가 null인 상황과 큐의 사이즈가 0인 것은 두 가지 다른 개념입니다:

1. 큐가 null일 경우:
   1. 큐가 null이라는 것은 큐 객체가 초기화되지 않았거나 명시적으로 null로 설정되었다는 의미입니다. 이 상태에서 큐를 사용하려고 하면 NullPointerException이 발생합니다. 예를 들어, Queue<Integer> queue = null; 이후에 queue.add(1);를 시도하면 예외가 발생합니다.
2. 큐의 사이즈가 0일 경우:
   1. 큐의 사이즈가 0이라는 것은 큐가 초기화되어 있지만, 아직 아무런 요소도 추가되지 않았거나 모든 요소가 제거되었다는 것을 의미합니다. 이 상태에서는 큐에 요소가 없으므로, 요소를 꺼내려고 하면 (queue.remove() 또는 queue.element() 등) NoSuchElementException을 만날 수 있습니다. 그러나 이 상태는 null과는 다릅니다. 큐 객체 자체는 존재하지만, 그 안에 아무런 요소도 포함되어 있지 않는 상태입니다.

큐가 null이라는 건 해당 변수가 단순히 포인터로만 존재하고 아무런 객체도 참조하지 않고 있다는 뜻.

큐 사이즈가 0이라는 건 new를 통해 해당 객체가 만들어졌고 =을 통해 할당도 되었는데 다만 안에 아무 것도 없다는 뜻.

---

Queue 인터페이스의 주요 구현체

1. LinkedList:
   1. LinkedList는 List와 Deque 인터페이스를 함께 구현하며, 큐의 모든 연산을 지원합니다. 이중 연결 리스트 기반으로, 요소의 추가와 제거가 빠릅니다.
2. ArrayDeque:
   1. 배열을 기반으로 하는 더블 엔디드 큐(Deque)로, 더 효율적인 순차적 접근을 제공합니다. LinkedList보다 더 빠른 일반적인 큐 연산을 제공하며, 스택으로도 사용할 수 있습니다.
3. PriorityQueue:
   1. 우선순위 큐는 요소들이 자연 순서 또는 Comparator를 통해 제공된 순서에 따라 정렬됩니다. 이 큐는 힙(Heap) 구조를 내부적으로 사용하여 중간 요소의 접근과 수정이 일반 큐보다 복잡할 수 있습니다.
4. ConcurrentLinkedQueue:
   1. 스레드 안전하며 락-프리(lock-free) 알고리즘을 사용하는 비차단 큐입니다. 동시성이 중요한 환경에서 유용하게 사용됩니다.
5. ArrayBlockingQueue:
   1. 크기가 고정된 배열을 기반으로 하는 블로킹 큐입니다. 이 큐는 멀티스레드 환경에서 생산자와 소비자 스레드 간의 동기화를 위해 사용됩니다.

각 큐 구현체는 사용하는 환경과 요구 사항에 따라 선택할 수 있으며, 각각의 장단점을 이해하는 것이 중요합니다. 예를 들어, 대량의 데이터를 빠르게 처리해야 하고, 스레드 안전이 중요하지 않다면 ArrayDeque를 사용할 수 있습니다. 반면, 멀티 스레드 환경에서 안전하게 데이터를 추가하고 제거해야 할 경우 ConcurrentLinkedQueue나 ArrayBlockingQueue를 고려할 수 있습니다.

 

코테를 치는 입장에서는 1~3번만 잘 써도 충분할 거 같다.

---

지금 약간 글이 길어지고 있는데 큐에 대해서는 프라이어리티큐, 링크드리스트, 어레이덱을 다 볼 거기 때문에 따로 진행을 해야겠다.

예를 들어 포스팅 하나에 프라이어리티큐에 대한 이야기, 문제 풀이와 답변을 다 넣을 거다.

그럼 다음 페이지로 꼬우!

 

'코딩 테스트 합격자 되기 - 자바 편 프로그래머스 제공 97 문제로 완벽 대비'편을 읽고 공부하며 쓴 글입니다.

본 책을 펴 낸 골든래빗 출판사에서는 '묘공단'이라는 자체 스터디 프로그램을 운영 중인데요,

거기서 스터디 운영을 하면서 책도 보고 자바 자료구조와 알고리즘 공부도 하고 있네요.

 

심적으로 진입 장벽이 좀 있어서 진도가 쉬이 안 나갈 거 같은 주제나 책은 묘공단 프로그램을 통해

보다 편하게 공부할 수 있습니다.

골든래빗에서 이번에 C++로 코테 대비하는 책도 출간했으니 많관부~