ArrayDeque로 스택과 큐 다루기

웹 브라우저의 뒤로 가기 버튼은 가장 최근에 본 페이지부터 되돌아갑니다. 반대로 프린터는 먼저 보낸 문서부터 인쇄합니다. 둘 다 '값을 모아 두었다가 하나씩 꺼낸다'는 점은 같지만 꺼내는 순서가 정반대입니다. 나중에 넣은 것을 먼저 꺼내는 구조를 스택(stack)이라 하고, 이 순서를 LIFO(last in, first out)라고 부릅니다. 먼저 넣은 것을 먼저 꺼내는 구조는 큐(queue)이고, 그 순서는 FIFO(first in, first out)입니다.

스택과 큐는 데이터를 배열에 담는지 연결 목록에 담는지로 정해지지 않습니다. 어떤 연산을 허용하고, 그 연산이 어떤 순서로 원소를 꺼내는지로 정해집니다. 이렇게 연산과 그 의미로 정의하는 자료구조를 추상 자료형(abstract data type)이라고 합니다. Java에서는 양쪽 끝 모두에서 넣고 꺼낼 수 있는 Deque 인터페이스 하나로 스택과 큐를 모두 표현합니다. 이 글에서는 Deque의 메서드와 기본 구현 ArrayDeque를 익히고, 스택으로 괄호의 짝을 검사하는 예제를 만들어 봅니다.

같은 데이터도 꺼내는 끝에 따라 순서가 달라집니다

작업 A, B, C를 차례로 받아 받은 순서대로 처리해야 한다고 해 봅시다. 다음 코드는 변수 이름을 queue로 지었고 뒤쪽 끝에 작업을 넣었습니다. 그런데 꺼낼 때도 뒤쪽 끝에서 꺼냅니다.

import java.util.ArrayDeque;
import java.util.Deque;

public final class WrongQueueEndBug {
    public static void main(String[] args) {
        Deque<String> queue = new ArrayDeque<>();
        queue.addLast("A");
        queue.addLast("B");
        queue.addLast("C");
        while (!queue.isEmpty()) {
            System.out.print(queue.removeLast());
        }
    }
}

CBA

원하던 ABC가 아니라 CBA가 출력됐습니다. addLast로 넣고 나면 덱 안의 순서는 앞에서부터 A, B, C입니다. 그런데 removeLast는 뒤쪽 끝에서 꺼내므로, 가장 나중에 들어온 C가 가장 먼저 나옵니다. 변수 이름은 큐인데 실제로는 스택처럼 동작한 것입니다. 이 프로그램은 println이 아니라 print로 출력하므로 출력 끝에 줄바꿈이 없다는 점도 함께 기억해 두세요.

FIFO를 만들려면 넣는 끝과 꺼내는 끝이 서로 달라야 합니다. 뒤에 넣고 앞에서 꺼내면 먼저 들어온 원소가 먼저 나옵니다. 반대로 LIFO는 한쪽 끝에서 넣고 같은 끝에서 꺼냅니다. 스택과 큐를 가르는 것은 클래스 이름이 아니라 넣는 끝과 꺼내는 끝의 조합입니다.

Deque 메서드는 끝과 실패 방식으로 고릅니다

덱(deque)은 double-ended queue의 줄임말로, 앞(first)과 뒤(last) 양쪽 끝에서 원소를 넣고, 꺼내고, 들여다볼 수 있는 자료구조입니다. 그래서 Deque의 메서드 이름은 두 가지를 알려 줍니다. 하나는 어느 끝에서 하는 일인지이고, 다른 하나는 연산이 실패했을 때 어떻게 알리는지입니다.

연산이 실패하는 경우는 두 가지입니다. 비어 있는 덱에서 꺼내거나 들여다보려 할 때, 그리고 용량이 정해진 덱이 가득 찬 상태에서 넣으려 할 때입니다. 이때 add, remove, get으로 시작하는 메서드는 예외를 던집니다. 반대로 offer, poll, peek으로 시작하는 메서드는 특별한 값을 돌려줍니다. 넣기에 실패하면 false를, 꺼내거나 들여다보는 데 실패하면 null을 돌려줍니다.

비어 있을 때 removeFirst나 getFirst 같은 예외형 메서드는 NoSuchElementException을 던집니다. 꽉 찬 덱에 넣는 add 계열은 IllegalStateException을 던지는데, 뒤에서 보듯 ArrayDeque는 필요할 때 스스로 커지므로 가득 차서 넣기에 실패하는 일이 없습니다.

어느 쪽을 쓸지는 비어 있는 상태가 정상인지에 따라 정합니다. 작업 큐가 비어 있는 것은 '지금은 할 일이 없다'는 평범한 상황이므로, poll로 꺼내고 null이면 쉬면 됩니다. 반대로 비어 있을 리 없는 곳에서 비어 있다면 프로그램에 버그가 있다는 뜻입니다. 그럴 때는 remove를 써서 그 자리에서 바로 예외로 멈추게 하는 편이 문제를 찾기 쉽습니다.

ArrayDeque는 null 원소를 받지 않습니다. offer(null)이나 push(null)을 호출하면 NullPointerException이 납니다. 덕분에 poll이 돌려준 null은 언제나 '비어 있음'이라는 한 가지 뜻입니다. 반면 LinkedList는 null 원소를 허용하므로, poll의 null이 비어 있다는 뜻인지 null 원소를 꺼냈다는 뜻인지 구분할 수 없습니다. '아무 작업도 아님'을 큐에 넣고 싶다면 null 대신 그 뜻을 나타내는 객체를 따로 만들어 넣는 것이 좋습니다.

push·pop으로 스택을, offerLast·pollFirst로 큐를 만듭니다

Deque에는 스택용 이름도 준비되어 있습니다. push(e)는 addFirst(e)와 같고, pop()은 removeFirst()와 같으며, peek()은 peekFirst()와 같습니다. 즉 Deque를 스택으로 쓰면 앞쪽 끝이 스택의 꼭대기(top)가 됩니다. 큐용 메서드 offer(e)와 poll()도 있는데, 각각 offerLast(e), pollFirst()와 같습니다. 다음 코드는 같은 A, B, C를 스택과 큐에 넣고 꺼내 봅니다.

import java.util.ArrayDeque;
import java.util.Deque;

public final class DequeAsStackAndQueue {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();
        stack.push("A");
        stack.push("B");
        stack.push("C");
        System.out.println("stack=" + stack.pop() + stack.pop() + stack.pop());

        Deque<String> queue = new ArrayDeque<>();
        queue.offerLast("A");
        queue.offerLast("B");
        queue.offerLast("C");
        StringBuilder order = new StringBuilder();
        for (String value; (value = queue.pollFirst()) != null; ) {
            order.append(value);
        }
        System.out.println("queue=" + order);
    }
}

stack=CBA
queue=ABC

push는 원소를 앞에 넣으므로, A, B, C를 차례로 넣은 스택을 앞에서부터 읽으면 C, B, A입니다. pop은 앞에서 꺼내므로 C, B, A 순서로 나옵니다. 반면 offerLast로 넣은 큐는 앞에서부터 A, B, C이고, pollFirst가 앞에서 꺼내므로 A, B, C 순서로 나옵니다. 두 경우 모두 앞쪽에서 꺼냈지만, 넣을 때 쓴 끝이 달라서 덱 안의 순서가 달라졌고 그래서 결과도 달라졌습니다.

큐를 비우는 for 문은 pollFirst()가 꺼낸 값을 value에 대입하고, 그 값이 null이 아닌 동안 반복합니다. ArrayDeque에는 null이 들어 있을 수 없으므로, null이 나왔다면 큐가 비었다는 뜻입니다. 그래서 isEmpty()를 따로 확인하지 않고도 반복을 끝낼 수 있습니다.

위 도식은 앞의 잘못된 큐와 이번 예제의 스택, 큐를 나란히 비교합니다. 세 영역은 각각 빈 덱에서 따로 시작하며, 한 영역의 결과가 다음 영역으로 이어지지 않습니다. 넣는 끝과 꺼내는 끝이 같으면 CBA, 다르면 ABC가 됩니다.

변수 타입이 Deque이면 양쪽 끝의 메서드를 모두 호출할 수 있어서, 스택으로 쓰던 덱에 실수로 offerLast를 섞어도 컴파일러가 막지 못합니다. 그래서 스택에는 push, pop, peek만 쓰고 큐에는 offer, poll, peek만 쓰기로 정해 두면 코드의 의도가 잘 드러납니다. 큐로만 쓸 변수라면 타입을 Queue<String> queue = new ArrayDeque<>();처럼 Queue 인터페이스로 선언하는 방법도 있습니다. Queue에는 양쪽 끝을 고르는 메서드가 없으므로 뒤에서 꺼내는 실수를 컴파일러가 막아 줍니다. 반면 Java 표준 라이브러리에는 스택 연산만 모은 인터페이스가 없으므로, 스택은 Deque 타입으로 선언하고 앞의 사용 규칙으로 의도를 지킵니다.

ArrayDeque를 기본 구현으로 쓰는 이유

ArrayDeque는 이름 그대로 배열에 원소를 담는 덱이고, OpenJDK의 구현은 이 배열을 원형 배열(circular array)로 씁니다. 원형 배열은 배열의 끝과 처음이 이어져 있다고 보고, 앞쪽 끝을 가리키는 head와 뒤쪽 끝을 가리키는 tail 위치만 옮기며 원소를 넣고 꺼내는 구조입니다. 앞에 넣을 때 원소를 한 칸씩 밀어낼 필요가 없으므로 양쪽 끝의 연산이 모두 빠릅니다. 배열이 가득 차면 더 큰 배열을 만들어 옮기는데, 동적 배열에서 본 것처럼 이 복사 비용을 모든 연산에 나눠 보면 한 번의 연산은 분할 상환 O(1)입니다. ArrayDeque 문서도 대부분의 연산이 분할 상환 상수 시간에 실행된다고 밝힙니다.

ArrayDeque는 원소의 참조를 배열 칸에 바로 담습니다. 그래서 원소마다 노드 객체를 만들 필요가 없고, 앞뒤 노드를 가리키는 참조도 필요 없습니다. 같은 Deque를 구현한 LinkedList는 양방향 연결 목록이라서 원소를 하나 넣을 때마다 노드 객체를 새로 만들고, 노드마다 앞뒤 참조 두 개를 더 씁니다. 원소가 메모리에 흩어지니 차례로 읽을 때도 배열보다 불리합니다. ArrayDeque의 문서도 스택으로 쓸 때는 Stack보다, 큐로 쓸 때는 LinkedList보다 빠를 가능성이 높다고 소개합니다.

그래서 단순한 스택이나 큐가 필요하면 ArrayDeque를 기본으로 씁니다. LinkedList가 더 나은 경우는 드뭅니다. 반복자로 목록 중간을 지나가면서 원소를 넣고 지워야 하거나, null 원소를 꼭 담아야 하는 정도입니다.

옛 코드에서는 java.util.Stack 클래스를 볼 수 있습니다. Stack은 Java 1.0 시절의 Vector를 상속하는데, 주요 메서드가 synchronized로 동기화되어 있어서 스레드 하나에서 쓸 때도 쓸데없는 비용이 듭니다. 더 큰 문제는 get(0)이나 add(0, e) 같은 인덱스 메서드까지 물려받아서, 스택의 한쪽 끝 규칙을 우회해 아무 위치나 읽고 고칠 수 있다는 점입니다. 게다가 Stack을 출력하면 꼭대기가 맨 뒤에 나오지만 ArrayDeque로 만든 스택은 꼭대기가 맨 앞에 나와서, 두 클래스를 섞어 쓰면 헷갈리기 쉽습니다. Stack의 문서도 Deque와 그 구현 클래스가 더 완전하고 일관된 LIFO 연산을 제공하므로 Stack보다 우선해서 쓰라고 권합니다. 그래서 새 코드에서는 Deque를 스택으로 씁니다.

더 깊이: 원형 배열 안에서 head와 tail이 움직이는 모습

ArrayDeque의 원형 배열이 실제로 어떻게 움직이는지 OpenJDK 21에서 내부 필드를 들여다보며 확인해 보겠습니다. 여기서 설명하는 배열 길이와 확장 규칙은 문서가 약속하는 동작이 아니라 현재 구현의 세부 사항입니다. new ArrayDeque<>(4)로 만든 덱은 길이 5의 배열로 시작하고, head와 tail은 모두 0입니다. tail은 마지막 원소의 다음 칸, 즉 다음 원소가 들어갈 자리를 가리킵니다.

push는 head를 한 칸 왼쪽으로 옮겨 원소를 넣는데, 0번 칸에서 왼쪽으로 가면 배열의 마지막 칸인 4번으로 돌아갑니다. 그래서 A가 4번 칸에 들어갔습니다. offerLast는 tail 자리에 원소를 넣고 tail을 오른쪽으로 옮깁니다. 앞에서부터 읽을 때는 head인 3번 칸에서 출발해 4번, 0번, 1번 칸으로 돌아가며 읽으므로 B, A, C, D가 됩니다. 원소를 하나도 밀어내지 않고 양쪽 끝에 넣었다는 점이 핵심입니다.

이 상태에서 offerLast("E")를 호출하면 E가 2번 칸에 들어가고, tail이 3이 되어 head와 만납니다. 배열이 가득 찼다는 뜻이므로 길이 12인 새 배열로 옮기는데, 늘어난 빈칸이 tail과 head 사이에 오도록 B와 A를 새 배열의 맨 끝인 10번과 11번 칸으로 옮깁니다. 그래서 확장한 뒤에는 head가 10, tail이 3이고, 앞에서부터 읽은 순서는 B, A, C, D, E 그대로입니다. 현재 구현은 배열 길이가 64보다 작으면 길이를 대략 두 배로, 64 이상이면 1.5배로 늘립니다. 실제로 길이 63인 배열은 128로, 길이 64인 배열은 96으로 늘어났습니다. 이 확장이 가끔씩만 일어나기 때문에 연산 하나하나의 평균 비용이 상수로 유지됩니다.

스택으로 괄호의 짝 검사하기

스택이 잘 맞는 대표적인 문제가 괄호 검사입니다. ([]{})처럼 괄호가 올바르게 짝지어져 있는지 확인하려면, 닫는 괄호가 나올 때마다 아직 닫히지 않은 여는 괄호 가운데 가장 최근 것과 짝이 맞는지 보면 됩니다. '가장 최근에 넣은 것을 먼저 꺼낸다'는 스택의 규칙과 정확히 같습니다.

단순히 여는 괄호와 닫는 괄호의 개수만 세면 안 됩니다. ([)]는 소괄호와 대괄호가 각각 한 쌍씩이라 개수는 맞지만, 대괄호가 닫히기 전에 소괄호가 먼저 닫혀서 올바른 중첩이 아닙니다. 순서까지 확인하려면 스택이 필요합니다.

규칙은 세 가지입니다. 여는 괄호는 스택에 push합니다. 닫는 괄호가 나오면 스택에서 하나를 pop해 짝이 맞는지 비교하는데, 스택이 비어 있거나 짝이 다르면 그 즉시 실패입니다. 문자열을 끝까지 읽은 뒤에는 스택이 비어 있어야 하며, 여는 괄호가 남아 있다면 닫히지 않은 괄호가 있다는 뜻입니다.

import java.util.ArrayDeque;
import java.util.Deque;

public final class BracketStackValidator {
    public static void main(String[] args) {
        for (String value : new String[] {"([]{})", "([)]", "(()"}) {
            System.out.println(value + "=" + valid(value));
        }
    }

    private static boolean valid(String text) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : text.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') stack.push(c);
            else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty() || !matches(stack.pop(), c)) return false;
            }
        }
        return stack.isEmpty();
    }

    private static boolean matches(char open, char close) {
        return open == '(' && close == ')'
                || open == '[' && close == ']'
                || open == '{' && close == '}';
    }
}

([]{})=true
([)]=false
(()=false

첫 입력 ([]{})에서는 (와 [를 쌓은 뒤 ]가 [를 꺼내 짝이 맞고, {를 쌓은 뒤 }가 {를 꺼내 짝이 맞습니다. 마지막 )가 처음의 (를 꺼내면 스택이 비므로 true입니다.

두 번째 입력 ([)]는 세 번째 문자에서 실패합니다. 그때 스택의 꼭대기는 [인데 닫는 괄호는 )이므로 matches가 false를 돌려주고, valid는 마지막 ]를 읽지도 않고 바로 false를 반환합니다.

세 번째 입력 (()는 중간에는 실패하지 않습니다. 두 번째 (가 )와 짝을 이룬 뒤 문자열이 끝나는데, 스택에 처음의 (가 남아 있어서 마지막 stack.isEmpty()가 false가 됩니다. 이처럼 실패에는 중간에 짝이 어긋나는 경우와 끝에 여는 괄호가 남는 경우가 있으므로, 테스트할 때도 두 경우를 모두 넣어야 합니다.

조건식의 stack.isEmpty() ||도 빼면 안 됩니다. )(처럼 닫는 괄호로 시작하는 입력에서는 꺼낼 여는 괄호가 없습니다. 이 검사가 없으면 빈 스택에 pop()을 호출하게 되고, pop()은 removeFirst()와 같으므로 false 대신 NoSuchElementException이 납니다. ||는 왼쪽이 true이면 오른쪽을 계산하지 않으므로, 스택이 비어 있으면 pop()까지 가지 않고 바로 실패로 처리됩니다.

이 valid는 괄호가 아닌 문자를 오류로 보지 않고 건너뜁니다. 그래서 a(b[c])는 a, b, c를 무시하고 괄호만 보아 true이고, 괄호가 하나도 없는 빈 문자열도 스택이 빈 채로 끝나므로 true입니다. 괄호의 짝만 볼 뿐 수식의 문법을 검사하거나 문자열·주석 안의 괄호를 따로 처리하지는 않는다는 점도 알아 두세요.

게시글 명령을 큐에 쌓아 차례로 처리하기

이번에는 큐를 써 보겠습니다. 게시판에 들어온 명령을 큐에 넣고, 작업 루프가 앞에서부터 하나씩 꺼내 처리합니다. 명령은 제목과 조회 수를 가진 레코드이고, 컴팩트 생성자에서 잘못된 값을 거부합니다.

import java.util.ArrayDeque;
import java.util.Deque;

public final class BoardCommandQueue {
    public static void main(String[] args) {
        Deque<Command> pending = new ArrayDeque<>();
        pending.offerLast(new Command("array", 40));
        pending.offerLast(new Command("queue", 50));
        int total = 0;
        while (!pending.isEmpty()) {
            Command command = pending.pollFirst();
            System.out.println("run=" + command.title());
            total += command.viewCount();
        }
        System.out.println("total=" + total + ", pending=" + pending.size());
    }

    private record Command(String title, int viewCount) {
        private Command {
            if (title == null || title.isBlank() || viewCount <= 0)
                throw new IllegalArgumentException();
        }
    }
}

run=array
run=queue
total=90, pending=0

offerLast로 뒤에 넣고 pollFirst로 앞에서 꺼냈으므로, 들어온 순서대로 array, queue가 실행됩니다. 두 명령의 조회 수를 더한 total은 40 + 50 = 90이고, 모든 명령을 꺼냈으므로 남은 명령은 0개입니다.

이 예제에서는 명령이 실패하지 않지만, 실제 서비스라면 처리 도중 실패하는 명령을 어떻게 다룰지 정해야 합니다. 큐에서 먼저 꺼내고 처리하다가 실패하면 그 명령은 이미 큐에서 사라진 상태입니다. 그래서 실패한 명령을 큐에 다시 넣을지, 실패 목록에 따로 모을지, 아니면 처리가 끝난 뒤에야 큐에서 지울지를 정해 두어야 합니다. 큐 자체는 꺼낸 원소를 대신 보관해 주지 않으므로, 실패한 명령을 잃지 않게 하는 것은 코드가 맡아야 할 몫입니다. 이 문제는 이 장의 마지막 글인 스택과 큐 활용: 뒤로 가기 이력과 작업 대기열에서 직접 다룹니다.

용량이 정해진 큐에서는 offer의 결과를 확인합니다

ArrayDeque는 문서에 따르면 용량 제한이 없어서, 메모리가 허락하는 한 필요할 때마다 배열을 늘립니다. 하지만 서버의 대기열이 끝없이 커지면 메모리가 바닥나고, 맨 뒤의 요청은 처리될 때까지 한참을 기다리게 됩니다. 그래서 대기열의 크기에 상한을 두기도 하는데, java.util.concurrent 패키지의 ArrayBlockingQueue가 생성할 때 정한 용량을 넘지 않는 큐입니다. 이런 큐가 가득 차면 add는 IllegalStateException을 던지고 offer는 false를 돌려줍니다.

import java.util.concurrent.ArrayBlockingQueue;

public final class BoundedOfferResult {
    public static void main(String[] args) {
        ArrayBlockingQueue<String> pending = new ArrayBlockingQueue<>(2);
        System.out.println("A=" + pending.offer("A"));
        System.out.println("B=" + pending.offer("B"));
        System.out.println("C=" + pending.offer("C"));
        System.out.println("first=" + pending.poll());
        System.out.println("second=" + pending.poll());
        System.out.println("empty=" + pending.poll());
    }
}

A=true
B=true
C=false
first=A
second=B
empty=null

용량이 2이므로 A와 B는 들어가고, 가득 찬 뒤에 넣으려 한 C는 거부되어 false가 나옵니다. C는 큐에 들어갔다가 사라진 것이 아니라 처음부터 저장되지 않았습니다. 그래서 두 번 꺼내면 A와 B만 나오고, 세 번째 poll은 큐가 비어 있으므로 null을 돌려줍니다.

여기서 offer의 반환값을 무시하면 위험합니다. 호출한 쪽은 명령을 맡겼다고 생각하고 사용자에게 '접수되었습니다'라고 응답했는데, 실제로 명령은 어디에도 저장되지 않은 채 사라집니다. 그래서 용량이 정해진 큐에서는 offer가 false를 돌려줬을 때 무엇을 할지 반드시 정해야 합니다. 바로 거절하고 사용자에게 다시 시도하라고 알릴 수도 있고, 정해진 시간만큼 기다렸다가 다시 넣어 볼 수도 있습니다. 요청을 보내는 쪽의 속도를 늦추는 방법도 있습니다.

이 예제는 스레드 하나에서 용량과 반환값만 확인한 것입니다. ArrayBlockingQueue는 원래 여러 스레드가 함께 쓰도록 만든 큐라서, 공간이 생길 때까지 기다리는 put과 원소가 들어올 때까지 기다리는 take 같은 메서드도 있습니다. put은 큐에 자리가 날 때까지 호출한 스레드를 멈춰 세우므로, 요청을 처리하는 스레드에서 무심코 쓰면 그 스레드 전체가 멈춰 버릴 수 있습니다. 이런 블로킹 연산은 BlockingQueue 메서드 고르기: offer·put·poll·take에서 자세히 다룹니다.

여러 스레드가 하나의 큐를 함께 쓸 때는 ArrayDeque가 아니라 스레드 안전한 큐를 써야 합니다. 그리고 if (!queue.isEmpty()) queue.remove();처럼 확인과 동작을 두 번의 호출로 나누면 안 됩니다. 확인한 직후 다른 스레드가 마지막 원소를 가져가면, 비어 있지 않다고 확인했는데도 remove가 예외를 던집니다. size()나 isEmpty()의 결과는 호출한 그 순간의 상태일 뿐이므로, poll()을 한 번 호출하고 그 결과가 null인지로 판단하는 편이 안전합니다. 이 문제는 스레드를 다루는 장에서 경쟁 조건(race condition)이라는 이름으로 다시 만납니다.

정리

• 스택은 나중에 넣은 것을 먼저 꺼내는 LIFO, 큐는 먼저 넣은 것을 먼저 꺼내는 FIFO입니다. 같은 끝에서 넣고 꺼내면 스택, 서로 다른 끝에서 넣고 꺼내면 큐가 됩니다.
• Deque는 양쪽 끝에서 넣고 꺼낼 수 있습니다. 스택으로 쓸 때는 앞쪽 끝만 쓰는 push, pop, peek을 쓰고, 큐로 쓸 때는 뒤에 넣고 앞에서 꺼내는 offer, poll, peek을 씁니다.
• add·remove·get 계열은 실패하면 예외를 던지고, offer·poll·peek 계열은 false나 null을 돌려줍니다. 비어 있는 상태가 정상이면 특별한 값을 돌려주는 쪽을 씁니다.
• ArrayDeque는 원형 배열로 양쪽 끝 연산을 분할 상환 O(1)에 처리하고 null 원소를 받지 않습니다. 단순한 스택이나 큐에는 Stack이나 LinkedList보다 ArrayDeque가 기본 선택입니다.
• 괄호 검사는 여는 괄호를 쌓고, 닫는 괄호에서 꺼내 비교하고, 끝에 스택이 비었는지 확인하는 세 단계로 이루어집니다.
• 용량이 정해진 큐에서는 offer가 false를 돌려줄 수 있으므로, 거부된 원소를 어떻게 처리할지 정해야 합니다.

연습 문제

1. 다음 코드의 세 출력 줄을 예상하세요. 각 연산 뒤에 덱 안의 순서를 앞에서부터 적어 보면 쉽게 풀 수 있습니다.

import java.util.ArrayDeque;
import java.util.Deque;

public final class DequeTraceExercise {
    public static void main(String[] args) {
        Deque<Integer> deque = new ArrayDeque<>();
        deque.offerLast(1);
        deque.push(2);
        deque.offerLast(3);
        deque.push(4);
        System.out.println(deque);
        System.out.println(deque.pop() + " " + deque.pollLast() + " " + deque.peek());
        System.out.println(deque);
    }
}

2. 최근에 본 게시글 제목을 최대 3개까지 보관하는 기능을 ArrayDeque로 만드세요. 새 제목은 앞에 넣고, 4개가 되면 가장 오래된 뒤쪽 제목을 버립니다. 이미 목록에 있는 제목을 다시 보면 기존 위치에서 지우고 맨 앞으로 옮깁니다. 입력이 array, hash, map, hash, queue 순서일 때, 각 입력 뒤의 목록을 최신부터 오래된 순서로 적어 보세요.
3. BracketStackValidator의 조건식에서 stack.isEmpty() ||를 지우면 )(를 검사할 때 무슨 일이 생기는지 설명하세요. pop() 대신 pollFirst()를 쓰면 이 검사 없이도 안전하게 고칠 수 있는지도 생각해 보세요.

[4, 2, 1, 3]
4 3 2
[2, 1]

import java.util.ArrayDeque;
import java.util.Deque;

public final class RecentTitlesDequeSolution {
    public static void main(String[] args) {
        Deque<String> recent = new ArrayDeque<>();
        for (String title : new String[] {"array", "hash", "map", "hash", "queue"})
            add(recent, title, 3);
        System.out.println(recent);
    }

    private static void add(Deque<String> recent, String title, int limit) {
        recent.remove(title);
        recent.addFirst(title);
        if (recent.size() > limit) recent.removeLast();
    }
}

[queue, hash, map]

다음 글

Map 활용: 중복 키 처리와 merge·compute에서는 다시 맵으로 돌아가, 단어 빈도 세기와 회원 저장소 같은 작은 문제들을 풉니다. 같은 키가 다시 들어왔을 때 값을 합칠지, 처음 값을 지킬지, 오류로 볼지를 정하고, 그에 맞춰 put, putIfAbsent, merge, computeIfAbsent, compute 가운데 알맞은 메서드를 고르는 연습을 합니다.