[코딩 테스트 Java] 큐 ❶

이 글은 〈[되기] 코딩 테스트 합격자 되기(자바 편)〉에서 발췌했습니다.

골든래빗 출판사
김희성, 박경록 지음

큐 개념을 이해하고, 이를 바탕으로 ADT를 작성할 수 있습니다.

큐 ❶ – 큐의 개념

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

1. 큐에서 데이터가 이동하는 과정 살펴보기

그림을 통해 큐에서 원소가 이동하는 과정을 이해해봅시다.

01단계 빈 큐를 하나 선언했습니다.

02단계 원소를 삽입합니다. 빈 큐이므로 제일 앞에 삽입합니다. 이어서 5를 삽입합니다. 5는 2 다음으로 삽입했으니 2보다는 뒤에 있습니다.

03단계 Dequeue을 하면 5가 아니라 2가 먼저 나옵니다. 이어서 Dequeue을 한 번 더 진행하면 5가 빠져나옵니다. 스택을 공부했다면 큐에서 데이터가 이동하는 과정은 이 정도 설명이면 쉽게 이해할 수 있을 겁니다.

2. 큐의 특성을 활용하는 분야

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

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

3. 큐의 ADT

여기서도 스택과 마찬가지로 큐의 ADT를 정의해보고 큐가 실제로 동작하는 원리를 살펴보겠습니다.

큐의 ADT는 다음과 같습니다. 여기서도 표와 그림으로 설명하겠습니다.

그림은 큐의 ADT를 나타낸 겁니다. 큐의 외부와 내부에 네모 모양으로 표현한 연산과 데이터 상태가 보입니다. 이 그림은 스택에서 제시했던 그림이므로 쉽게 이해할 수 있을 겁니다. 달라진 점은 스택의 top이 front와 rear로 바뀐 겁니다. front는 큐의 앞, rear는 큐의 뒤를 의미합니다. 큐는 앞에서 데이터를 빼고(poll), 뒤에서 데이터를 넣으므로(add) 이렇게 앞과 뒤의 데이터 최종 위치를 기억할 변수가 필요합니다. 지금의 경우 아무런 데이터도 넣은 상태가 아니므로 front와 rear 모두 -1입니다.

※ 배열의 인덱스는 0부터 시작하므로 아무것도 넣지 않은 상황을 표현하기 위해 초깃값을 -1로 했습니다.

4. 큐의 세부 동작에 대해 조금 더 자세히 알아보기

구체적인 예와 함께 큐에서 연산이 수행되면 어떻게 되는지 알아보겠습니다.

01단계 다음은 isFull( ) 연산으로 ➊ 현재 큐가 가득 찼는지 확인하고 큐가 가득 차지 않았으므로 (isFull이 false) ➋ rear를 +1한 다음 rear가 가리키는 위치에 ➌ 3을 add하는 모습입니다.

※ 반대로 isFull 연산이 true이면 데이터를 add하지 않습니다.

02단계 이 상태에서 poll을 하면 어떻게 될까요? ➊ 우선 isEmpty( ) 연산을 통해 큐가 비었는지 확인합니다. isEmpty( ) 연산은 front, rear의 값이 같은지 확인해서 큐에 원소가 없는데 poll하는 동작을 방지합니다. ➋ 만약 비어 있지 않다면(isEmpty가 false) front를 +1합니다. 이렇게 하면 front, rear가 0으로 같아지므로 ➌ isEmpty( ) 연산 시 큐가 빈 것(isEmpty( )가 true)으로 처리되어 실제 배열의 데이터를 삭제하지 않고도 데이터를 삭제한 것처럼 관리할 수 있습니다.

03단계 계속해서 add를 해봅시다. ➊ 5를 add하면 isFull( ) 연산을 수행해 큐가 가득 찼는지 검사하고, 가득 차지 않았다면 add합니다. ➋ 연거푸 6과 8을 add하면 다음과 같이 front는 0, rear는 3일 겁니다.

04단계 이제 큐가 가득 찼을 때 add하면 어떻게 되는지 봅시다. ➊ rear가 3이므로 maximize -1과 같습니다. 다시 말해 ➋ isFull( ) 연산은 true이므로 add하지 못합니다.

큐가 가득 찬 상태에서 하나 생각해볼 내용이 있습니다. 마지막 add에서 실제 data에 저장한 데이터는 3, 5, 6, 8로 4개지만 큐는 5, 6, 8로 3개입니다. 다시 말해 큐는 front의 다음부터 rear까지를 큐가 관리하는 데이터로 생각해야 합니다. 그런데 가만히 생각해보면 실제 data의 공간은 4개인데 큐가 관리하는 데이터는 3개이므로 실질적으로는 메모리 공간을 낭비한 상황입니다. 이렇게 된 이유는 큐를 한 방향으로 관리하고 있기 때문입니다. 이렇게 하면 front 이전의 공간을 활용하지 못합니다. 다시 말해 front 이전을 기준으로 큐의 사용할 수 있는 부분과, 사용할 수 없는 부분으로 나뉘게 됩니다.

💡합격 조언_큐를 원형으로 개선하기

이를 개선하려면 책에서 설명한 형태의 큐가 아니라 다른 형태의 큐가 필요합니다. 책에서 설명한 큐는 선형으로 구현한 큐입니다. 선형 큐는 front와 rear가 한 방향으로 이동하죠. 이를 개선한 큐는 원형 큐입니다. 낭비하는 공간을 없애기 위해 원형으로 front와 rear가 돕니다.

원형 큐는 선형 큐보다 구현하기는 조금 복잡하지만 메모리 공간을 절약할 수 있다는 장점이 있습니다. 다만 코딩 테스트에서는 자바 컬렉션에서 제공하는 Queue 인터페이스를 사용해도 충분합니다. 왜냐하면 자바의 Queue는 배열 길이를 자동으로 관리하기 때문입니다. 다시 말해 메모리를 효율적으로 쓰기 위해 원형 큐를 사용할 필요는 없습니다.

이런 이유로 필자도 원형 큐를 본문에 설명해야 할지 말아야 할지 고민했으나, 코딩 테스트에서 쓰지 않아도 될 원형 큐를 장황하게 설명하기보다는 ‘메모리 관점에서 간단히 설명하는게 옳다’라고 생각했습니다. 원형 큐가 궁금하다면 인터넷으로 원형 큐를 검색하여 공부해보세요.

5. 큐 구현하기

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

5.1 Queue 인터페이스 사용하기

Queue 인터페이스를 사용하는 방식부터 설명하겠습니다. add 연산은 add( ) 메서드를 활용하고, poll 연산은 poll( ) 메서드를 활용합니다.

※ add 연산은 offer( ) 메서드로도 할 수 있습니다. add( ) 메서드와 offer( ) 메서드는 내부적으로 결국 같은 로직을 수행합니다만 내부에서 메서드 호출 횟수가 offer( )가 1회 더 많기 때문에 add( ) 메서드를 사용하는 것이 아주 근소한 차이로 빠를 수 있습니다. 물론 거의 차이가 없다고 봐도 좋습니다.

자바 컬렉션 프레임워크에서 Queue는 인터페이스로 구현되어 있습니다. Queue의 구현체로 자주 사용하는 클래스는 ArrayDeque와 LinkedList가 있습니다. 단순히 코딩 테스트에서 Queue만을 구현하려면 둘 중 어떤 클래스를 구현체로 사용해도 괜찮습니다만 일반적인 코딩 테스트에서는 LinkedList 보다는 ArrayDeque를 더 많이 사용하므로 공부 범위를 줄이기 위해 이 책은 Queue의 구현체로 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

5.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 하나면 큐, 스택 그리고 덱을 전부 구현할 수 있습니다.

자료구조, 알고리즘, 빈출 97 문제로 대비하는 코테 풀 패키지

[되기] 코딩 테스트 합격자 되기(자바 편)