큐(Queue)

큐(Queue)

Queue란?

한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조(FIFO).

Queue의 성질

• 원소의 추가가 O(1)
• 원소의 제거가 O(1)
• 제일 앞/뒤의 원소 확인이 O(1)
• 제일 앞/뒤가 아닌 나머지 원소들의 확인/ 변경이 원칙적으로 불가능

Queue 구현하기

array로 구현한 Queue

class Queue {
    private final int MAX = 100005;
    private final int[] data = new int[MAX];
    private int head = 0, tail = 0;

    boolean offer(int e) {
        data[tail] = e;
        tail++;
        return true;
    }


    int poll() {
        return data[head++];
    }


    int peek() {
        return data[head];
    }

    int size() {
        return tail - head;
    }

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

LinkedList로 구현한 Queue

class Queue<E> {
    private Node<E> head;
    private Node<E> tail;

    private int size = 0;

    private static class Node<E> {
        E data;
        Node<E> next;

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

    boolean offer(E e) {
        Node<E> newNode = new Node<>(e);
        if (head == null) {
            head = newNode;
        } else {
            tail.next = newNode;
        }
        tail = newNode;
        size++;
        return true;
    }


    E poll() {
        if (size == 0) return null;
        E e = head.data;
        Node<E> nextNode = head.next;

        head.data = null;
        head.next = null;

        head = nextNode;
        size--;
        return e;
    }


    E peek() {
        return head.data;
    }

    int size() {
        return size;
    }

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

java의 Queue에는 offer, poll, peek 외에도 add, remove, element 메소드가 존재한다.
java의 queue interface의 메소드를 비교하면 아래와 같다.

	예외발생	값 리턴
추가(enqueue)	add(e)	offer(e)
삭제(dequeue)	remove()	poll()
검사(peek)	element()	peek()

차이는 예외가 발생하는지 안하는지 여부이다.