큐에 대해서

안녕하세요, 오늘은 큐라는 자료구조에 대해서 이야기를 해보려고 합니다.
큐는 저번 시간에 공부한 스택과 몇 가지의 차이를 제외하고는 거의 비슷한 구조로 이루어져 어렵지 않을 것입니다.

🤷‍♀️ 큐는 무엇인가요?

큐는 저번에 공부한 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓은 자료구조입니다. 하지만 스택의 입출력 방식이 후입 선출이었다면 큐는 선입선출의 입출력 방식을 가지고 있습니다. 저희가 생활 속에서 마주하는 상황과 아주 비슷한 순서라고 말할 수 있습니다.

 

구성 모습	프런트 (Front) / 리어 (Rear)
개념 및 의미	데이터를 일시적으로 저장하기 위한 자료구조
구현 가능 방식	배열 (Array) / 링 버퍼 (Ring Buffer)
데이터 입력 방식	인큐 (Enqueue)
데이터 출력 방식	디큐 (Dequeue)
데이터 입력과 출력 방식	선입선출 (FIFO, First In First Out)

📢 큐의 구조를 알아보자!

큐는 스택과 달리 데이터의 입력과 출력 방식이 선입선출 방식입니다. 즉 가장 먼저 넣은 데이터를 가장 먼저 꺼낸다는 의미입니다. 이 방식은 실제 생활 속에서도 쉽게 마주할 수 있는 방식입니다. 아래의 그림은 어떤 가게가 아침 일찍 오픈을 하였다면 손님들이 줄을 서서 먼저 줄을 빨리 선 손님이 가게에 더 빨리 들어가는 모습을 큐의 선입선출 방식에 비유를 하였습니다. 아래의 그림 보시죠!

 

가게에 손님들이 줄을 서서 먼저 온 손님부터 먼저 들어가는 모습을 선입선출 방식과 연결시켰습니다.

위의 그림이 이해가 되셨나요? 위의 그림은 큐의 데이터 입력과 출력 방식을 선입선출 방식으로 비유한 것입니다. 그럼 큐에서 이용되는 선입선출의 방식을 조금 더 자세히 살펴보겠습니다. 아래의 그림은 실제 배열 큐에서 이루어지는 선입 선출의 과정입니다.

# 배열 큐 알아보기

 

실제 배열 큐에서 이루어지는 데이터 입 출력 과정을 표현하였습니다.

큐에서 데이터를 입력할 때는 리어에서 인큐 방식을 사용하여 데이터를 추가하고 데이터를 출력할 때는 프런트 부분에서 디큐 방식을 통해 데이터를 출력합니다. 큐 또한 스택과 같이 프로그램을 추후 구현을 하려면 위의 내용을 자세히 기억해야 하며 정말 중요합니다.

 

바로 위의 그림은 배열 큐의 방식입니다. 뭔가 특이한 점이 보이지 않나요? 배열 속에서 데이터를 추가할 때는 아무 문제없이 아래에서 데이터를 추가하지만 데이터를 출력할 때는 위에서 데이터를 빼내면서 출력합니다. 그때 기존의 데이터들은 디큐된 데이터의 자리의 빈 공간을 모두 매우면서 한 칸씩 앞으로 옮기고 있습니다. 따라서 배열 큐를 구현한다면 신경 써야 하는 부분 중 한 개입니다.

# 링 버퍼 큐 알아보기

 

실제 링 버퍼 큐에서 이루어지는 데이터 입 출력 과정을 표현하였습니다.

위의 그림의 왼쪽은 실제 링 버퍼 큐에서 이루어지는 데이터 입 출력 과정을 표시한 것입니다. 프런트의 값부터 순차적으로 데이터가 추가되는 모습을 볼 수 있습니다. 그림의 오른쪽은 링 버퍼 큐의 모양을 배열 큐 모습으로 변환시켜 놓은 것입니다. 이해를 위해서.

 

링 버퍼 큐는 배열 큐와 달리 데이터가 디큐가 된 후 인덱스 자리를 옮겨줘야 하는 등 불편한 점이 존재하지 않습니다. 지금까지 배열 큐와 링 버퍼 큐에 대해서 알아보았는데요, 이 둘은 각기 다른 것이 아닌 큐를 구현하는 모양의 차이입니다. 대부분의 사람들이 큐를 구현할 때는 배열 모양보다는 링 버퍼 모양으로 큐를 구현하는 것이 대부분입니다. 그럼 큐를 구현하는 코드를 이제 보겠습니다.

🛒 큐의 필수 요소는 무엇인가요?

이제는 큐를 구현하기 위해 필요한 구성 요소들에 대해서 알아보겠습니다. 이 요소들은 링 버퍼 큐를 구현할 때 필요한 요소들로 정리를 하였습니다. 그러나 배열 큐와 링 버퍼 큐의 구성요소는 배열 큐의 자리 인덱스를 옮기는 기능을 제외하고 모두 똑같은 방식으로 이루어지기 때문에 링 버퍼 큐를 구현할 수 있다면, 배열 큐 또한 쉽게 구현이 가능하다고 생각을 하여 링 버퍼 큐를 설명하겠습니다.

---

📕 큐 멤버 변수

큐 또한 프로그램에서 공통으로 사용할 수 있는 멤버 변수가 필요합니다. 아래와 같이 max 변수는 큐 본체의 용량을 저장하고 front 변수는 큐의 첫 번째 요소를 가리키고 rear 변수는 큐 데이터의 마지막 요소를 가리킵니다. 또한 num 변수는 현재 데이터 수의 개수를 저장하며 front와 rear의 값이 같은 경우 큐가 비어있는지, 가득 차 있는지 구별할 수 없는 상황을 피하기 위한 역할을 합니다.

 

큐가 비어있을 때는 num은 0이고 큐가 가득 차 있을 때는 num과 max의 값은 같기 때문에 front와 rear의 값이 같은 상황에서 현재 front와 rear이 큐의 데이터가 꽉 차서 같은 것인지 또는 큐의 데이터가 비어서 값이 같은 것인지 판단을 할 수 있습니다. 즉 이러한 이유로 num 변수가 존재를 해야 합니다. 마지막으로 que 배열 변수는 큐의 본체로서 데이터들을 저장하는 역할을 하고 있습니다.

class IntQueue{
    int max;
    int front;
    int rear;
    int num;
    int[] que;
}

📘 큐 매서드

큐의 멤버 변수에 대해서 알아보았다면 구현한 멤버 변수들을 활용할 메서드들을 알아보겠습니다. 큐 또한 데이터를 입, 출력하는 매서드가 매서드 중에서 가장 중요하다고 말할 수 있습니다. 먼저 데이터를 리어 쪽으로 입력하는 매서드 인큐에 대해 예기하겠습니다.

 

인큐는 아래의 코드와 같이 매개변수로 데이터를 입력받은 후 큐의 맨 뒤쪽 rear 부분에서부터 데이터를 추가하고 데이터의 수를 저장하는 num변수와 rear 변수의 값을 1 증가시켜 데이터가 추가되었다는 것을 알립니다. 그럼 아래의 그 아래의 코드는 무엇일까요?

 

만약 rear 변수의 값과 max의 값이 같다면 rear의 값을 0으로 설정해줍니다. 이 뜻은 rear변수가 max와 같다는 것은 현재 데이터가 맨 끝 인덱스에 추가 되었다는 것이며 rear의 값을 0으로 설정을 안 해준다면 다음 데이터는 존재하지 않는 배열 인덱스에 추가가 되어 오류가 발생할 것입니다. 그렇기 때문에 rear의 값을 0으로 설정하여 다시 처음부터 데이터를 추가하게 합니다. 이해되셨나요?

public int enqueue(int x) throws OverflowIntQueueException{
     if(num == max) throw new OverflowIntQueueException();

     que[rear++] = x;
     num++;

     if(rear == max) rear = 0;
     return x;
}

반면에 디큐는 x라는 지역 변수를 만든 후 그 변수에 출력할 데이터의 값을 저장해둡니다. 그 후 front의 값을 1 증가시키고 num의 값을 1 감소시키는 과정을 통해 데이터가 출력되었다는 것을 알립니다. 그럼 아래의 코드는 또한 의미가 무엇일까요?

 

만약 front의 값이 max의 값과 같아진다는 것은 큐 배열의 인덱스를 넘어간다는 의미이기 때문에 오류가 발생합니다. 즉 그래서 front의 값을 다시 0으로 설정하여 인덱스의 첫 번째 값을 front로 다시 설정을 해주어야 합니다. 이 과정을 잘 기억해야 합니다.

public int dequeue() throws EmptyIntQueueException{
     if(num <= 0) throw new EmptyIntQueueException();

     int x = que[front++];
     num--;

     if(front == max) front = 0;
     return x;
}

큐 또한 저번 스택과 같이 인큐, 디큐 매서드뿐만이 아니라 큐에 관련된 다양한 매서드들이 존재합니다. 그 매머드의 기능은 저번 스택과 같으며 이번에 역시 코드에 주석 처리를 하여 아래에 첨부를 해드리도록 하겠습니다. 참고해주시면 좋을 것 같습니다.

public class IntQueue {
    public int max; // 큐의 용량
    public int front; // 큐의 첫 번째 요소
    public int rear; // 큐의 마지막 요소
    public int num; // 현재 데이터의 수;
    public 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 ex){
            max = 0;
        }
    }

    // 큐에 데이터 인큐
    public int enqueue(int x) throws OverflowIntQueueException{
        if(num == max) throw new OverflowIntQueueException();

        que[rear++] = x;
        num++;

        if(rear == max) rear = 0;
        return x;
    }

    // 큐에 데이터 디큐
    public int dequeue() throws EmptyIntQueueException{
        if(num <= 0) throw new EmptyIntQueueException();

        int x = que[front++];
        num--;

        if(front == max) front = 0;
        return x;
    }

    // 큐의 최상위 데이터 전달
    public int peek() throws EmptyIntQueueException{
        if(num <= 0) throw new EmptyIntQueueException();
        return que[front];
    }

    // 큐의 데이터 인덱스 값 반환
    public int indexOf(int x){
        for(int i = 0; i < num; i++){
            int idx = (i + front) % max;
        }
        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++){
                int idx = (i + front) % max;
                System.out.println(que[idx] + " ");
            }
            System.out.println();
        }
    }
}

---

🎬 큐를 이제 구현해보자!

이제 앞에서 배운 큐를 활용하여서 간단한 프로그램을 구현해보도록 하겠습니다. 프로그램의 구조는 저번 스택의 프로그램과 같습니다. 저번과 같이 앞의 IntQueue 클래스를 사용할 것이며 IntQueueTester 클래스를 따로 생성하여 테스트를 진행할 것입니다.

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

        int input = 1;

        while(input != 0){
            System.out.println("현재 데이터 수 : " + intQueue.size() + "/" + intQueue.capacity());
            System.out.print("(0) 종료 (1) 인큐 (2) 디큐 (3) 피크 (4) 덤프 : "); input = scanner.nextInt();

            switch (input){
                case 0: break;
                case 1:{
                    System.out.print("데이터 : "); int data_input = scanner.nextInt();
                    try{ intQueue.enqueue(data_input); }
                    catch (IntStack.OverflowIntStackException ex){
                        System.out.println("큐가 가득 찼습니다.");
                    } break;
                }
                case 2: {
                    try{System.out.println("디큐 데이터는 " + intQueue.dequeue() + "입니다.");}
                    catch (IntStack.EmptyIntStackException ex){
                        System.out.println("큐가 비어 있습니다.");
                    } break;
                }
                case 3: {
                    try{System.out.println("피크한 데이터는 " + intQueue.peek() + "입니다.");}
                    catch (IntStack.EmptyIntStackException ex){
                        System.out.println("큐가 비어 있습니다.");
                    } break;
                }
                case 4: intQueue.dump(); break;
            }
            System.out.println();
        }
    }
}

큐를 활용하여 구현한 간단한 프로그램입니다.

👍 글을 마치며

오늘은 저번 시간에 스택에 이어 큐에 대해서 알아보았습니다. 큐는 스택과 정말 비슷한 부분이 많아 크게 배우는데 어렵지 않았습니다. 하지만 배열 큐와 링 버퍼 큐 두 가지의 모양이 존재하여 약간씩 헷갈릴 수는 있었습니다. 다음 시간에 배울 내용은 재귀 함수이며 저도 블로그에 글을 조금 더 쉽게 정리하여 글을 잘 쓸 수 있도록 열심히 공부하고 준비를 하도록 하겠습니다. 감사합니다.

 

참고 : Do it 자료구조와 함께 배우는 알고리즘 입문 자바 편