[Data Structure] Queue 큐, array로 구현하기 (java)

Queue

FIFO(First In First Out : 선입선출) 형태를 갖는 자료구조.

일상생활에서 Queue와 가장 밀접한 예로 줄을 서는 행위를 들 수 있다. 

보통 줄을 설 때 줄을 가장 먼저 선 사람이 가장 먼저 처리되므로 Queue와 같다.(Queue 라는 단어 자체가 줄을 서다 라는 뜻을 갖는 동사, 대기줄이라는 뜻을 갖는 명사 이다)

 

[java.util.Queue 의 기본적인 사용예]

package algo_datastructure.queue.queuebyarray;
 
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) {
        
        System.out.println("Queue---------");
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(1);
        q.add(2);
        System.out.println(q.peek());
        while(!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
        
        System.out.println("\nPriorityQueue (default : ascending)---------");
        Queue<Integer> q2 = new PriorityQueue<Integer>();
        q2.add(1);
        q2.add(3);
        q2.add(2);
        System.out.println(q2.peek());
        while(!q2.isEmpty()) {
            System.out.print(q2.poll() + " ");
        }
        
        System.out.println("\nPriorityQueue (Descending)---------");
        Queue<Integer> q3 = new PriorityQueue<Integer>((o1, o2)->o2-o1);
        q3.add(1);
        q3.add(3);
        q3.add(2);
        System.out.println(q3.peek());
        while(!q3.isEmpty()) {
            System.out.print(q3.poll() + " ");
        }
    }
}
 

[실행결과]

Queue---------
1
1 2
PriorityQueue (default : ascending)---------
1
1 2 3
PriorityQueue (Descending)---------
3
3 2 1

Queue 는 입력된 순서대로 저장 및 출력되는(LinkedList 를 구현체로 사용) Queue 와

입력된 데이터들을 특정 기준에 의해 정렬된 상태로 저장 및 출력하는 PriorityQueue 가 있다.

위와 같이 PriorityQueue는 Comparator 인터페이스를 파라미터로 넘겨 정렬순서를 원하는대로 선택할 수 있다. (위 예제에선 람다로 처리)

Comparator 인터페이스를 넘겨주지 않을 경우, 오름차순 정렬(default)로 처리된다.

 

두가지 queue 모두 공통적으로 아래와 같은 메소드를 갖는다.

add() : queue 에 값을 넣는다. (값 넣기 실패시 exception 을 뱉는다)

offer() : add()와 같이 queue에 값을 넣는다. (값 넣기 실패시 false 를 리턴한다)

peek() : queue 내에서 가장 앞에 위치한 데이터를 꺼낸다.(데이터는 그대로 둔다)

poll() : queue 내에서 가장 앞에 위치한 데이터를 꺼낸다.(데이터를 꺼내고 지운다)

 

[Array로 구현한 Queue]

package algo_datastructure.queue.queuebyarray;
 
public class Queue {
    
    private int[] array = new int[100];
int lastIdx = 0;
    
    public void add(int input) {
        array[lastIdx] = input;
        lastIdx++;
    }
    
    public int peek() {
        return array[0];
    }
    
    public int poll() {
        int rs = array[0];
        
        for(int i=1; i<=lastIdx; i++) {
            array[i-1] = array[i];
        }
        lastIdx--;
        
        return rs;
    }
    
    public boolean isEmpty() {
        return lastIdx==0?true:false;
    }
}
 

[사용]

package algo_datastructure.queue.queuebyarray;
 
public class Main {
    public static void main(String[] args) {
        
        Queue q = new Queue();
        q.add(1);
        q.add(2);
        q.add(3);
        System.out.println(q.peek());
        while(!q.isEmpty()) {
            System.out.print(q.poll() + " ");
        }
    }
}