Queue 큐

큐 Queue

선입선출 = FIFO = LIFO = 들어온 순서대로 나감

Java

큐는 자바에선 인터페이스로 존재하기 때문에
Queue 자체를 사용하려면 Queue 인터페이스를 상속 받아 구현해야 한다.

구현하는 대신에 Queue를 상속받아 활용한 LinkedList를 사용할수도 있다.

• Queue Q = new LinkedList() = 큐 사용을 위한 LinkedList() 인스턴스화 진행
• Q.add( data ) = 큐에 data 입력
• Q.poll() = 큐에서 값을 꺼냄
  -> 맨 앞에 위치하는 값이 나온다.
  -> 값을 그냥 삭제하지 않고 들고 나오기 때문에 ,
  이 값을 사용하려면 적당한 변수에 담아주면 된다.
  -> int outNum = Q.poll()
• Q.peek() = Stack 클래스에도 있는 메소드로,
  지금 사용 할 수 있는 값(맨앞에 있는 값)을 복사해오는 메소드
• Q.contains( data ) = 큐에 data가 들어있는지 확인
• Q.clear() = 큐에 들어있는 값 모두 삭제

큐가 비어있을 때 poll() 연산을 실행한다면?

Stack과는 다르게, LinkedList로 구현된 객체를 사용해서 그런지
에러문구를 띄우지 않고, null 상태임을 알려주고 정상 종료 된다.

Ring Buffer 를 이용해서 큐 구조 이해하기

Ring Buffer

원형으로 연결 된 자료 구조 형태

데이터를 이동하지 않고,
front 와 rear 포인터를 이동하면서 데이터를 관리한다.

구현 해보기

class MyQueue<T> {
    T[] q;

    private int front;
    private int rear;

    private int dataCount;
    private int size;

    private MyQueue(){}
    public MyQueue(int size) {
        this.front = 0;
        this.rear = 0;
        this.dataCount = 0;
        this.size = size;

        q = (T[]) new Object[size];
    }

    public T add(T data) {
        if (dataCount < size) {
            dataCount++;

            q[rear] = data;

            rear = (rear + 1) % size;

            return data;
        } else {
            System.out.println(" [ add 실패 : " + data + " ] 큐가 가득 찼습니다. ");

            return null;
        }
    }

    public T poll() {
        if (dataCount > 0) {
            dataCount--;

            T data = q[front];
            q[front] = null;

            front = (front + 1) % size;

            return data;
        }

        System.out.println(" [ poll 실패 ] 큐가 비었습니다. ");
        return null;
    }

    public T peek() {
        return q[front];
    }

    public boolean contains(T data) {
        for (int i = 0; i < dataCount; i++) {
            int idx = (front + i) % size;
            if (data.equals(q[idx]))
                return true;
        }

        return false;
    }

    public void clear() {
        while (dataCount > 0) {
            poll();
        }

        front = 0;
        rear = 0;
    }

    public void print() {
        System.out.println(this);
    }

    @Override
    public String toString() {
        return  "  MyQueue : " + Arrays.toString(q) + "\n" +
                "    front : " + front + "\n" +
                "     rear : " + rear + "\n" +
                "dataCount : " + dataCount + "\n" ;
    }
}