[자료구조] 큐 (Queue)

큐 (Queue)

• 추가되는 자료를 차례대로 저장하여, 저장된 순서에 의해 데이터가 나오는 자료구조
• FIFO (First In First Out, 선입선출)
• 저장된 자료들은 선후 관계가 모두 1:1
• front : 큐의 제일 앞, 자료가 반환되는 곳
• rear : 큐의 제일 뒤, 자료가 추가되는 곳
• enqueue() : 큐에 자료를 삽입하는 함수
• dequeue() : 큐에서 자료를 빼내는 함수
• peek() : 큐에 맨 위에 있는 자료 반환하는 함수 (큐에서 삭제는 하지 않는다)
• 큐의 크기 : 큐가 저장할 수 있는 최대 자료의 개수 → 이 갯수를 넘어버리면 오버플로우(Overflow) 발생
• ex) 은행 업무 처리 대기열, 프린터 대기 문서

 

//배열로 구현한 선형 큐
public class Main {

    static final int QUEUE_SIZE = 5;
    static int queue[] = new int[QUEUE_SIZE];
    static int front = -1;
    static int rear = -1;
    
    static void enqueue(int element)
    {
        queue[++rear] = element;
    }

    static int dequeue()
    {
        return queue[++front];
    }

    static int peek()
    {
        return queue[front+1];
    }
    public static void main(String[] args) {

        enqueue(3);
        enqueue(5);
        enqueue(10);
        System.out.println(peek());
        System.out.println(dequeue());
        System.out.println(dequeue());
        System.out.println(dequeue());

        /* 결과 :
        3
        3
        5
        10
        */
    }
}

 

---

원형 큐 (Circular Queue)

• 배열로 구현한 선형 큐의 단점은 front가 이미 사용된 공간에는 다시는 자료를 넣을 수 없다는 점이다 → 이를 해결하기 위해서 배열의 오른쪽과 왼쪽을 연결한 원형 큐가 대안으로 제시됨
• rear가 무한히 오른쪽으로 이동할 수 있다.
• enqueue : rear = (rear + 1) % QUEUE_SIZE
• dequeue : front = (front + 1) % QUEUE_SIZE

 

//배열로 구현한 원형큐
public class Main {

    static final int QUEUE_SIZE = 5;
    static int circular_queue[] = new int[QUEUE_SIZE];
    static int front = -1;
    static int rear = -1;

    static void enqueue(int element)
    {
        rear = (rear + 1) % QUEUE_SIZE;
        circular_queue[rear] = element;
    }

    static int dequeue()
    {
        front = (front + 1) % QUEUE_SIZE;
        return circular_queue[front];
    }

    static int peek()
    {
        return circular_queue[(front+1) % QUEUE_SIZE];
    }
    public static void main(String[] args) {

        enqueue(3);
        enqueue(5);
        enqueue(10);
        enqueue(12);
        enqueue(15);
        enqueue(16);
        enqueue(17);

        for (int i = 0; i < 7;i++)
        {
            System.out.println(dequeue());
        }
        /* 결과 :
        16
        17
        10
        12
        15
        16
        17
        */
    }
}

 

---

덱 (Deque, Double-Ended Queue)

• 두 개의 끝을 가지는 큐
• 양쪽 끝에서 자료 삽입, 반환이 모두 가능한 선형 자료구조

연산		덱	스택	큐
front 앞	추가	insertFront	x	x
​	반환	deleteFront	x	dequeue
rear 뒤	추가	insertRear	push	enqueue
​	반환	deleteRear	pop	x