[자료구조] Queue

큐 란?

줄 서기 같이 먼저 온 사람이 먼저 나가는 것 처럼 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 FIFO(First In First Out) 자료구조.
Enqueue : 큐 맨 뒤에 데이터 추가
Dequeue : 큐 맨 앞쪽의 데이터 삭제

큐는 stack과 달리 별도의 'Queue'클래스가 존재하지 않는다. 대신, 큐를 다루기 위한 인터페이스인 'Queue'를 제공하여 다양한 구현체(LinkedList, ArrayDeque, PriorityQueue 등)를 이용해 큐를 생성하고 다룬다. 주로 LinkedList를 이용하여 생성한다.
Queue 인터페이스를 구현한 다양한 클래스들을 사용하여 개발자는 자신의 요구사항에 맞는 큐를 선택하여 사용할 수 있다. 예를 들어, LinkedList는 일반적인 큐를 구현하는 데 유용하고, ArrayDeque는 큐의 용량을 동적으로 조절하면서 빠른 성능을 제공하며, PriorityQueue는 우선순위 큐를 구현하는 데 사용된다.
자바에서 큐를 다루는 방식은 큐를 직접 구현하지 않아도 다양한 구현체를 사용할 수 있도록 인터페이스를 활용하는데, 이는 디자인 패턴 중 생성패턴의 '추상 팩토리 패턴'과 유사한 구조를 가진다고 한다.

큐 특징

1. 큐는 삽입과 삭제 연산이 FIFO(First In First Out) 로 이루어진 구조
2. 삽입과 삭제가 양방향으로 이루어지며 가장 끝의 데이터는 rear, 가장 앞의 데이터는 front라고 한다.
3. front에서는 삭제 연산만, rear에서는 삽입 연산만 이루어진다.
4. BFS(넓이우선탐색)에서 자주 사용된다.
5. 멀티스레드 환경에서 큐는 작업 대기열을 관리하거나 작업 스케줄링에 사용된다..
6. 큐는 요소를 추가, 제거하는 연산이 O(1)의 시간 복잡도를 가진다. (LinkedList를 이용해 구현할 때를 생각하면 쉽다.)

큐 사용법

Queue 선언

import java.util.Queue;
import java.util.LinkedList;

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

Queue 삽입 : Enqueue

import java.util.Queue;
import java.util.LinkedList;

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

queue.add(1);
queue.add(2);
queue.offer(3);

add(e) : 삽입 성공 시 true 반환, 용량 초과로 삽입 실패 시 IllegalStateException 발생.
offer(e) : 삽입 성공 시 true 반환, 용량 초과로 삽입 실패 시 false 반환.

Queue 삭제 : Dequeue

import java.util.Queue;
import java.util.LinkedList;

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

queue.add(1);
queue.add(2);
queue.offer(3);

queue.poll();	// 결과 : 1
queue.remove();	// 결과 : 2

queue.clear()	//  큐의 모든 요소 제거

remove() : 헤드 요소를 조회(출력 가능)하고 제거, 큐가 비어 있다면 예외 발생.
poll() : 헤드 요소를 조회(출력 가능)하고 제거, 큐가 비어 있다면 null 반환.

Queue 조회

import java.util.Queue;
import java.util.LinkedList;

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

queue.add(1);
queue.add(2);
queue.offer(3);

System.out.println(queue.element());	// 결과 : 1
System.out.println(queue.peek());	// 결과 : 1

element() : 헤드 요소 조회 및 반환, 하지만 큐가 비어 있다면 예외 발생
peek() : 헤드 요소 조회 및 반환, 하지만 큐가 비어 있다면 null 반환

위 메소드들의 차이가 궁금해서 찾아본 내용

출처 : https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

즉, 작업 결과에 따라 예외를 발생시킬지, 아니면 특별한 값을 반환시킬지에 따라 사용할 메소드가 나뉜다는 것이다.

기타

Methods declared in interface java.util.Collection

addAll, clear, contains, containsAll, equals, hashCode, isEmpty, iterator, parallelStream, remove, removeAll, removeIf, retainAll, size, spliterator, stream, toArray, toArray, toArray

이러한 메소드들을 사용할 수 있다.

Methods declared in interface java.lang.Iterable

forEach

자바에서 컬렉션 프레임워크의 모든 컬렉션들은 forEach 메서드를 지원하며, 이 메서드는 컬렉션의 각 요소를 반복하여 처리하는데 사용된다.

// queue forEach 구현 예시

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        Queue<String> queue = new LinkedList<>();
        queue.offer("First");
        queue.offer("Second");
        queue.offer("Third");

        queue.forEach(System.out::println); // 결과 : First Second Third
    }
}

위 코드에서 forEach 메서드는 Queue의 구현 클래스인 LinkedList가 상속받은 Iterable 인터페이스의 메서드를 사용하여 요소를 처리한다.

---

혹시라도 틀린 내용이 있으면 둥글게 둥글게 지적 해주시면 감사하겠습니다..
둥글게 둥글게.. 지구도 둥그니까.. 둥글게 둥글게..

---

참고:
https://coding-factory.tistory.com/602
https://go-coding.tistory.com/6
https://imyena.tistory.com/99
https://velog.io/@ha0kim/Design-Pattern-%EC%83%9D%EC%84%B1-%ED%8C%A8%ED%84%B4Creational-Patterns