Stack·Queue·Deque

Stack은 마지막에 넣은 값을 먼저 꺼내고, Queue는 먼저 넣은 값을 먼저 꺼냅니다.

두 추상 자료형은 저장 구현 이름이 아니라 허용 연산과 제거 순서로 정의됩니다.

Java의 Deque는 양끝 추가·조회·삭제를 제공해 Stack과 Queue를 모두 표현합니다.

remove 방향과 자료구조

작업 A, B, C를 순서대로 enqueue한 뒤 뒤에서 제거하면 C, B, A가 나옵니다.

이름은 큐여도 실제 행동은 LIFO입니다.

lab/WrongQueueEndBug.java

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와 반대입니다.

FIFO는 뒤에 offerLast하고 앞에서 pollFirst해야 합니다.

LIFO는 같은 끝에 push와 pop을 적용합니다.

예외형 메서드와 특별값형 메서드 구분

Deque는 add/remove/get처럼 실패 시 예외를 던지는 메서드와 offer/poll/peek처럼 false 또는 null을 반환하는 메서드를 제공합니다.

빈 큐가 정상적인 “할 일 없음” 상태라면 poll이 자연스럽고, 비어 있으면 프로그램 결함이라면 remove로 즉시 실패시킬 수 있습니다.

ArrayDeque는 null을 허용하지 않으므로 poll의 null이 비어 있음을 명확히 뜻합니다.

null 작업 자체를 저장해야 한다는 설계는 부재 표현과 충돌하므로 값 객체로 의미를 명시하는 편이 낫습니다.

src/DequeAsStackAndQueue.java

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입니다.

변수 타입을 Deque로 두면 양끝 메서드가 모두 보이므로 팀 규칙으로 스택에서는 push/pop/peek, 큐에서는 offer/poll/peek만 사용해 의도를 유지합니다.

ArrayDeque와 LinkedList

ArrayDeque는 원형 배열을 사용해 양끝 연산을 상환 O(1)로 제공합니다.

연속 저장이라 Node 객체와 prev·next 참조가 없고 순회 지역성도 좋습니다.

일반 Stack·Queue에는 ArrayDeque가 기본 선택입니다.

LinkedList도 Deque를 구현하지만 원소마다 Node 할당과 두 참조 비용이 있습니다.

반복자로 중간 Node를 직접 수정해야 하는 드문 요구가 아니라면 구조 복잡도를 지불할 이유가 적습니다.

용량 상한과 블로킹 동시성 요구는 ArrayBlockingQueue 같은 다른 구현을 검토합니다.

레거시 Stack 클래스는 Vector를 상속해 불필요한 index 연산과 동기화 규칙을 함께 노출합니다.

새 코드에서는 Deque를 스택 역할로 사용합니다.

괄호 검사와 Stack 상태 기계

여는 괄호를 push하고 닫는 괄호에서 top과 짝을 비교합니다.

중간에 맞지 않거나 마지막에 스택이 비지 않으면 실패입니다.

단순 개수만 세면 ([)]처럼 개수는 맞지만 순서가 틀린 입력을 통과시킵니다.

src/BracketStackValidator.java

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 == '}';
    }
}

게시글 저장소 명령 큐의 처리 전후 상태 분리

입력 명령을 Queue에 넣고 작업자가 앞에서 하나씩 꺼냅니다.

처리 실패 시 재시도 정책이 없다면 제거 전에 실행할지, 제거 뒤 실패 항목을 별도 큐에 넣을지 결정해야 합니다.

자료 구조만으로 전달 보장 의미가 자동 생기지 않습니다.

app/BoardCommandQueue.java

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();
        }
    }
}

제한 큐의 offer 결과

ArrayDeque는 필요할 때 내부 배열을 확장하지만, 서버의 대기열은 메모리와 지연 상한을 위해 고정 용량이 필요할 수 있습니다.

ArrayBlockingQueue 같은 제한 Queue에서 add는 가득 차면 예외를 던지고 offer는 false를 반환합니다.

호출자가 false를 무시하면 명령이 처리될 것처럼 응답하고 실제로는 사라지는 문제가 생깁니다.

대기열 포화 정책은 즉시 거부, 일정 시간 대기, 생산자 속도 제한, 디스크 저장 중 하나로 정해야 합니다.

put은 공간이 날 때까지 기다리므로 요청 스레드 전체를 막을 수 있습니다.

단일 스레드 게시글 예제에서도 offer 결과를 출력해 어느 작업이 Queue 소유권으로 넘어갔는지 확인하는 습관을 들입니다.

Deque의 size()는 순간 관찰값이며 동시 환경에서 다음 연산 성공을 보장하지 않습니다.

if (!queue.isEmpty()) queue.remove()처럼 검사와 동작을 나누지 말고 poll 결과를 기준으로 처리합니다.

이 원칙은 이후 스레드 장의 경합 조건과 연결됩니다.

연습 문제

최근 제목을 앞에 추가하고 최대 3개만 보관하세요.

네 번째 입력이 오면 가장 오래된 뒤쪽 원소를 제거합니다.

같은 제목 재입력은 기존 위치를 지우고 앞으로 옮깁니다.

정답과 해설

remove(값)는 기존 중복을 지우고 addFirst는 최신 위치를 만듭니다.

size가 제한을 넘을 때 removeLast로 오래된 값을 버립니다.

exercise/RecentTitlesDequeSolution.java

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();
    }
}

최종 순서는 큐, 해시, map입니다.

배열은 용량 초과로 제거되고 해시는 중복 없이 최신 위치로 이동합니다.

Stack과 Queue를 구분하는 가장 안전한 방법은 넣는 끝과 빼는 끝을 문장으로 먼저 쓰는 것입니다.

ArrayDeque가 기본 구현이어도 API 방향을 틀리면 자료 구조의 의미가 반대로 바뀝니다.