Queue 이론과 구현

 

 

📌 Queue<E> 컬렉션

- Stack<E>와는 달리 별도의 interface로 구성

- 먼저 들어간 데이터가 먼저 나오는 FIFO(First in First out) 구조

- LinkedList<E> 클래스는 List<E>와 Queue<E> interface를 구현

 

 

✅ 예외처리기능 미포함 메서드 → 데이터가 없는 경우 예외 발생

예) add(), remove(), element()

 

✅  예외처리기능 포함 메서드 → 데이터가 없는 경우 기본값 출력 (null)

예) offer(), poll(), peek()

 

 

---

 

📌 Queue<E> 컬렉션 주요 메서드

구분		리턴타입	메서드 이름	기능
예외처리 기능 미포함 메서드	데이;터 추가	boolean	add(E item)	매개변수의 item을 Queue에 추가
	데이터 보기	E	element()	가장 상위에 있는 원소 값 리턴 (데이터는 변화가 없음) (데이터가 하나도 없는 경우 NoSuchElementException 발생)
	데이터 꺼내기	E	remove()	가장 상위에 있는 원소 값 꺼내기 (데이터는 변화가 있음) (데이터가 하나도 없는 경우 NoSuchElementException 발생)
예외처리 기능 포함 메서드	데이터 추가		offer(E item)	매개변수의 item을 Queue에 추가
	데이터 보기	E	peek()	가장 상위에 있는 원소 값 리턴 (데이터는 변화가 없음) (데이터가 하나도 없는 경우 null 리턴)
	데이터 꺼내기	E	poll()	가장 상위에 있는 원소 값 꺼내기 (데이터는 변화가 있음) (데이터가 하나도 없는 경우 null 리턴)

 

 

예시코드)

public class QueueMethod {
    public static void main(String[] args) {

        //#1. 예외처리기능 "미포함" 메서드
        Queue<Integer> queue1 = new LinkedList<>();

        //        System.out.println(queue1.element()); //예외발생

        //@1-1. add(E item)
        queue1.add(3);
        queue1.add(4);
        queue1.add(5);
        System.out.println(queue1);

        //@1-2. element()
        System.out.println(queue1.element()); //3
        System.out.println();

        //@1-3. remove()
        System.out.println(queue1.remove()); //3
        System.out.println(queue1.remove()); //4
        System.out.println(queue1.remove()); //5
//        System.out.println(queue1.remove()); //예외발생



        //#2. 예외처리기능 "포함" 메서드
        Queue<Integer> queue2 = new LinkedList<>();

        System.out.println(queue2.peek()); //null : 예외발생 X

        //@2-1. offer(E item)
        queue2.offer(3);
        queue2.offer(4);
        queue2.offer(5);

        //@2-2. E peek()
        System.out.println(queue2.peek());

        //@2-3. E poll()
        System.out.println(queue2.poll()); //3
        System.out.println(queue2.poll()); //4
        System.out.println(queue2.poll()); //5
        System.out.println(queue2.poll()); //null : 예외발생 X

    }
}

 

 

---

 

💡Queue 구현

- 다음과 같이 예외처리 기능 포함 메서드들을 구현해봤다.

 

public class MyQueue <T>{
    private static class Node<T>{
        private T data;
        private Node<T> next;

        Node(T data){
            this.data = data;
        }

    }

    private Node<T> front;
    private Node<T> rear;
    private int size;

    public MyQueue(){
        this.front = null;
        this.rear = null;
        this.size = 0;
    }

    public boolean isEmpty(){
        return size == 0;
    }

    public void offer(T data){
        Node<T> newNode = new Node<>(data);
        if(rear != null){
            rear.next = newNode;
        }
        rear = newNode;

        if(front == null){
            front = rear;
        }
        size++;
    }

    public T poll(){
        if(isEmpty()){
            return null;
        }

        T data = front.data;
        front = front.next;
        if(front == null){
            rear = null;
        }
        size--;
        return data;
    }

    public T peek(){
        if(isEmpty()){
            return null;
        }
        return front.data;
    }

    public int size(){
        return size;
    }
}

 

 

---

 

필드, 메서드, 내부 클래스

 

- Node 클래스: 데이터를 저장하고 다음 노드를 가리킴

private static class Node<T> {
    private T data;       // 노드의 데이터
    private Node<T> next; // 다음 노드를 가리키는 참조

    Node(T data) {
        this.data = data;
    }
}

private Node<T> front; // 큐의 앞쪽 노드를 가리키는 포인터
private Node<T> rear;  // 큐의 뒤쪽 노드를 가리키는 포인터
private int size;      // 큐의 크기를 나타내는 변수

public MyQueue() {
    this.front = null; 
    this.rear = null;  
    this.size = 0;    
}

 

 

---

 

큐가 비어있는지 확인 (isEmpty)

 

public boolean isEmpty() {
    return size == 0; // 큐 크기가 0이면 true 반환
}

 

 

---

 

큐에 데이터 추가 (offer)

 

public void offer(T data) {
    Node<T> newNode = new Node<>(data); // 새로운 노드 생성
    if (rear != null) { // 큐가 비어 있지 않다면
        rear.next = newNode; // 기존 rear의 next를 새 노드로 설정
    }
    rear = newNode; // rear를 새 노드로 갱신

    if (front == null) { // 큐가 비어 있었다면
        front = rear; // front도 새 노드를 가리킴
    }
    size++; // 큐 크기 증가
}

 

 

---

큐에서 데이터를 제거하고 반환 (poll)

 

public T poll() {
    if (isEmpty()) { // 큐가 비어 있다면
        return null; // null 반환
    }

    T data = front.data; // front 노드의 데이터 저장
    front = front.next;  // front를 다음 노드로 이동
    if (front == null) { // front가 null이면 큐가 비어 있음
        rear = null; // rear도 null로 설정
    }
    size--; // 큐 크기 감소
    return data; // 제거된 데이터 반환
}

 

 

---

 

큐의 앞쪽 데이터 반환 (peek)

 

public T peek() {
    if (isEmpty()) { // 큐가 비어 있다면
        return null; // null 반환
    }
    return front.data; // front 노드의 데이터 반환
}

 

 

---

 

큐의 크기 반환 (size)

 

public int size() {
    return size; // 현재 큐 크기 반환
}