[자료구조] 큐(Queue)

이번시간에는 Queue에 대해서 공부해보겠습니다.

Queue의 개념은 일상생활에서도 많이 사용됩니다. 예를들어, 은행에서 창구수에 비해 오는 고객들이 많으니, 이들 고객에는 순서가 필요합니다. 그래서 나온 것이, 대기순번이죠. 내가 일찍왔으면 내가 먼저 상담을 받고, 늦게 오면 늦게 온 대로 상담을 받습니다. 만약 내가 늦게 왔는데 일찍하려고 하면 싸움이 나기 시작하죠.

 

바로 이 개념이 Queue입니다. 앞서 배운 스택은 "LIFO", 먼저 들어간 놈이 늦게 나오는 구조입니다. 저희가 은행에 먼저 갔는데, 저희 순서가 가장 마지막번쨰라뇨? 저희의 직관과는 잘 맞지 않습니다. 반면에 Queue는 먼저 온 놈이 먼저 나갑니다. FIFO(First In First Out)이죠. 

 

게임을 좋아하시는 분이라면, 사용자가 몰리는 시간때에 동시 접속 인원이 많아, 대기 순위를 받아본 적이 있을 것입니다. 사람들이 많이 몰리기 때문에, 먼저 온 순서대로 게임에 들어가게 해줘야 겠죠 ? 마찬가지로 Queue개념이 들어갑니다.

 

 

 

Queue에는 rear와 front라는 개념이 나옵니다. rear는 데이터가 들어가는 부분, front는 데이터가 나오는 부분입니다. 실제로 구현을 하면 이해가 안갈 수 있는데, rear를 사용해서 데이터를 넣고, front를 사용해서 데이터를 뺀다 라고 생각하시면 될 것 같습니다. 사실 rear와 front는 index를 의미하는 정수형 데이터입니다.

 

Enqueue는 데이터를 넣는 행동(함수), Dequeue는 데이터를 빼는 행동(함수)입니다. 

 

 

1. 선형큐 : 1차원 배열을 사용하여 순차 자료구조 방식으로 큐를 구현

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Queue que = new Queue(10);
        que.enQueue('A');
        que.enQueue('B');
        que.enQueue('C');
        que.delete();
        que.print();
        
    }
}

class Queue {
    int front = -1; // 저장된 원소중에 첫번쨰 원소
    int rear = -1; // 저장된 원소중에 마지막 원소
    int size;
    char items[];

    Queue(int size) {
        this.size = size;
        items = new char[this.size];
    }

    boolean isEmpty() {
        return front == rear;
    }

    boolean isFull() {
        return rear == this.size - 1;
    }

    void enQueue(char item) {
        if (isFull()) {
            System.out.println("큐가 모두 차있습니다");
        } else {
            items[++rear] = item;
        }
    }

    char deQueue() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다");
            return 0;
        } else {
            return items[++front];
        }
    }

    void delete() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다");
        } else {
            ++front;
        }
    }

    char peek() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다");
            return 0;
        } else {
            return items[front + 1];
        }
    }

    void print() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다");
        } else {
            for (int i = front + 1; i <= rear; i++) {
                System.out.print(items[i]);
            }
            System.out.println();
        }
    }
}

 

 

enQueue()와 deQueue()에서 각각 rear, front 변수를 사용하고 있습니다. 

enQueue()를 보면, 데이터를 넣기 전에 Queue의 포화상태를 검사하고 rear을 증가한 후, 그 위치에 값을 넣고 있습니다.

deQueue()를 보면, 데이터를 뺴기 전에 Queue가 비어있는지 검사하고 front를 증가한 후, 그 위치의 값을 반환하고 있습니다.

 

사실 전체 배열에서 데이터가 없어진 것은 아닙니다. 단순히 front와 rear라는 index를 사용하여 그 범위를 바꿔줄 뿐이죠.

 

하지만, 선형큐가 만약 다 차버리면 어떻게 될까요 ? 데이터를 삭제하고 다시 넣을 수 있지만, 선형큐의 포화조건이 rear==size-1 입니다.

이 말은 즉, 뒤에서 아무리 삭제(++front) 포화조건을 검사하는데 아무런 영향을 주지 못합니다. 그렇기 때문에, 선형큐의 경우 데이터를 추가할 수 있는 상황이라도 데이터를 추가 하지 못하는 것이죠. 이런 문제를 해결하기 위해 원형큐가 나오게 됩니다.

 

 

2. 원형큐 : 선형큐와 마찬가지고 1차원 배열을 사용하는데, 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 생각합니다.

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Queue que = new Queue(10);
        que.enQueue('A');
        que.enQueue('B');
        que.enQueue('C');
        que.delete();
        que.print();

    }
}

class Queue {
    int front = 0; // 저장된 원소중에 첫번쨰 원소
    int rear = 0; // 저장된 원소중에 마지막 원소
    int size;
    char items[];

    Queue(int size) {
        this.size = size;
        items = new char[this.size];
    }

    boolean isEmpty() {
        return front == rear;
    }

    boolean isFull() {
        return (((rear + 1) % this.size) == front);
    }

    void enQueue(char item) {
        if (isFull()) {
            System.out.println("큐가 모두 차있습니다");
        } else {
            rear = (rear + 1) % this.size;
            items[rear] = item;
        }
    }

    char deQueue() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다");
            return 0;
        } else {
            front = (front + 1) % this.size;
            return items[front];
        }
    }

    void delete() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다");
        } else {
            front = (front + 1) % this.size;
        }
    }

    char peek() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다");
            return 0;
        } else {
            return items[(front + 1) % this.size];
        }
    }

    void print() {
        if (isEmpty()) {
            System.out.println("큐가 비어있습니다");
        } else {
            for (int i = (front + 1) % this.size; i != (rear + 1) % this.size; i = ++i % this.size) {
                System.out.print(items[i]);
            }
            System.out.println();
        }
    }
}

원형큐를 구현할 떄는 신기하게, 나머지연산자(%)를 사용했습니다. 원형큐의 특징은 계속 꼬리를 물면서 데이터를 넣는 것인데, 만약 데이터를 하나 넣는데 배열의 인덱스를 벗어나면, 다시 0부터 다시 채워져야 합니다(0에 데이터가 없다면). 

 

예를 들어, 배열의 크기가 7이고, 현재 rear가 6이라고 가정해봅시다. 여기서 데이터를 하나 더 넣으면, rear 7위치에 넣게 되는데 이는 배열 크기를 벗어나게 되겠죠 ? 여기서는 다시 0위치에 넣어줘야 합니다. 그게 원형Queue니깐요 !!

그래서 (rear+1) % size를 해줍니다. +1을 한 것은, 다음 공간에 넣기 위해 한 것이고, 7 % 7 은0이 되므로, 다시 0번쨰 위치부터 데이터를 넣게 됩니다.