[JAVA/자료구조] 자바 큐 Queue 사용법 / 큐의 특징과 예시 총 정리

▷ 큐(Queue)이란?

큐(Queue)는 FIFO(퍼스트 인 퍼스트 아웃) 원리를 기반으로 구성된 요소들의 집합을 나타내는 추상적인 데이터 유형이다.

큐는 스택과 다르게 양방향 자료구조이다. 즉 출구, 입구가 따로 따로 존재한다는 것이다.
스택의 삽입,삭제가 top에서 모두 이루어진다면 
큐는 -큐의 가장 앞 부분을 가리키는 front
-큐의 가장 뒷 부분을 가리키는 rear 에서 삽입, 삭제가 이루어진다.

큐에서 수행되는 작업은 다음과 같다.
큐의 rear에 데이터를 추가하는 add/offer, 
큐의 front의 데이터를 제거하고 null값으로 채우는 poll,  제거만 하는 remove, 초기화하는 clear
큐의 맨 앞(front)에 있는 요소를 제거하지 않고 액세스하는 peek

▷ 큐(Queue)의 특징?

큐 구조는 줄을 선 사람들과 같다. 

• FIFO(First-In First-out)

> 큐에 맨 처음 추가된 요소가 가장 먼저 제거 (줄을 먼저 선 사람이 먼저 빠짐)

• 스택의 양쪽 끝에서 액세스 가능

> 큐는 'rear'라고 하는 맨 뒤에서 삽입되고 'front'라고 하는 맨 앞에서 삭제된다.

• 일정한 시간 복잡성

> 빅오 표기법을 따라 O(1)의 일정한 시간으로 수행 가능 (O(n))

• BFS(넓이 우선 탐색)에 사용

> 알고리즘 그래프 구현 시 넓이 우선 탐색(BFS)에 사용되는 자료 구조이다.

• 동적 크기

> 큐는 연결리스트를 사용하여 구현한다. (LinkedList)

 

 

▷ 자바에서 큐(Queue) 을 어떻게 쓰나?

import java.util.Queue; <- 먼저 호출은 필수! LinkedList를 기본적으로 이용하기 때문에 

import java.util.LinkedList; <- 함께 호출해줍니다.

 

기초적인 실습을 통해 큐 구조를 익혀보자.

public class MyQueue {
    Queue<Element> queue = new LinkedList<Element>();

//값의 삽입(Enqueue)
    public void push(element) {
        queue.offer(element) //값이 꽉 찼을 경우 false 반환
        queue.add(element) //값이 꽉 찼을 경우 IllegalStateException 예외 발생
    }
//값의 제거(Dequeue)
    public pop() {
        return queue.poll() //비어있을 경우 null 반환
		//return queue.remove() //비어있을 경우 NoSuchElementException 발생
    }

    public peek() {
        return queue.peek() //비어있을 경우 null 반환
		//return queue.element() //비어있을 경우 NoSuchElementException 발생
    }
    
    public int size() {
        return queue.size();
    }

}

보면 알 수 있듯이 자바 Queue 클래스는 큐의 Enqueue와 Dequeue기능을 기본적으로 제공한다.

 

다음은 자바에서 Queue 클래스를 활용한 예시다.

 

 

[JAVA/백준] 2164번 : 카드2

 

 

---

 

 

지금까지 큐 자료 구조를 자바에서 어떻게 구현하는 지 예시를 통해 알아봤다.

큐와 함께 거론되는 스택과 함께 알고 있으면 좋다.

다음에는 우선순위 큐(Queue)에 대해 기회가 되면 정리해 보겠다.

 

 

 

 

>참고하기 좋은 글

[JAVA/자료구조] 자바 Stack 사용법 / 스택 예시 총 정리 - 문자열 뒤집기, 괄호 짝 맞추기