Queue란?

개념 정리

Queue는, 일반적으로 우리가 줄을 서는 모습을 상상하면 이해하기 쉽다. 한 쪽에서 줄을 서고 (= Enqueue), 다른 쪽에서 줄이 마무리 (= Dequeue)가 된다. 이러한 구조를 FIFO (First In First Out) 구조라고도 한다.

여기서 Dequeue가 발생되는 구간을 Front, Enqueue가 발생되는 구간을 Rear라고 자주 부른다. 이를 바탕으로 어떤 주요 기능들이 있는지 살펴보자.

주요 기능

먼저 Queue에서 주목할 점 중 하나는 바로 Queue가 Inferface의 형태로 구현되었다는 점이다. 따라서, Queue를 바로 불러오지 않고,LinkedList()를 활용하여 값을 불러올 수 있다. (즉, 다형성을 활용하겠다는 뜻이다.)

public class myQueueStudy {
    public static void main(String args[]){
        Queue queue = new LinkedList(); // Queue가 Interface임..
        queue.add(1);
        queue.add(2);
        queue.add(3);
        queue.add(4);
        System.out.println("queue = " + queue);
        System.out.println("== Poll ==");
        System.out.println(queue.poll());
        System.out.println("queue = " + queue);
        System.out.println("== Peek ==");
        System.out.println(queue.peek());
        System.out.println("queue = " + queue);
        System.out.println("== Else ==");
        System.out.println(queue.contains(3));
        System.out.println(queue.size());
        System.out.println(queue.isEmpty());
        queue.clear();
        System.out.println("queue = " + queue);
    }
}

또 주의할 점이 하나 있는데, 여기서 enqueue가 add(), dequeue가 poll()로 구현되었음에 주의하자. 특히, front 단의 값을 확인만 하는 것(즉, 삭제 X)은 peek()임에 주의하자.

어디서 사용하는가?

예제1. Find Last Card

여기서는 마지막 카드를 찾는 규칙을 확인하고 remove -> add를 쓰는 기법에 대해 알아보자.

    public static int findLastCard(int N){
        Queue queue = new LinkedList();
        IntStream.range(1, N + 1).forEach(x -> queue.add(x));

        while (queue.size() > 1){
            queue.remove(); // 하나 지우고
            int data = (int) queue.remove(); // 하나 더 꺼내서
            queue.add(data); // 맨 아래로
        }
        return (int) queue.remove();
    }

front에 위치한 값을 꺼내서 지운 후, 하나 더 꺼낸 값을 add하는 장면이 중요하다. 결과적으로 하나의 값만이 삭제되는 것을 확인해보자.

            queue.remove(); // 하나 지우고
            int data = (int) queue.remove(); // 하나 더 꺼내서
            queue.add(data); // 맨 아래로

예제2. Josephus

 public static ArrayList getJosephus(int N, int k){
        Queue queue = new LinkedList();
        ArrayList result = new ArrayList();

        IntStream.range(1, N+1).forEach(x -> queue.add(x));

        int cnt = 0;
        while (!queue.isEmpty()){
            int data = (int) queue.remove();
            cnt += 1;
            if (cnt % k == 0){
                result.add(data);
            } else {
                queue.add(data);
            }
        }
        return result;
    }

여기서 주목할 점은 2가지.
1) IntStream의 활용 -> 모든 값에 같은 내용을 적용할 때 사용해보자.

IntStream.range(1, N+1).forEach(x -> queue.add(x));

2) k개마다 삭제 -> 즉, cnt % k == 0을 기준으로 특수 동작을 수행한다는 점
- queue를 remove한 후 -> result에 저장: 즉, queue에서 값 하나 빠짐.
- queue를 remove한 후 -> queue에 저장: 즉, 한 칸씩 값이 밀림.

        int cnt = 0;
        while (!queue.isEmpty()){
            int data = (int) queue.remove();
            cnt += 1;
            if (cnt % k == 0){
                result.add(data);
            } else {
                queue.add(data);
            }
        }

Deque란?

개념 정리

말 그대로, 여러 곳에 값을 넣을 수 있다는 뜻이다. 상황에 따라서 입/출력 위치 값을 제한할 수도 있으나 여
기서는 Front, Rear 둘 다에서 값을 넣을 수 있다고 가정하자.

주요 기능

Deque 역시 Inferface의 형태로 구현되었다는 점이다. 따라서, deque를 바로 불러오지 않고,LinkedList()를 활용하여 값을 불러올 수 있다. (즉, 다형성을 활용하겠다는 뜻이다.)

front에서 값을 꺼내오는 removeFirst, rear에서 값을 꺼내오면 removeLast를 사용할 수 있다.
반대로 값을 넣는 값은 addFirst, addLast를 사용한다.

poll()의 경우 remove()와 유사하나, 값이 비어있으면 "null"을 출력한다는 점에서 차이가 있다.

public class myDequeStudy {
    public static void main(String[] args){
        Deque deque = new ArrayDeque();
        
        deque.addFirst(1);
        deque.addFirst(2);
        deque.addFirst(3);
        System.out.println("deque = " + deque);
        
        deque.addLast(10);
        deque.addLast(20);
        deque.addLast(30);
        System.out.println("deque = " + deque);

        // Front
        System.out.println(deque.removeFirst());
        System.out.println(deque);

        // Rear
        System.out.println(deque.removeLast());
        System.out.println(deque);

        // Poll
        System.out.println(deque.pollFirst());
        System.out.println(deque);


        System.out.println(deque.pollFirst());
        System.out.println(deque.pollFirst());
        System.out.println(deque.pollFirst());
        System.out.println(deque.pollFirst());
        System.out.println(deque);

    }
}