[자료구조] Queue

overview

이번 포스트에서 공부할 자료구조는 Queue이다.

Queue

Queue를 우리나라 말로 변역을 하면 대기줄, 열, 동사로는 차례를 기다리다 라는 뜻으로 사용이 되어진다.
예시로 들면 은행의 대기표와 같은 것이다. 은행에 먼저 온 사람이 먼저 대기표를 뽑고 먼저 은행업무를 본다. 그리고 들어온 순서대로 대기 순번을 갖고 대기 순번대로 은행일을 보고 은행을 나간다.

Queue는 구멍이 두 개인다. Stack과 다르게 들어오는 입구와 나가는 출구가 다르다. 그래서 먼저 들어온 데이터가 먼저 나가는 구조를 가지고 있다. 이를 선입선출(Frist In, Last Out)이라고 한다.

자바를 기준으로 Queue에서 많이 사용이 되는 메소드에 대해서 알아보자.
add, add는 Queue에 데이터를 넣을 때 사용이 된다.
remove, remove는 Queue에 데이터 삭제할 때 사용이 된다.
peek, peek은 가장 첫 번째에 있는 값을 조회하고 싶을 때 사용이 된다.

자바에서 Queue를 사용해보기

add

public class QueueStudy {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);
        queue.add(2);
        queue.add(3);

        System.out.println("queue :" + queue);
    }
}

queue에 add메소드로 1,2,3을 넣고 출력을 해보았다.

1, 2, 3이 잘 들어가 있는 것을 확인을 할 수 있다.

remove

public class QueueStudy {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);
        queue.add(2);
        queue.add(3);

        Integer remove = queue.remove();

        System.out.println("remove :" + remove);
    }
}

1, 2, 3이 들어있는 Queue에 remove를 했을 때 반환을 하는 값을 출력을 해보았다.

값으로 1이 나왔다.
이 결과를 보면 Queue가 선입선출이라는 구조라는 것을 알 수 있다.
코드를 보면 1을 가장 먼저 넣어주었다. 그리고 remove을 했을 때 1이 나왔다라는 것은 가장 먼저 넣어주었던 1이 가장 앞에 있ㄷ기 때문에 나왔다라는 것이다. 이를 통해서 Queue가 선입선출이라는 구조를 가지고 있다는 것을 알 수 있다.

peek

public class QueueStudy {
    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedList<>();

        queue.add(1);
        queue.add(2);
        queue.add(3);

        Integer peek = queue.peek();

        System.out.println("peek :" + peek);
    }
}

peek은 가장 앞에 있는 데이터를 조회하는 메소드이다. 마찬가지로 1, 2, 3을 넣어주고 peek을 해보고 출력을 해보았다.

가장 먼저 넣어서 가장 앞에는 1이 나온 것을 알 수 있다. 이 또한 Queue의 선입선출의 구조를 의미하는 것이다.

자바에서 Queue를 구현해보기

public class MakeQueue {

    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int currentSize;

    public MakeQueue(int size) {
        this.maxSize = size;
        this.queueArray = new int[maxSize];
        this.front = 0;
        this.rear = -1;
        this.currentSize = 0;
    }

    public void add(int value) {
        if (isFull()) {
            System.out.println("가득 차있습니다.");
            return;
        }
        // 순환 큐 처리
        rear = (rear + 1) % maxSize;
        queueArray[rear] = value;
        currentSize++;
    }

    public int remove() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot dequeue");
            return -1; // 큐가 비어있으면 -1 반환
        }
        int temp = queueArray[front];
        front = (front + 1) % maxSize; // front 위치를 한 칸 앞으로 이동 (순환)
        currentSize--;
        return temp;
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty. Cannot peek");
            return -1;
        }
        return queueArray[front];
    }

    public boolean isEmpty() {
        return (currentSize == 0);
    }

    public boolean isFull() {
        return (currentSize == maxSize);
    }
}

자바로 Queue를 구현을 해주었다.
Queue에 경우 입구와 출구가 따로 존재하기 때문에 이를 구분하기 위해서 front와 rear로 구분을 해주었다.
그래서 add에 경우 뒤로 들어가야 하기 때문에 rear를 이용을 했고 remove에 경우 앞에서 나가기 때문에 front를 활용을 해서 구현을 해주었다.