Devjava

[Java] Queue

Queue의 종류

Queue는 공통적으로 Front, Rear 두 개의 pointer를 갖는다.

Queue는 Array나 Linked List를 사용하여 구현한다.

  • Simple or linear Queue
    • 일반적으로 Linked-list로 구현된다. FIFO(First In First Out)의 기본을 기킨다.
  • Circular Queue
    • 말 그대로 head와 rear가 이어져있는 구조.
  • Priority Queue
    • 각 개체(node, item, etc.)가 Priority를 가지고 있어서 First in은 성립하지만 Priority가 높은 녀석이 먼저 나오게 된다.
  • Dequeue
    • Double-Ended Queue를 의미하며 front (head) 쪽과 back (tail) 쪽 모두에서 추가/삭제될 수 있는 구조를 말한다.
      Head-tail linked list 라고도 불리운다.

java.util.Queue

Java에서는 기본적으로 Queue를 지원한다. (실제로 이걸 사용한 코드는 적어도 회사에서는 본 적 없다.)

이 Queue는 Java Collections Framework에 속한 interface로 세부 내용들은 구현 해주어야 한다.

Java Collections Framework에 속한 interface들은 다음과 같은 것들이 있다.

  • java.util.Collection에 속한 것들
    • java.util.Set
    • java.util.SortedSet
    • java.util.NavigableSet
    • java.util.Queue
    • java.util.concurrent.BlockingQueue
    • java.util.concurrent.TransferQueue
    • java.util.Degue
    • java.util.concurrent.BlockingDegue
  • java.util.Map에 속한 것들
    • java.util.SortedMap
    • java.util.NavigableMap
    • java.util.concurrent.ConcurrentMap
    • java.util.concurrent.ConcurrentNavigableMap

이걸 바로 사용하기 위해서는 아래와 같은 방식으로 사용 용도에 맞게 초기화 해주어야 한다.

1
2
3
4
5
Queue<Integer> aQueue = new LinkedList<Integer>();
Queue<Integer> bQueue = new PriorityQueue<Integer>();
Queue<Integer> cQueue = new LinkedBlockingQueue<Integer>();
Queue<Integer> dQueue = new ArrayBlockingQueue(20);
Queue<Integer> eQueue = new PriorityBlockingQueue<Integer>();

해보자

기본적인 add (혹은 push)와 poll (혹은 pop)을 Linked List로 구현해보자.

Node

사용할 Node를 만든다.

1
2
3
4
5
6
7
8
9
10
11
12
public class Node<T> {
    private T item;
    Node<T> next;
    
    Node(T item) {
        this.item = item;
    }
    
    public T getItem() {
        return item;
    }
}

Queue

Node를 이용한 Queue를 생성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class MyQueue<T> {
    Node<T> head;
    Node<T> rear;
    
    MyQueue() {
        head = null;
        rear = null;
    }
    
    public void add(T item) {
        if (head == null) {
            head = new Node<T>(item);
            rear = head;
        } else {
            Node<T> newNode = new Node<T>(item);
            rear.next = newNode;
            rear = newNode;
        }
    }
    
    public T poll() {
        Node<T> tmp = null;
        T ret = null;
        
        ret = (head != null) ? head.getItem() : null;
        if (head == rear) {
            head = null;
        } else {
            tmp = head;
            head = head.next;
            tmp = null;
        }
        
        return ret;
    }
}

Use

그리고 사용하자. 아래 예시에서는 3개를 넣고 4개를 빼기 때문에 NullPointerException이 발생한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {
    public static void main(String[] args) {
        MyQueue<Integer> mQueue = new MyQueue<Integer>();
        
        mQueue.add(1);
        mQueue.add(2);
        mQueue.add(3);
        
        try {
            System.out.println(mQueue.poll());
            System.out.println(mQueue.poll());
            System.out.println(mQueue.poll());
            System.out.println(mQueue.poll());
        } catch (NullPointerException e) {
            System.out.println("null");
        }
    }
}

출처

아래의 글들을 교재삼아 작성하였습니다.

Share