큐(Queue)

큐란?

데이터를 일시적으로 쌓아놓은 자료구조이다. 

데이터의 입출력순서는 선입선출(먼저 들어온 것이 먼저 나감)이다.

큐에 데이터를 넣는 작업을 인큐(enqueue), 꺼내는 작업을 디큐(dequeue)라고 한다.

 

즉 어떤 데이터를 인큐하면 큐의 맨 뒤에 데이터를 추가하고,

데이터를 디큐하면 큐의 맨 앞 데이터를 제거한다음 한칸씩 앞으로 당긴다.

근데 이렇게 디큐할때의 복잡도는 O(n)으로, 데이터를 하나 꺼낼때마다 이런 처리를 한다면 효율이 매우 떨어진다.

 

이런 문제점은 링버퍼를 사용하여 큐를 구현하면 개선할 수 있다.

프런트와 리어 값을 업데이트하며 인큐와 디큐를 수행하게 되기 때문이다.

[ O(1) ]

 

다음은 링버퍼로 큐를 구현하는 코드이다.

구간별 설명은 주석으로 대신한다!

 

import java.util.*;

public class Main {

    static class IntQueue{
        private int max; //큐의 용량
        private int front; //첫번째 요소 커서
        private int rear; //마지막 요소 커서(마지막 요소 하나 뒤의 인덱스)
        private int num; //현재 데이터수
        private int[] que; //큐 본체

        //실핼시 예외: 큐가 비어있음
        public class EmptyIntQueueException extends RuntimeException{
            public EmptyIntQueueException(){}
        }

        //실핼시 예외: 큐가 가득참
        public class OverflowIntQueueException extends RuntimeException{
            public OverflowIntQueueException(){}
        }

        //생성자
        public IntQueue(int capacity){
            num = front = rear = 0;
            max = capacity;
            try{
                que = new int[max];
            }catch(OutOfMemoryError e){
                max = 0;
            }
        }

        //큐에 데이터를 인큐
        public int enque(int x) throws OverflowIntQueueException{
            if(num>=max)
                throw new OverflowIntQueueException();
            que[rear++] = x;
            num++;
            if(rear==max)
                rear = 0;
            return x;
        }

        //큐에서 데이터를 디큐
        public int deque() throws EmptyIntQueueException {
            if(num<=0)
                throw new EmptyIntQueueException();
            int x = que[front++];
            num--;
            if(front==max)
                front=0;
            return x;
        }

        //큐에서 데이터를 피크(front 데이터 엿보기)
        public int peek() throws EmptyIntQueueException{
            if(num<=0)
                throw new EmptyIntQueueException();
            return que[front];
        }

        //큐에서 x를 검색하여 인덱스 반환. 없으면 -1 반환.
        //스캔의 시작은 배열의 첫 요소가 아니라 큐의 첫 요소!(front) 따라서 인덱스가 (i+front)%max 이다.
        public int indexOf(int x){
            for (int i = 0; i < num; i++) {
                int idx = (i+front) % max;
                if(que[idx]==x)
                    return idx;
            }
            return -1;
        }

        //큐를 비움
        public void clear(){
            num = front = rear = 0;
        }

        //큐의 용량을 반환
        public int capacity(){
            return max;
        }

        //큐에 쌓여있는 데이터 수를 반환
        public int size(){
            return num;
        }

        //큐가 비어 있는지
        public boolean isEmpty(){
            return num<=0;
        }

        //큐가 가득 찼는지
        public boolean isFull(){
            return num>=max;
        }

        //큐 안의 모든 데이터를 프런트>리어 순으로 출력. 큐가 비어있으면 비어있다고 출력.
        public void dump(){
            if(num<=0)
                System.out.println("큐가 비어 있습니다.");
            else{
                for (int i = 0; i < num; i++) {
                    System.out.println(que[(i+front) % max]+" ");
                }
                System.out.println();
            }
        }


    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntQueue q = new IntQueue(64);

        while (true){
            System.out.println("현재 데이터 수：" + q.size() + " / "
                    + q.capacity());
            System.out.print("(1)인큐　(2)디큐　(3)피크　" +
                    "(4)덤프　(0)종료：");

            int menu = scanner.nextInt();
            if (menu == 0) break;

            int x;
            switch (menu){
                case 1:
                    System.out.print("데이터: ");
                    x = scanner.nextInt();
                    try {
                        q.enque(x);
                    }catch (IntQueue.OverflowIntQueueException e){
                        System.out.println("큐가 가득 찼습니다.");
                    }
                    break;

                case 2:
                    try {
                        x = q.deque();
                        System.out.println("디큐한 데이터는 "+x+"입니다.");
                    }catch (IntQueue.EmptyIntQueueException e){
                        System.out.println("큐가 비어 있습니다.");
                    }
                    break;

                case 3:
                    try {
                        x = q.peek();
                        System.out.println("피크한 데이터는 "+x+"입니다.");
                    }catch (IntQueue.EmptyIntQueueException e){
                        System.out.println("큐가 비어 있습니다.");
                    }
                    break;

                case 4:
                    q.dump();
                    break;
            }
        }
    }
}

 

링버퍼의 활용

링버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다.

 

예를 들어 배열의 길이가 10인 배열에 \1~12까지 순서대로 12개의 데이터가 입력된다면, 앞의 두개를 뒤의 두개가 덮어써서 총 3~12까지의 데이터만 배열에 남기는 식이다.

 

다음은 위의 예를 링버퍼를 사용해서 구현한 예시이다.

 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int N = 10;
        int[] a = new int[N];
        int cnt = 0;
        int retry;

        System.out.println("정수를 입력하세요.");

        do {
            System.out.printf("%d번째 정수：", cnt + 1);
            a[cnt++ % N] = scanner.nextInt();

            System.out.print("계속 할까요? (예.1／아니오.0）：");
            retry = scanner.nextInt();
        } while (retry == 1);

        int i = cnt - N;
        if (i < 0) i = 0;

        for ( ; i < cnt; i++)
            System.out.printf("%2d번째의 정수 ＝ %d\n", i + 1, a[i % N]);
    }
}