JAVA의 Queue

자료구조 - 큐

큐는 먼저 들어온 데이터가 먼저 나가는 선입선출(LIFO) 구조입니다.

큐에는 삽입(ENQUEUE) 연산과 삭제(DEQUEUE) 연산이 존재하는데

삽입의 경우 가장 마지막 위치(Rear)에 쌓이게 되며

삭제의 경우 가장 먼저 들어온 데이터, 즉 Front 에 위치한 데이터가 삭제 됩니다.

예를 들면, 줄을 서서 물건을 받는 경우를 생각하시면 됩니다!

---

JAVA로 Queue 구현

큐를 구현하는 방법은 2가지가 있습니다.

배열을 이용한 큐와 연결리스트를 이용한 큐입니다.

먼저 배열을 이용한 큐의 구현입니다.

public class CQueueArray {
    private int front;
    private int rear;
    private int maxSize;
    private Object[] queueArray;
 
    // 큐 배열 생성 및 초기화
    public CQueueArray(int maxSize){
        this.front = 0;
        this.rear = -1;
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
    }

큐의 처음을 가리키는 front 변수, 

큐의 끝을 가리키는 rear 변수

배열의 최대 크기를 받는 maxSize 변수가 있습니다.

    // 큐가 비어있는지 확인
    public boolean empty(){
        return (front == rear+1);
    }
 
    // 큐가 차있는지 확인
    public boolean full(){
        return (rear == maxSize-1);
    }
 
    // 큐 삽입연산
    public void enqueue(Object item){
 
        if(full()) throw new ArrayIndexOutOfBoundsException();
 
        queueArray[++rear] = item;
    }
 
    // 큐의 마지막 데이터 조회
    public Object peek(){
 
        if(empty()) throw new ArrayIndexOutOfBoundsException();
 
        return queueArray[front];
    }
 
    // 큐 삭제연산
    public Object dequeue(){
        Object item = peek();
        front++;
        return item;
    }

empty, full 함수는 스택이 비었는지 차있는지를 체크해주고

enqueue, dequeue 함수를 통해 삽입, 삭제 연산이 이루어집니다.

하지만 배열을 이용한 큐는 크기가 제한적이라는 단점이 있습니다.

이 때문에 rear 와 front가 계속 증가하다 보면 배열의 사이즈에 도달하여 문제가 발생합니다.

따라서 큐를 구현하는 경우 연결리스트가 효과적인 방법입니다.

다음은 연결리스트를 이용한 큐입니다.

public class CQueueList {
    
    private class Node{
        private Object  data;
        private Node nextNode;
 
        Node(Object data){
            this.data = data;
            this.nextNode = null;
        }
    }
    private Node front;
    private Node rear;
 
    public CQueueList(){
        this.front = null;
        this.rear = null;
    }

노드는 데이터 필드와 다음 노드를 가리키는 포인터 필드로 구성됩니다.

그리고 큐는 처음과 끝을 가리키는 front, rear 객체를 가지고 있습니다.

    // 큐가 비어있는지 확인
    public boolean empty(){
        return (front==null);
    }
 
    // 큐 삽입연산
    public void enqueue(Object item){
        Node node = new Node(item);
        node.nextNode = null;
 
        if(empty()){
            rear = node;
            front = node;
        }else{
            rear.nextNode = node;
            rear = node;
        }
    }
 
    // 큐의 마지막 데이터 조회
    public Object peek(){
        if(empty()) throw new ArrayIndexOutOfBoundsException();
        return front.data;
    }
 
    // 큐 삭제연산
    public Object dequeue(){
        Object item = peek();
        front = front.nextNode;
 
        if(front == null){
            rear = null;
        }
        return item;
    }

배열과 마찬가지로 삽입, 삭제가 이루어집니다.

---

JAVA의 Queue

Java에서는 Queue를 편리하게 사용할 수 있도록 API를 제공합니다.

Java의 Queue는 인터페이스 형태이므로 

LinkedList 또는 ArrayList를 통해 사용할 수 있습니다.

주요 메소드는 다음과 같습니다.

Method	Description
Object element()	저장된 요소를 읽어옴
Object peek()	큐의 맨 끝에 저장된 객체를 반환
Object remove()	큐에서 객체를 삭제
boolean offer(Object o)	큐에 객체를 저장

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(10);
        queue.offer(20);
        queue.offer(30);
        
        while(!queue.isEmpty()) {
            queue.remove();
        }
    }

Integer 타입의 Queue 객체를 생성한 다음,

offer 함수를 통해 10, 20, 30 순서로 넣어줍니다.

그리고 큐가 비어있지 않으면 remove 함수를 통해 삭제해주는 코드입니다.