[자료구조] 큐(Queue)

큐(Queue)란 무엇인가?

큐는 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out)구조이다.

우선순위에 따라서 요소 순서가 정해지며, 요소는 중복 될 수 있다는 것이 특징이다.

Queue는 줄(line)이라는 의미를 가지고 있다.

가장 오래된 먼저 입력된 데이터를 front라고 하고 가장 최근에 입력된 마지막에 있는 데이터를 rear라고 한다. 데이터 삽입은 rear에서 이루어지고 삭제는 front에서 이루어진다. 

front와 rear를 관리하는 배열을 이용해서 front 노드와 rear 노드를 관리하는 연결 리스트를 이용할 수 있다.

큐는 insert(삽입), remove(삭제), 읽기(peek)으로 사용할 수 있다.

배열을 통한 Queue

public class ArrayQueue {
    
    // 큐 배열은 front와 rear 그리고 maxSize를 가진다.
    private int front;
    private int rear;
    private int maxSize;
    private Object[] queueArray;
    
    // 큐 배열 생성
    public ArrayQueue(int maxSize){
        
        this.front = 0;
        this.rear = -1;
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
    }
    
    // 큐가 비어있는지 확인
    public boolean empty(){
        return (front == rear+1);
    }
    
    // 큐가 꽉 찼는지 확인
    public boolean full(){
        return (rear == maxSize-1);
    }
    
    // 큐 rear에 데이터 등록
    public void insert(Object item){
        
        if(full()) throw new ArrayIndexOutOfBoundsException();
        
        queueArray[++rear] = item;
    }
    
    // 큐에서 front 데이터 조회
    public Object peek(){
        
        if(empty()) throw new ArrayIndexOutOfBoundsException();
        
        return queueArray[front];
    }
    
    // 큐에서 front 데이터 제거
    public Object remove(){
        
        Object item = peek();
        front++;
        return item;
    }
 
}
 
 
출처: http://hyeonstorage.tistory.com/263?category=578561 [개발이 하고 싶어요]

front, rear, maxSize, queueArray(실제 데이터 저장)를 선언하고 생성자를 통해 이를 초기화한다.

empty() 메소드는 front가 rear를 넘었을 경우 더 이상 꺼낼 데이터가 없다고 true 반환,

full()은 데이터를 저장할 rear가 배열의 최대크기인 maxSize에 도착했을 때 true 반환한다.

remove() 메소드는 peek() 메소드를 통해 데이터를 하나 반환, front를 하나 증가시키면서 데이터를 삭제한다.

배열을 이용해서 큐를 구현하면 데이터가 다 차있지 않아도 rear와 front가 계속 증가되면 배열의 maxSize에 도착하여 더이상 사용할 수 없는 경우가 오는 문제점을 가지고 있다.

이러한 점 때문에 moving queue를 사용하기도 한다. 

이 것은 앞부분에 사용할 수 있는 공간만큼 전체 데이터들을 앞쪽으로 이동시키고 rear와 front를 수정하여 남은 공간을 사용하는 방법이다. 하지만 이 또한 자료를 이동하면서 발생하는 시간 소모가 있다.

이 또한 보완하기 위한 방법으로는 원형 큐(Circular Queue)를 사용할 수 있다고 한다.

LIST를 통한 Queue

public class ListQueue {
    
    private class Node{
        
        // 노드는 data와 다음 노드를 가진다.
        private Object  data;
        private Node nextNode;
    
        Node(Object data){
            this.data = data;
            this.nextNode = null;
        }
    }
    
    // 큐는 front노드와 rear노드를 가진다.
    private Node front;
    private Node rear;
    
    public ListQueue(){
        this.front = null;
        this.rear = null;
    }
    
    // 큐가 비어있는지 확인
    public boolean empty(){
        return (front==null);
    }
    
    // item을 큐의 rear에 넣는다.
    public void insert(Object item){
        
        Node node = new Node(item);
        node.nextNode = null;
        
        if(empty()){
            
            rear = node;
            front = node;
        
        }else{
            
            rear.nextNode = node;
            rear = node;
            
        }
    }
    
    // front 의 데이터를 반환한다.
    public Object peek(){
        if(empty()) throw new ArrayIndexOutOfBoundsException();
        return front.data;
    }
    
    // front 를 큐에서 제거한다.
    public Object remove(){
        
        Object item = peek();
        front = front.nextNode;
        
        if(front == null){
            rear = null;
        }
        
        return item;
    }
}
 
출처: http://hyeonstorage.tistory.com/263?category=578561 [개발이 하고 싶어요]
 

front가 null 값을 가질 경우 더이상 데이터를 꺼낼 수 없다는 것을 의미한다.

데이터를 삽입할 경우 노드를 먼저 생성하고 노드의 nextNode 값을 null로 지정하여 마지막 노드임을 표시한다.

비어있는 큐였을 경우 front와 rear 값 모두 새로 생성한 노드를 지정한다.

remove() 메소드는 front 노드를 삭제하고 반환, peek()을 호출하여 front 노드의 data를 반환한다. 삭제될 노드의 nextNode는 새로운 front가 된다.

만약 삭제한 노드가 마지막일 경우 큐에 데이터가 더이상 없으므로 rear값도 초기화 한다.

큐 구현 클래스

priorityQueue

1. PIPO(Priority-In, Priority-Out)

2. 정렬된 순서에 의해 반복

3. null 요소를 허용하지 않음

priorityBlockingQueue

1. Priority Queue의 동기화 버전

2. 동기화 메소드 보유

3. PriorityQueue보다 느린 속도

4. null 요소를 허용하지 않음

LinkedList

1. 끝에 요소추가 용이

2. List 인터페이스 구현

3. 요소에 null 허용

PriorityQueue 클래스 / LinkedList 클래스

앞서 살펴 본 클래스들의 사용법을 보자.

priorityQueue 클래스

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Test{
    public static void main(String[] args){
        Queue<String>queue = new PriorityQueue<String>(10, new myqueue());
        
        queue.add("JAVA");
        queue.add("SCRIPT");
        queue.add("JSP");
        
        while(!queue.isEmpty()){
            System.out.println(queue.remove());
        }
    }
}
 
class myqueue implements Comparator<String>{
    public int compare(String s1, String s2){
        return s2.compareTo(s1);
    }
}

LinkedList 클래스

import java.util.LinkedList;
import java.util.Queue;
 
public class Test{
    public static void main(String[] args){
        Queue<String> queue = new LinkedList<String>();
        
        queue.add("JAVA");
        queue.add("Script");
        queue.add("jsp");
 
        while(!queue.isEmpty()){
            system.out.println(queue.remove());
        }
    }
}

LinkedList 클래스로 좀더 간략하게 작성할 수 있는 것 같다. 위에 언급한대로 배열로 생성 했을 시에는 여러가지 문제점을 안고 있으니 되도록 LinkedList 클래스로 사용하는 것이 좋겠다.

출처:

http://hyeonstorage.tistory.com/263?category=578561

http://dreamzelkova.tistory.com/entry/JAVA-%EC%BB%AC%EB%A0%89%EC%85%98%ED%81%90Queue