Queue에 대해서

2019-09-12

Queue란?

Queue<E> queue = new LinkedList<E>();

선입선출(FIFO:First In First Out)의 자료구조이다. 가장 먼저 저장된(push) 데이터가 가장 먼저 인출(pop)된다.

Queue 큐에서 삭제가 발생하는 곳을 front라 하고, 큐에서 삽입이 발생하는 곳을 rear라고 한다.

Queue 인터페이스를 상속받은 하위 인터페이스는 다음과 같다.

  1. Deque
  2. BlockingDeque
  3. BlockingQueue
  4. TransferQueue

Deque(덱)

자료의 입력과 출력을 양 끝에서 가능하게 한 자료구조로 큐와 스택의 성격을 가지고 있다.

Queue Method

Queue 인터페이스는 큐 메모리 구조를 표현하기 위해, 다음과 같은 Collection 인터페이스 메소드만을 상속받아 사용한다.

QueueMethod

Queue의 종류

Linear Queue(선형 큐)

한 방향으로 데이터 항목들이 삽입/삭제되는 큐, 배열을 선형으로 사용해 큐를 구현한다.

public class Linear_Queue {

    int rear = -1;
    int front = 0;
    int maxsize = 0;
    int[] Linear_Queue;

    public Linear_Queue(int maxsize)
    {
        this.maxsize = maxsize;
        Linear_Queue = new int[maxsize];
    }

    public void EnQueue(int num)
    {
        if(rear != maxsize-1)
        {
            Linear_Queue[++rear] = num;
        }
        else
        {
            System.out.println("데이터 다참");
        }
    }

    public int DeQueue()
    {
        if(rear!=front || (rear==0 && front==0))
        {
            int tmp =Linear_Queue[front];
            for(int i=1;i<=rear;i++)
            {
                Linear_Queue[i-1] = Linear_Queue[i];
            }
            rear--;
            return tmp;
        }
        else
        {
            return -1;
        }
    }
}

하지만 선형 큐를 수행 했을 경우 요소들을 하나씩 다 옮겨줘야 하고, 가득 차지 않았는데 rear이 마지막 인덱스를 가리키고있으면 공간이 비어있더라도 연산을 하지 못한다. 즉, 메모리를 효율적으로 관리하지 못한다.

Circular Queue(원형 큐)

선형 큐의 문제점을 보완하기 위한 자료구조이다. 시작점과 끝점이 서로 연결되어 있는 큐

원형큐에서는 포인터 증가 방식이 (rear+1)%arraysize 형식으로 변환하기 때문에 배열의 첫 인덱스부터 다시 데이터의 삽입이 가능해진다.

public class Circular_Queue {

    int rear = 0;              //초기 공백 상태일 때 0에서부터 시작
    int front = 0;            //초기 공백 상태일 때 0에서부터 시작
    int maxsize = 0;          //배열의 크기
    int[] circular_Queue;     //배열

    public Circular_Queue(int maxsize)
    {
        this.maxsize = maxsize;
        circular_Queue = new int[this.maxsize];
    }

    public boolean Isempty()    //공백 상태인지 체크
    {
        if(rear == front)
        {
            return true;
        }
        return false;
    }
    public boolean Isfull()        //배열이 포화 상태인지 체크
    {
        if((rear+1)%maxsize == front)
        {
            return true;
        }
        return false;
    }

    public void EnQueue(int num)
    {
        if(Isfull())            //배열이 포화상태일경우
        {
            System.out.println("큐가 가득 찼습니다");
        }
        else                //배열이 포화상태가 아닐경우
        {
            rear = (rear+1) % maxsize;
            circular_Queue[rear]=num;
        }
    }

public int DeQueue()
    {
        if(Isempty())         //배열이 공백상태이면 -1반환
        {
            return -1;
        }
        else                 //배열이 공백상태가 아니라면
        {
            front = (front+1)%maxsize;
            return circular_Queue[front];
        }
    }
}

Priority Queue(우선순위 큐)

들어온 순서에 관계 없이 데이터를 꺼낼 때, 우선순위가 가장 높은 데이터가 먼저 나오는 큐

힙을 이용하여 구현하는것이 일반적이다. 데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소힙을 구성하고 데이터를 꺼낼 때 루트 노드를 얻어낸다. 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮긴다.

우선순위를 정하는 기준은 Java의 정렬기준과 동일하다. 기본적으로 오름차순으로 정렬하게 되는데, 우선순위를 변경하고 싶다면 Compartor 클래스나 Comparable 인터페이스를 이용한다. Collections.reversOrder()를 사용해 간편하게 내림차순으로 변경할 수도 있다.

Comparable과 Compartor 차이

  • Comparable: 기본 정렬기준을 구현할 때 사용. 기본적으로 작은 값에서 큰 값, 오름차순 형태로 구현된다. Comparable를 implements한 후, compareTo() 메소드를 오버라이드한다.
  • Compartor: 기본 정렬기준 외 다른 기준으로 정렬할 때 사용. Compartore를 implements한 후, compare 메소드를 오버라이드 한다.

참조

https://lktprogrammer.tistory.com/47 http://tcpschool.com/java/java_collectionFramework_stackQueue https://songeunjung92.tistory.com/23 https://freestrokes.tistory.com/83?category=1045118 https://eskeptor.tistory.com/98