[ 개념 ] 23. 큐(Queue)

> 큐(QUEUE)란?

---

큐의 개념

Queue의 사전적의미는 1.(무엇을 기다리는 사람, 자동차 등의) 줄, 혹은 줄을 서서 기다리는 것을 의미한다.

따라서 일상생활에서 놀이동산에서 줄을 서서 기다리는 것, 은행에서 먼저 온 살마의 업무를 창구에서 처리하는 것과 같이 선입선출(FIFO, First in First out) 방식의 자료구조를 말한다.

큐의 특징

정해진 한 곳(top)을 통해서 삽입, 삭제가 이루어지는 스택과는 달리 큐는 한쪽 끝에서 삽입 작업이, 다른 쪽 끝에서 삭제 작업이 양쪽으로 이루어진다.

이 때 삭제연산만 수행되는 곳을 프론트(front), 삽입연산만 이루어지는 곳을 리어(rear)로 정하여 각각의 연산작업만 수행된다.

이 때, 큐의 리어에서 이루어지는 삽입연산을 인큐(enQueue), 프론트에서 이루어지는 삭제연산을 디큐(deQueue)라고 부른다.

• 큐의 가장 첫 원소를 front / 가장 끝 원소를 rear
• 큐는 들어올 때 rear로 들어오지만 나올 때는 front부터 빠지는 특성
• 접근 방법은 가장 첫 원소와 끝 원소로만 가능
• 가장 먼저 들어온 프론트 원소가 가장 먼저 삭제

즉, 큐에서 프론트 원소는 가장 먼저 큐에 들어왔떤 첫 번째 원소가 되는 것이며, 리어 원소는 가장 늦게 큐에 들어온 마지막 원소가 되는 것이다.

큐의 활용 예시

큐는 주로 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.

• 우선순위가 같은 작업 예약 (프린터의 인쇄 대기열)
• 은행 업무
• 콜센터 고객 대기시간
• 프로세스 관리
• 너비 우선 탐색(BFS) 구현
• 캐시(Cache) 구현

Queue Interface

클래스로 구현된 스택과는 달리 자바에서 큐 메모리 구조는 별도의 인터페이스 형태로 제공된다.

이러한 Queue 인터페이스를 상속받는 하위 인터페이스는 다음과 같다.

1. Deque<E>
2. BlockingDeque<E>
3. BlockingQueue<E>
4. TransferQeue<E>

따라서 Queue 인터페이스를 직간접적으로 구현한 클래스는 상당히 많다. 그중에서도 Dequeue 인터페이스를 구현한 LinkedList 클래스가 큐 메모리 구조를 구현하는 데 가장 많이 사용된다.

큐 메모리 구조는 선형 메모리 공간에 데이터를 저장하면서 선입선출(FIFO)의 시멘틱을 따르는 자료구조이다.

즉, 가장 먼저 저장된(push) 데이터가 가장먼저 인출(pop)되는 구조이다.

Queue 인터페이스는 큐 메모리 구조를 표현하기 위해, 다음과 같은 Collection 인터페이스 메소드만을 상속받아 사용한다.

메소드	설명
boolean add(E e)	해당 큐읜 맨 뒤에 전달된 요소를 삽입. 삽입에 성공하면 true , 큐에 여유공간이 없어 삽입에 실패하면 illegalStateException을 발생시킴
E element()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소 반환
boolean offer(E e)	해당 큐의 맨 뒤에, 전달된 요소를 삽입
E peek()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환 만약 큐가 비어 있으면 null 반환
E poll()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 반환하고 해당 요소를 큐에서 제거 만약 큐가 비어 있으면 null 반환
E remove()	해당 큐의 맨 앞에 있는(제일 먼저 저장된) 요소를 제거

더욱 복잡하고 빠른 큐를 구현하고 싶다면 Deque 인터페이스를 구현한 ArrayDeque클래스를 사용하면 된다.

Deque<Integer> q = new ArrayDeque<Integer>();

-구현

import java.util.*;
public class Queue{

    public static void main(String[] args){
        LinkedList<String> q = new LinkedList<String>()    // 큐의 생성
        //Deque<String> q = new ArrayDeque<String>();

        // add() 메소드를 이용한 요소의 저장
        q.add("넷");
        q.add("둘");
        q.add("셋");
        q.add("하나");

        // peek() 메소드를 이용한 요소의 반환
        System.out.println(q.peek());
        System.out.println(q);

        // poll() 메소드를 이용한 요소의 반환 및 제거
        System.out.println(q.poll());
        System.out.println(q);

        // remove() 메소드를 이용한 요소의 제거
        q.remove("하나");
        System.out.println(q);
    }
}

# 실행결과
넷
[넷, 둘 셋, 하나]
넷
[둘, 셋, 하나]
[둘, 셋]