큐

큐의 개념

큐(queue)는 줄을 서다 라는 뜻을 가지고 있습니다. 큐는 먼저 들어간 데이터가 먼저 나오는 자료구조입니다. 역시 스택과 마찬가지로 생활 속에서 쉽게 예를 찾아볼 수 있습니다. 맛집에서 줄을 선 순서대로 식당에 입장할 때를 생각해보면 됩니다. 먼저 줄을 선 사람이 먼저 입장합니다. 이런 큐의 특징을 선입선출 또는 FIFO(first in first out)이라고 합니다. 그리고 큐에서는 삽입하는 연산을 Enqueue(Add), 꺼내는 연산을 Dequeue(Poll)이라고 합니다.

 

큐의 특성을 활용하는 분야

먼저 들어온 것을 먼저 처리하는 큐의 동작 방식은 프로그래밍 언어에서 많이 활용되고 있습니다. 대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용됩니다. 실생활에서도 큐의 특성은 자연스럽게 사용되고 있습니다. 영화관에서 줄을 서는 사람들을 처리해야 할 때 먼저 줄을 선 사람을 먼저 처리하는 것이 그 예죠. 그 밖의 큐의 특성을 활용하는 분야는 다음과 같습니다.

• 작업 대기열 : 네트워크 통신을 할 때 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리합니다. 이때 큐를 활용할 수 있습니다.
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스 움직임을 처리할 때 큐를 활용할 수 있습니다.

큐 구현하기

큐를 간단하게 구현하는 방식은 크게 2가지 방식이 있습니다. 첫 번째는 Queue 인터페이스를 활용하는 방식, 두번째는 덱(ArrayDeque)클래스를 활용하는 방식입니다. 
 

Queue 인터페이스 사용하기

Queue 인터페이스를 사용하는 방식부터 설명하겠습니다. add 연산은 add() 메서드를 활용하고, poll 연산은 poll() 메서드를 활용합니다.
참고로 add 연산은 offer()메서드로도 할 수 있습니다. add() 메서드와 offer() 메서드는 내부적으로 결국 같은 로직을 수행합니다만 내부에서 메서드 호출 횟수가 offer()가 1회 더 많기 때문에 add() 메서드를 사용하는 것이 아주 근소한 차이로 빠를 수 있습니다..
 
자바 컬렉션 프레임워크에서 Queue는 인터페이스로 구현되어 있습니다. Queue의 구현체로 자주 사용하는 클래스는 ArrayDeque와 LinkedList가 있습니다. 단순히 코딩 테스트에서 Queue만을 구현하려면 둘 중 어떤 클래스를 구현체로 사용해도 괜찮습니다만 일반적인 코딩 테스트에서는 LinkedList 보다는 ArrayDeque를 더 많이 사용하므로 ArrayDeque에 대해 알아보겠습니다.
 

// 큐를 구현한 ArrayDeque 개개체 생성
Queue<Integer> queue = new ArrayDeque<>();

// 큐에 데이터 추가
queue.add(1);
queue.add(2);
queue.add(3);

// 큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.poll();
System.out.println(first); //1

// 큐에 데이터 추가
queue.add(4);
queue.add(5);

// 큐의 맨 앞 데이터를 제거하면서 반환
first = queue.poll();
System.out.println(first); // 2

 

덱을 큐처럼 활용하기

다음은 덱을 큐처럼 활용하는 방법입니다. 덱은 Double Ended Queue를 줄인 말입니다. 말 그대로 양 끝에서 삽입이나 삭제할 수 있는 큐를 구현한 겁니다. 양 끝에서 삽입이나 삭제를 할 수 있다는 특징 때문에 큐를 구현하라 때는 덱을 사용하는 것도 좋습니다.

ArrayDeque<Integer> queue = new ArrayDeque<>();

// 큐에 데이터 추가
queue.addLast(1);
queue.addLast(2);
queue.addLast(3);

// 큐의 맨 앞 데이터를 제거하면서 반환
int first = queue.pollFirst();
System.out.println(first); // 1

// 큐에 데이터 추가
queue.addLast(4);
queue.addLast(5);

// 큐의 맨 앞 데이터를 제거하면서 반환
first = queue.pollFirst();
System.out.println(first); // 2

 
사실 ArrayDeque에도 Queue와 동일한 역할은 하는 add() 메서드와 poll() 메서드가 있습니다. 동작하는 방식도 같습니다. 하지만 이 코드에서는 addLast() 메서드와 pollFirst() 메서드를 대신 사용했습니다. 왜 그랬을까요? 다음 그림을 보면서 설명하겠습니다.

그림을 보면 큐를 기준으로 왼쪽이 First, 오른쪽이 Last라고 한다면 데이터를 왼쪽에서 꺼내는 것은 pollFirst(), 오른쪽으로 넣는 것은 addLast()입니다. 이렇게 하면 메서드의 이름을 더욱 직관적으로 이해할 수 있습니다. 추가로 데이터를 addFirst()로만 넣고, pollFirst() 로만 꺼내면 동작은 스택의 push(), pop()과 동일하므로 ArrayDeque 하나면 큐, 스택 그리고 덱을 전부 구현할 수 있습니다.