[자료구조] Queue (큐) 구현 - 자바(JAVA)

큐(queue)

 

 

큐는 BFS(너비우선탐색) 알고리즘에서 자주 사용된다고 하여 배열로 구현해 보았다.

 

큐는 입구 1개, 출구 1개로 FIFO(First In First Out) 구조이며 스택(LIFO)과는 조금 다르다.

 

큐 구현을 위한 클래스 변수 3개

• front: 큐의 맨 앞 원소위치 (초기값 0)
• rear: 큐의 맨 뒤 원소위치 (초기값 -1)
• size: 큐의 원소 개수 (초기값 0)

메소드

• offer(Enqueue): 맨 뒤에 원소 삽입
• poll(Dequeue): 맨 앞에 원소 추출
• peek: 해당 메소드는 원래 맨 앞 원소를 확인하는 메소드인데 나는 front, back 메소드로 맨 앞, 맨 뒤 원소를 확인하는 메소드로 구현하였다.

 

poll 메소드를 사용하여 맨 앞 원소를 추출하기 전에 원소가 없는 경우를 판단해야 하는데 그때는 간단하게 size 변수를 사용해서 확인해도 되지만 front가 rear보다 더 큰 경우로 판단하였다.

 

일반적으로 자료구조를 구현할 때 예를 들어 배열을 사용하였다면 사이즈를 동적으로 조정하는 기능이 필요한데 나는 원형큐를 구현할 때 해당 기능을 붙여두었다. 

 

배열의 사이즈를 조정하는 기능이 필요한 이유

처음 배열의 사이즈를 10으로 잡은 후 5개 원소를 삽입(offer)하고 5개 원소를 추출(poll)하면 rear 변수는 4인 상태여서 앞으로 5개 밖에 원소를 더 추가하지 못하기 때문에 배열의 사이즈를 조정하는 기능이 필요하다.

혹은 남은 원소들을 앞으로 이동시키는 작업도 할 수는 있지만 이건 원소들이 많이 추출 되었을 때 가능하다는 제약사항이 존재한다.

 

배열의 사이즈를 조정하거나 남은 원소들을 앞으로 이동시키는 작업은 결국 O(n)의 시간복잡도가 발생하지만 불가피하다.

 

원형큐를 사용하는 이유

위 배열의 사이즈를 조정하는 기능이 필요한 이유에서 5개 원소를 추출하여 배열 0 ~ 4 인덱스가 비어있는데 5 ~ 9 인덱스만 사용할 수 있기 때문에  0 ~ 4 인덱스도 다시 사용할 수 있는 원형큐를 사용하는 경우도 많다.

 

 

https://jiji-gilog.tistory.com/4

자바(JAVA) - Circular Queue (원형큐) 구현

 

 

 

 

- 큐 구현 소스

public class Queue {

    private static int front = 0;
    private static int rear = -1;
    private static int size = 0;

    private static void offer(int[] queue, int val) {
        queue[++rear] = val;
        size++;
    }

    private static int poll(int[] queue) {
        // 데이터 없는 경우
        if(front > rear) {
            return -1;
        }

        size--;
        return queue[front++];
    }

    private static int size() {
        return size;
    }

    private static int empty() {
        if(size <= 0) {
            return 1;
        }

        return 0;
    }

    private static int front(int[] queue) {
        if(size <= 0) {
            return -1;
        }

        return queue[front];
    }

    private static int back(int[] queue) {
        if(size <= 0) {
            return -1;
        }

        return queue[rear];
    }
}

 

 

위 소스는 큐의 기능(메소드)만 구현한 소스이고 아래는 테스트가 가능한 전체 소스이다.

 

 

- 큐 구현 및 테스트 소스

public class Queue {

    private static int front = 0;
    private static int rear = -1;
    private static int size = 0;

    private static void offer(int[] queue, int val) {
        queue[++rear] = val;
        size++;
    }

    private static int poll(int[] queue) {
        // 데이터 없는 경우
        if(front > rear) {
            return -1;
        }

        size--;
        return queue[front++];
    }

    private static int size() {
        return size;
    }

    private static int empty() {
        if(size <= 0) {
            return 1;
        }

        return 0;
    }

    private static int front(int[] queue) {
        if(size <= 0) {
            return -1;
        }

        return queue[front];
    }

    private static int back(int[] queue) {
        if(size <= 0) {
            return -1;
        }

        return queue[rear];
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int cmd = Integer.parseInt(br.readLine());
        int[] queue = new int[cmd];

        for(int i = 0; i < cmd; i++) {
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();
            
            switch (str) {
                case "push":
                    offer(queue, Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    sb.append(poll(queue)).append("\n");
                    break;
                case "size":
                    sb.append(size()).append("\n");
                    break;
                case "empty":
                    sb.append(empty()).append("\n");
                    break;
                case "front":
                    sb.append(front(queue)).append("\n");
                    break;
                case "back":
                    sb.append(back(queue)).append("\n");
                    break;
            }
        }

        System.out.println(sb);
        br.close();
    }
}

 

 

 

- 이미지 출처

https://velog.io/@db_jam/%EC%9E%90%EB%B0%94-%ED%81%90Queue-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%A0%95%EB%A6%AC