[자료구조] 큐(Queue) (Java)

 

큐란? 쉽게 보면 대기줄이다

우리가 흔히 줄을 설 때 온 순서대로 차례로 입장한다.

먼저 들어간 것이 먼저 나온다.

=> 선입선출(FIFO)

 

 

큐의 앞부분 front에서는 삭제 연산만 수행하고

큐의 뒷부분 rear에서는 삽입 연산만 수행한다.

 

차근차근 큐에 쌓아보기

삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()의 과정을 수행해 보자.

 

 

삽입(5)

5

 

삽입(2)

5 2

 

삽입(3)

5 2 3

 

삽입(7) 

5 2 3 7

 

삭제() 

2 3 7

 

삽입(1)

2 3 7 1

 

삽입(4)

 2 3 7 1 4 

 

삭제() 

3 7 1 4

=> 삽입을 통해 데이터를 차례대로 쌓고 삭제를 통해 들어온 순서대로 데이터를 내보낸다.

 

코드로 구현

 

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

// 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
q.offer(5);
q.offer(2);
q.offer(3);
q.offer(7);
q.poll();
q.offer(1);
q.offer(4);
q.poll();

while (!q.isEmpty()) {
    System.out.print(q.poll() + " ");
}

 

큐와 함께 쓰이는 함수들

 

원소 추가

- q.add()

boolean add(E e);

 

- q.offer()

boolean offer(E e);

 

<공통점>

큐의 맨 뒤에 값을 추가하고 성공 시 true를 반환한다.

 

<차이점>

큐의 용량 제한 때문에 더 추가할 수 없는 경우

q.add(): IllegalStateException 발생

q.offer(): false 반환

 

 

원소 삭제

- q.remove()

E remove();

 

- q.poll()

E poll();

 

<공통점>

큐의 맨 앞 원소를 삭제하고 성공 시 해당 값을 반환한다.

 

<차이점>

큐가 비어있는 경우

q.remove(): NoSuchElementException 발생

q.poll(): null 반환

 

+) 큐 비우기

- q.clear()

void clear();

 

맨 앞 원소 확인

- q.element()

E element();

 

- q.peek()

E peek();

 

<공통점>

큐의 맨 앞 원소 값을 반환한다.

 

<차이점>

큐가 비어있는 경우

q.element(): NoSuchElementException 발생

q.peek(): null 반환

 

💟정리

add(), remove(), element()와 offer(). poll(), peek()의 차이는

문제 상황에서 Exception을 발생시키는지 false 혹은 null을 반환시키는 지의 차이이다.

 

Reference

이것이 코딩 테스트다 - 나동빈

https://cocoon1787.tistory.com/774