Dico

[Java] Class Queue

Collection Framework

데이터 군을 저장하는 클래스들을 표준화한 설계

컬렉션 Collection :  다수의 데이터. 데이터 그룹

프레임웍 Framework :  표준화된 프로그래밍 방식.

Class Queue

처음에 저장한 데이터를 가장 먼저 꺼내는 FIFO(First In First Out) 방식의 자료 구조.  ex) 밑 빠진 독

순서의 변경 없이 먼저 넣은 것을 먼저 꺼내게 된다.

데이터를 꺼낼 때 항상 첫 번째 저장된 데이터를 삭제하므로 데이터의 추가/삭제가 쉬운 LinkedList로 구현하는 것이 적합하다.

Java에서 Queue 인터페이스로만 정의하여 이를 구현한 클래스들을 사용한다.

Known Indirect Subclasses

Queue 인터페이스에 정의된 기능을 사용하고 싶다면 다음 중 적당한 것을 하나 골라서 사용한다.

AbstractQueueArrayBlockingQueueArrayDequeBlockingDequeBlockingQueue
ConcurrentLinkedDequeConcurrentLinkedQueueDelayQueueDequeLinkedBlockingDeque
LinkedBlockingQueueLinkedListLinkedTransferQueuePriorityBlockingQueuePriorityQueue
SynchronousQueueTransferQueue

method

반환타입이름설명
  abstract boolean  add(E e)  지정된 객체 추가. 성공하면 true.
  저장 공간이 부족하면 IllegalStateException 발생
  abstract E  element()  삭제 없이 요소를 읽어온다.
  비어있으면 NoSuchElementException 발생
  abstract boolean  offer(E e)  객체 저장. 성공하면 true
  abstract E  peek()  삭제 없이 요소를 읽어온다. 비어있으면 null
  abstract E  poll()  객체를 꺼내서 반환. 비어있으면 null
  abstract E  remove()  객체를 꺼내 반환. 비어있으면 NoSuchElementException 발생

Class PriorityQueue

Queue 인터페이스의 구현체 중 하나.

저장공간으로 배열을 사용하며, 각 요소를 힙(heap)의 형태로 저장한다.

저장 순서와 관계없이 우선순위가 높은 것부터 꺼낸다.

null을 저장하면 NullPointerException이 발생한다.

  • 우선순위 priority

     객체 :  각 객체의 크기를 비교할 수 있는 방법을 제공해야 한다.

     숫자 :  작을 수록 높다. Number의 자손들은 자체적으로 숫자를 비교하는 방법을 정의하고 있다.

Queue<Integer> qu = new PriorityQueue<>();
qu.offer(1);                           // qu.offer(new Integer(1)); 오토박싱

Class Deque

Double-Ended Queue. 덱 또는 디큐라고 읽는다.

양쪽 끝에 추가/삭제가 가능.

구현체 :  ArrayDeque, LinkedList 등

  • Queue + Stack
DequeQueueStack
offerLast()offer()push()
pollLast()pop()
pollFirst()poll()
peekLast()peek()
peekFirstpeek()

Example

최근 사용한 것의 목록을 보여주는 기능.

package queue;

import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
import java.util.ListIterator;

public class Test {
    static Queue<String> q = new LinkedList<>();
    static final int MAX_SIZE = 5;

    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);  
        String input = "";

        while(!input.equalsIgnoreCase("end")){
            System.out.print("명령어를 입력해주세요: ");
            input = scan.nextLine();
                 
            if (input.equals("")) {
                continue;
            }
            
            if (input.equalsIgnoreCase("help")) {
                print("help - 도움말");
                print("end - 프로그램 종료");
                print("history - 최근에 입력된 명령어 " + MAX_SIZE + "개");
            } else if (input.equalsIgnoreCase("history")) {
                save(input);
            
                LinkedList<String> tmp = (LinkedList<String>) q;
                ListIterator it = tmp.listIterator();
            
                while (it.hasNext()) {
                    print(it.next().toString());
                }
            } else {
                save(input);
                print(input);
            }
        }
    }
   
    public static void save(String input) {
        if(!input.equals("")){
            q.offer(input);
        }

        if(q.size() > MAX_SIZE){
            q.remove();
        }
    }

    public static void print(String str) {
        System.out.println(str);
    }
}
명령어를 입력해주세요: HELP
help - 도움말
end - 프로그램 종료
history - 최근에 입력된 명령어 5개
명령어를 입력해주세요: LIST
LIST
명령어를 입력해주세요: OPEN
OPEN
명령어를 입력해주세요: LOGIN
LOGIN
명령어를 입력해주세요: HISTORY
LIST
OPEN
LOGIN
HISTORY
명령어를 입력해주세요: END
END

Oueue API

Deque API

PriorityQueue API

참고 서적: 자바의 정석 3판 2