6.Queue

Queue란?

일반적인 대기열을 생각하면 된다.

버스 정류장에서는 먼저 선 사람이 먼저 버스에 타고 나중에 선 사람이 나중에 탄다(FIFO)
이런 원리를 활용한 것이 Queue이다.

Queue는 선입선출의 원리를 활용한 자료구조이다.

자바에서 Queue

자바에서 queue는 스택과 다르게 인터페이스 자료형이다.

즉, 세부적으로 구현되어 있지 않고 내부 동작만 정의되어있다.

queue는 여러가지가 선택이 가능한데 LinkedList,PriorityQueue,ArrayDeque 등 으로 구현 가능하다.

인터페이스 사용의 장점으로는 다른 Queue를 사용하고 싶을때 최소한의 수정만으로 갈아낄수가 있다는 것이다.

LinkedList던 ArrayDeque던 Queue<> q=new ~~;으로 선언하여 q로 사용이 가능하다.

인터페이스에 정의된 매소드만 사용이 가능하다.

매소드

1. 삽입(enqueue)
- offer(value) : 전통적인 삽입 방식 큐의 시작점에 밀어넣음
- add(value) : offer와 같은 삽입 매소드, 단 오류 발생시 예외처리함

2. 삭제(dequeue)
- poll() : 가장 처음 추가된 값을 반환한다.
- remove() : poll()과 같으나 오류시 예외처리

3. 공백확인
- isEmpty()

4. 초기화
- clear() : 큐의 모든 원소 삭제 null로 만듬 

5. 크기
- size() : 큐 안에 저장된 원소 개수 반환

6. 확인
- peek() : 가장 먼저 들어간 값을 삭제없이 반환

실구현

public class customQueue {
    private QueueNode Head;
    private QueueNode Tail;
    private int size=0;

    public customQueue(){
        Head=new QueueNode();
        Tail=new QueueNode();

        Head.nextNode=Tail;
        Tail.prevNode=Head;
    }

    public void offer(Object value){
        QueueNode newQueue=new QueueNode(value);

        newQueue.nextNode=Head.nextNode;
        Head.nextNode.prevNode=newQueue;

        Head.nextNode=newQueue;
        newQueue.prevNode=Head;

        size++;
    }

    public Object poll(){
        QueueNode tmp=Tail.prevNode;

        tmp.prevNode.nextNode=Tail;
        Tail.prevNode=tmp.prevNode;

        tmp.prevNode=null;
        tmp.nextNode=null;

        size--;
        return tmp.obj;
    }

    public Object peek(){
        return Tail.prevNode.obj;
    }

    public boolean isEmpty(){
        return Head.nextNode==Tail?true:false;
    }

    public int size(){
        return size;
    }

    @Override 
    public String toString(){
        String str="[";

        for(QueueNode tmp=Head.nextNode;tmp!=Tail;tmp=tmp.nextNode)
            str+=tmp.obj.toString()+",";

        str+="]";

        return str;
    }
    class QueueNode{
        private Object obj;
        private QueueNode nextNode;
        private QueueNode prevNode;

        QueueNode(){};
        QueueNode(Object obj){
            this.obj=obj;
        }
    }
}