Day28-4. 자료구조 (7) Queue

큐(Queue)

: 선입선출(FIFO, First-In-First-Out) 방식으로 요소를 관리하는 자료구조

- 맨 앞에서부터 요소가 하나씩 제거되고, 새로운 요소는 항상 뒤에서 추가됨.

- 키보드 입력에 많이 쓰이곤 합니다.

 

<대표적인 클래스>

자바에서는 Queue 인터페이스를 구현한 여러 클래스가 제공되며,

그 중 대표적인 클래스로는 LinkedList와 PriorityQueue가 있다.

 

1. LinkedList

: LinkedList는 이중 연결 리스트(doubly linked list)를 구현한 클래스

- LinkedList를 이용해 구현한 큐는 삽입과 삭제가 매우 빠르지만, 검색 속도가 느리다.

 

2. PriorityQueue

: 이진 힙(binary heap)을 기반으로 하는 클래스로, 우선순위 큐(priority queue)를 구현한다.

- PriorityQueue는 요소를 우선순위에 따라 정렬하므로,

  가장 우선순위가 높은 요소를 먼저 꺼내는 것이 가능합니다.

- 검색 속도가 빠르지만, 삽입과 삭제가 느립니다.

 

<주요 메서드>

메서드	설명
boolean add(E e)	- 큐의 끝에 요소를 추가합니다. - 추가에 성공하면 true를 반환하고, 큐가 가득 차있는 경우 예외를 발생시킵니다.
boolean offer(E e):	- 큐의 끝에 요소를 추가합니다. - 추가에 성공하면 true를 반환하고, 큐가 가득 차있는 경우 false를 반환합니다.
E remove()	- 큐의 맨 앞에서 요소를 제거하고, 제거된 요소를 반환합니다. - 큐가 비어있는 경우 예외를 발생시킵니다.
E poll()	- 큐의 맨 앞에서 요소를 제거하고, 제거된 요소를 반환합니다.-  큐가 비어있는 경우 null을 반환합니다.
E element()	- 큐의 맨 앞에서 요소를 제거하지 않고, 그 요소를 반환합니다. - 큐가 비어있는 경우 예외를 발생시킵니다.
E peek()	-큐의 맨 앞에서 요소를 제거하지 않고, 그 요소를 반환합니다. - 큐가 비어있는 경우 null을 반환합니다.

 

위의 메서드 중 add(), offer(), remove(), poll() 메서드는 큐에서 요소를 추가하고 제거할 때 사용되며,

element(), peek() 메서드는 큐에서 요소를 검색할 때 사용됩니다.

---

 

<큐 예시 모양>

 

 

예제 >

package mega.backend_onemore.Day28;

import java.util.LinkedList;

public class QueueTest {

  public static void main(String[] args) {

    LinkedList<String> q = new LinkedList<String>();
    System.out.println("큐 offer : " + q.offer("한국"));
    System.out.println("큐 offer : " + q.offer("중국"));
    System.out.println("큐 offer : " + q.offer("미국"));
    System.out.println("큐 offer : " + q.offer("러시아"));
    System.out.println("큐 offer : " + q.offer("우크라이나"));
    System.out.println("큐 offer : " + q.offer("북한"));

    System.out.println("===============================");

    // "우크라이나"가 큐(Queue)의 몇 번째 위치에 있는지 찾습니다.
    int index = q.indexOf("우크라이나");
    if(index != -1) {
      System.out.println("큐에서 숫자 \"우크라이나\"의 위치는 : " + index + "번째 입니다.");
    }
    else {
      System.out.println("큐에서 숫자 \"우크라이나\"가 없습니다.");
    }
    System.out.println("===============================");

    // 큐(Queue)에서 값을 순서대로 빼내어 출력합니다.
    while(!q.isEmpty()) { // 비어있지 않다면(차있다면) 반복
      String obj = q.poll(); // 꺼내서
      System.out.println("poll : "+ obj); // 요소 전체출력
    }
  }

}

실행 결과

큐 offer : true
큐 offer : true
큐 offer : true
큐 offer : true
큐 offer : true
큐 offer : true
===============================
큐에서 숫자 "우크라이나"의 위치는 : 4번째 입니다.
===============================
poll : 한국
poll : 중국
poll : 미국
poll : 러시아
poll : 우크라이나
poll : 북한