[알고리즘] 자료구조 : 큐 (Queue)

Queue

큐는 자료구조의 스택과 반대의 구조라고 생각하면 된다. 큐는 FIFO(First In First OUt)의 형태를 가지게 된다. 가장 먼저 들어온 데이터가 가장 먼저 나가는 구조를 말한다.
카페에 대입해서 설명해보면 카페에서 음료를 시키고 받은 주문번호가 있을 것이다. 이 번호표 기계도 프로그래밍된 프로그램인데 그 번호가 108번이라면 내 번호인 108번을 부를 때는 처음인 1번부터 확인해서 이 손님이 서비스를 받았는지 안 받았는지 확인하며 다음으로 호출할 번호를 정할까?
이러면 매우 비효율 적이다. 단순하게 생각하면 서비스를 받을 처음 위치와 마지막의 위치만 기억하면 모든게 쉽게 풀린다. 이 위치들을 큐에서는 front, rear이라고 한다.

 

위 그림을 보면 Enqueue는 맨 뒤에 어떤 요소를 추가 즉, 마지막으로 온 손님에게 번호표를 부여, Dequeue는 맨 앞쪽의 요소를 삭제, 즉 카페에서 음료를 받은 손님의 번호표를 대기목록에서 삭제이다.

정리해보면

• Enqueue: 큐 맨 뒤에 데이터를 추가
• Dequeue: 큐 맨 앞쪽의 데이터를 삭제
• Peek: front에 위치한 데이터를 읽음(다음 주문을 받을 손님이 누구인지 확인)
• front: 큐의 맨 앞의 위치, 다음 서비스를 받을 손님의 번호
• rear: 큐의 맨 뒤의 위치, 마지막에 온 손님의 번호

 

특징

1. 큐의 한쪽 끝은 Front로 정하여 삭제 연산만 수행한다.
2. 다른 한쪽 끝은 Rear로 정하여 삽입 연산만 수행한다.
3. 그래프의 넓이 우선 탐색(BFS)에서 사용된다.
4. 컴퓨터 버퍼에서 주로 사용, 마구 입력이 되었으나 처리를 하지 못할 때, 버퍼(큐)를 만들어 대기시킨다. 먼저 들어온 입력 먼저 처리

 

[Java] 배열을 이요한 Queue 구현

먼저 자바에서 제공해주는 Queue클래스를 이용해 Queue를 구현해 보자.

자바에서는 스택을 클래스로 구현하여 제공하지만 큐는 Queue인터페이스만 있고 별도의 클래스가 없다. 그래서 Queue인터페이스를 ㅜ현한 클래스들을 사용해야 한다.

import java.util.LinkedList;
import java.util.Queue;

public class Main {

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

        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        queue.offer(4);
        queue.offer(5);

        while(!queue.isEmpty()) {
            System.out.println(queue.poll());
        }

    }

}

출력 결과:

1
2
3
4
5

• queueIsEmpty(): 큐 안이 비었는지 판단하는 함수
• queueIsFull(): 배열의 최대 크기를 벗어나면 안 되기에 큐에 더 이상 들어갈 공간이 없는지 판단하는 함수
• size(): queue에 현재 들어가 있는 데이터의 개수를 return 하는 함수
• push(int value): 큐 안에 데이터를 집어넣는 함수
• peek(): 큐 안의 데이터들 중 가장 먼저 나오는 데이터를 return 하는 함수
• pop(): 큐 안의 데이터들 중 가장 먼저 나올 수 있는 데이터를 return 하고 삭제하는 함수

public class ArrayQueue {
    int MAX = 1000;
    int front;    //머리 쪽에 위치할 index값, pop할때 참조하는 index
    int rear;    //꼬리 쪽에 위치할 index값, push할때 참조하는 index
    int [] queue;
    public ArrayQueue() {
        front = rear = 0;    //초기값 0
        queue = new int[MAX]; //배열 생성
    }

    public boolean queueisEmpty() { //queue에 아무것도 들어있지 않은지 판단하는 함수
        return front == rear;
    }
    public boolean queueisFull() {    //queue가 가득 차 공간이 없는지 판단하는 함수
        if(rear == MAX-1) {
            return true;
        }else 
            return false;
    }
    public int size() { //queue에 현재 들어가 있는 데이터의 개수를 return
        return front-rear;
    }
    public void push(int value) {
        if(queueisFull()) {
            System.out.println("Queue is Full");
            return;
        }
        queue[rear++] = value; //rear가 위치한 곳에 값을 넣어주고 rear를 증가시킨다.
    }
    public int pop() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[front++];
        return popValue;
    }
    public int peek() {
        if(queueisEmpty()) {
            System.out.println("Queue is Empty");
            return -1;
        }
        int popValue = queue[front];
        return popValue;
    }
}

 

스택과 마찬가지로 배열과 연결 리스트를 이용하여 구현할 수 있다. 배열과 연결리스트 모두 장단점이 존재하기 때문에 , 그 상황에 맞게 사용할 자료구조를 정하면 된다. 배열과 연결 리스트로 (Queue)를 구현하면 치명적인 문제점이 있다. 이 문제점을 해결하기 위해 원형-큐(Circular Queue)가 있다. 이는 다음에 정리해보겠다.