[선형 자료구조] 큐 (Queue)

제로베이스의 자료구조 과제 중 큐와 관련된 문제가 나와 공부하면서 내용을 정리해본다.

---

💡 큐 (Queue)

• 선입선출 (First In First Out ; FIFO) 자료구조 : 먼저 들어온 데이터가 먼저 나가는 구조
• 입력 순서대로 데이터 처리가 필요할 때 사용한다.
  ex. 프린터 출력 대기열, BFS (Breath-First Search) 등

👉 큐 기본 구조

• 선입선출 구조를 따른다.
• 기본적으로 데이터를 추가, 꺼내기, 큐 공간 확인 동작으로 이루어져있다.

👉 큐 기본 연산

• 데이터 저장 (Enqueue) : 큐에 데이터 추가 (offer)
• 데이터 추출 (Dequeue) : 큐에서 데이터 꺼내기 (poll)

👉 큐의 메서드

📖 처음 보는 메서드를 공부할 때는 꼭 공식 문서를 먼저 살펴보자.

메서드	설 명
boolean add(Object o)	지정된 객체를 Queue에 추가한다. 성공하면 true 반환. 저장공간이 부족하면 IllegalStateException 발생한다.
Object remove()	Queue에서 객체를 꺼내 반환한다. 비어있으면 NoSuchElementException 발생한다.
Object element()	삭제없이 요소를 읽어온다. peek 와 달리 Queue 가 비었을 때 NoSuchElementException 발생한다.
boolean offer(Object o)	Queue에 객체를 저장한다. 성공하면 true 실패하면 false 를 반환한다.
Object poll()	Queue에서 객체를 꺼내서 반환한다. 비어있으면 null 을 반환한다. (예외가 발생하지 않는다.)
Object peek()	삭제없이 요소를 읽어 온다. Queue가 비어있으면 null 을 반환한다.

👉 큐 인터페이스를 구현한 클래스 사용하기

• 큐를 구현하기 위한 방법은 직접 구현하거나 구현한 클래스를 사용하는 방법이다.
• 링크드리스트는 삭제 시 자리이동이 필요없기 때문에 큐를 구현할 때 링크드리스트를 사용한다.

Queue g = new LinkedList();
g.offer("o");

📖 최근 검색 기록 조회 예제

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

public class Main {

    static Queue q = new LinkedList();
    static final int MAX_SIZE = 5;  // Queue에 최대 5개까지만 저장되도록 한다.

    public static void main(String[] args) {
        System.out.println("help를 입력하면 도움말을 볼 수 있습니다.");

        while (true) {
            System.out.print(">> ");
            try{
                // 화면으로부터 라인단위로 입력받는다.
                Scanner sc = new Scanner(System.in);
                String input = sc.nextLine().trim();

                if("".equals(input)) continue;

                if(input.equalsIgnoreCase("q")){    // 대소문자를 구분하지 않고 비교
                    System.exit(0);
                } else if(input.equalsIgnoreCase("help")){
                    System.out.println(" help - 도움말을 보여줍니다.");
                    System.out.println(" q 또는 Q - 프로그램을 종료합니다.");
                    System.out.println(" history - 최근에 입력한 명령어를 " + MAX_SIZE + "개 보여줍니다.");
                } else if(input.equalsIgnoreCase("history")){
                    save(input);    // 입력받은 명령어를 저장한다.

                    LinkedList list = (LinkedList) q;   // LinkedList의 내용을 보여준다.

                    for (int i = 0; i < list.size(); i++) {
                        System.out.println((i + 1) + "." + list.get(i));
                    }
                } else {
                    save(input);
                    System.out.println(input);
                }   // if(input.equalsIgnoreCase("q")) {
            } catch (Exception e){
                System.out.println("입력오류 입니다.");
            }
        }
    }

    public static void save(String input){
        if(!"".equals(input))   // input이 공백이 아니면
            q.offer(input);     // Queue에 저장

        if(q.size() > MAX_SIZE) // Queue의 최대 크기를 넘으면
            q.remove();         // 제일 처음 입력된 데이터 삭제
    }
}