5.1 큐 추상 데이터 타입

정의

선입선출(First-In, First-Out; FIFO) 방식으로 데이터를 저장하고 꺼내는 자료구조
큐에서 삽입이 일어나는 곳은 후단(rear), 삭제가 일어나는 곳은 전단(front)

연산

객체: 0개 이상의 원소를 가지는 유한 선형 리스트
연산:
  create(max_size) ::=
  	최대 크기가 max_size인 공백 큐를 생성한다.
  init(q) ::=
  	큐를 초기화한다.
  is_full(q) ::=
    if(size == max_size) return TRUE;
    else return FALSE;
  is_empty(q) ::=
    if(size == 0) return TRUE;
    else return FALSE;
  enqueue(q, e) ::=
  	if( is_full(q) ) queue_full 오류;
    else q의 끝에 e를 추가한다.
  dequeue(q) ::=
    if( is_empty(q) ) queue_empty 오류;
    else q의 맨 앞에 있는 q를 제거하여 반환한다.
  peek(q) ::=
    if( is_empty(q) ) queue_empty 오류;
    else q의 맨 앞에 있는 e를 읽어서 반환한다.

5.2 선형큐(Linear queue)

배열 기반

public class ArrayLinearQueue<T> {
    T[] data;
    private int front;		// 삽입이 일어나는 인덱스 (0-based)
    private int rear;		// 삭제가 일어나는 인덱스 (0-based)
    private int maxSize;	// 현재 배열의 최대 크기
    
    // create(maxSize): 최대 크기가 maxSize인 공백 선형큐 생성
    public ArrayLinearQueue(int maxSize) {
        @SuppressWarnings("unchecked")
        T[] temp = (T[]) new Object[maxSize];
    	this.front = -1;	// 공백 큐
        this.rear = -1;		// 공백 큐
        this.maxSize = maxSize;
    }
    
    // is_full: 큐가 가득 찼는지
    public boolean is_full() {
    	return this.rear == maxSize - 1;
    }

    // is_empty: 큐가 비었는지
    public boolean is_empty() {
    	return this.front == this.rear;
    }
    
    // enqueue: (큐가 가득 차면 2배로 확장 후) rear에 item 추가 
    public int enqueue(T item) {
    	if (is_full()) {
        	int newSize = maxSize * 2;
            @SuppressWarnings("unchecked")
            T[] newData = (T[]) new Object[newSize];
            System.arraycopy(data, 0, newData, 0, maxSize);
            data = newData;
            maxSize = newSize;
        }
        data[++rear] = item;
        return 0;	// 정상 종료 (0 반환
    }

    // dequeue: 큐가 비어 있으면 예외, 아니면 front의 item 제거·반환
    public T dequeue(T item) {
    	if (is_empty()) {
            throw new NoSuchElementException("큐가 비었습니다!");
        }
        return data[++front];
    }
    
    // peek: 큐가 비어 있으면 예외, 아니면 front의 item을 제거하지 않고 반환
    public T peek() {
        if (is_empty()) {
            throw new NoSuchElementException("큐가 비었습니다!");
        }
        return data[front + 1];
    }

	// 현재 큐에 들어 있는 item 개수
    public int size() {
        return Math.max(0, rear - front);
    }
    
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
    	for (int i = 0; i < maxSize; i++) {
        	if (i <= front || i > rear) {
                sb.append(" | ");
            } else {
                sb.append(data[i]).append(" | ");
            }
        }
        return sb.toString();
    }
}

public class QueueTest {
    public static void main(String[] args) {
        ArrayLinearQueue<Integer> q = new ArrayLinearQueue<>(2);

        System.out.println(q.enqueue(10)); // 0
        System.out.println(q.enqueue(20)); // 0
        System.out.println(q.enqueue(30)); // 크기 2 → 4로 확장, 0

        System.out.println(q); // toString() 호출 → 큐 상태 출력

        System.out.println(q.peek()); // 10
        System.out.println(q.dequeue()); // 10
        System.out.println(q.dequeue()); // 20
        System.out.println(q.dequeue()); // 30
        System.out.println(q.dequeue()); // NoSuchElementException("큐가 비었습니다!")
    }
}

java.util.List 기반

import java.util.*;

public class ListQueue {
    public static void main(String[] args) {
        // create(): 공백 큐 생성 (크기 무관)
        List<String> queue = new ArrayList<>();

        // is_full: 없음 (자동 확장)

        // is_empty
        System.out.println(queue.isEmpty()); // true

        // enqueue 연산 (rear에 추가)
        queue.add("A");
        queue.add("B");
        queue.add("C");

        // peek 연산 (front 값 반환)
        System.out.println(queue.get(0)); // A

        // dequeue 연산 (front 값 제거 및 반환) -> O(n)
        System.out.println(queue.remove(0)); // A
        System.out.println(queue.remove(0)); // B
        System.out.println(queue.remove(0)); // C

        // size 연산 (큐에 들어 있는 원소 개수)
        System.out.println(queue.size()); // 0

        // 비어 있을 때 dequeue 또는 peek: 예외 발생
        try {
            System.out.println(queue.remove(0));
        } catch (IndexOutOfBoundsException e) {
            System.out.println("IndexOutOfBoundsException: 큐가 비었습니다!");
        }

        try {
            System.out.println(queue.get(0));
        } catch (IndexOutOfBoundsException e) {
            System.out.println("IndexOutOfBoundsException: 큐가 비었습니다!");
        }
    }
}

java.util.Queue 기반

import java.util.*;

public class LinkedListQueue {
    public static void main(String[] args) {
        // create(): 공백 큐 생성
        Queue<String> queue = new LinkedList<>();

        // is_full: 없음 (자동 확장)

        // is_empty
        System.out.println(queue.isEmpty()); // true

        // enqueue 연산 (rear 값 추가, offer 또는 add 사용)
        queue.offer("A");
        queue.offer("B");
        queue.offer("C");

        // peek 연산 (front 값 반환, 비어 있으면 null)
        System.out.println(queue.peek()); // A

        // dequeue 연산 (front 제거 및 반환, 비어 있으면 null)
        System.out.println(queue.poll()); // A
        System.out.println(queue.poll()); // B
        System.out.println(queue.poll()); // C
        
        // size 연산 (큐에 들어 있는 원소 개수)
        System.out.println(queue.size()); // 0

        // 비어 있을 때 dequeue: null 반환
        System.out.println(queue.poll()); // null

        // 비어 있을 때 peek: null 반환
        System.out.println(queue.peek()); // null

        // 예외 발생 버전 (remove/element)
        try {
            queue.remove(); // 예외 발생
        } catch (NoSuchElementException e) {
            System.out.println("NoSuchElementException: 큐가 비었습니다!");
        }

        try {
            queue.element(); // 예외 발생
        } catch (NoSuchElementException e) {
            System.out.println("NoSuchElementException: 큐가 비었습니다!");
        }
    }
}

메서드	설명	비었을 때
offer(E e)	큐에 삽입 (add도 가능하나 예외 발생 가능)	false 반환
poll()	앞에서 제거하고 반환	null 반환
peek()	앞을 반환 (제거 안 함)	null 반환
remove()	앞에서 제거하고 반환	예외 발생
element()	앞을 반환 (제거 안 함)	예외 발생

java.util.Deque 기반

import java.util.*;

public class DequeQueue {
    public static void main(String[] args) {
        // create(): 공백 큐 생성
        Deque<String> queue = new ArrayDeque<>();

        // is_full: 없음 (자동 확장)

        // is_empty
        System.out.println(queue.isEmpty()); // true

        // enqueue 연산 (rear에 추가)
        queue.offerLast("A");
        queue.offerLast("B");
        queue.offerLast("C");

        // peek 연산 (front 값 확인)
        System.out.println(queue.peekFirst()); // A

        // dequeue 연산 (front 제거 및 반환)
        System.out.println(queue.pollFirst()); // A
        System.out.println(queue.pollFirst()); // B
        System.out.println(queue.pollFirst()); // C

        // size 연산
        System.out.println(queue.size()); // 0

        // 비어 있을 때 dequeue: null 반환
        System.out.println(queue.pollFirst()); // null

        // 비어 있을 때 peek: null 반환
        System.out.println(queue.peekFirst()); // null

        // 예외 발생 버전
        try {
            queue.removeFirst(); // 예외 발생
        } catch (NoSuchElementException e) {
            System.out.println("NoSuchElementException: 큐가 비었습니다!");
        }

        try {
            queue.getFirst(); // 예외 발생
        } catch (NoSuchElementException e) {
            System.out.println("NoSuchElementException: 큐가 비었습니다!");
        }
    }
}

기능	Deque 메서드	비었을 때
enqueue (rear)	offerLast(e) / addLast(e)	false / 예외
peek (front)	peekFirst() / getFirst()	null / 예외
dequeue (front)	pollFirst() / removeFirst()	null / 예외

비교

구현체	자동 확장	스레드 안전성	특징 / 용도
Array	❌	❌	고정 크기, 학습용 (직접 인덱싱 및 사이즈 관리 필요)
ArrayList / List	✅	❌	간단한 선형 큐 구현 가능 (add / remove(0) 사용, O(n) 제거 비용)
LinkedList (Queue)	✅	❌	Queue 인터페이스 구현, offer / poll / peek 사용 가능
ArrayDeque (Deque)	✅	❌	가장 권장되는 큐 구현체, offerLast / pollFirst로 FIFO 구현
ConcurrentLinkedQueue	✅	✅ (비동기)	멀티스레드 환경에서 빠른 비차단 큐
LinkedBlockingQueue, ArrayBlockingQueue	✅	✅ (동기화)	작업 큐, 생산자-소비자 패턴에 최적화됨, 용량 지정 가능

5.5 덱(deque)이란?

정의

double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐

java.util.Deque 기반

방향	삽입용	조회용	삭제용
앞	addFirst / offerFirst	peekFirst / getFirst	pollFirst / removeFirst
뒤	addLast / offerLast	peekLast / getLast	pollLast / removeLast

✅ LinkedList vs ArrayDeque 시간 복잡도 비교표

연산 종류	LinkedList	ArrayDeque	설명
addFirst(e)	O(1)	O(1) 암시적	앞에 삽입 (스택 push용)
addLast(e)	O(1)	O(1) 암시적	뒤에 삽입 (큐 enqueue용)
removeFirst()	O(1)	O(1) 암시적	앞에서 제거 (큐 dequeue)
removeLast()	O(1)	O(1) 암시적	뒤에서 제거 (스택 pop)
peekFirst()	O(1)	O(1)	앞 요소 조회
peekLast()	O(1)	O(1)	뒤 요소 조회
get(index)	O(n)	❌ 미지원 (NoSuchMethodError)	임의 접근 불가
내부 구조	이중 연결 리스트	원형 배열 (resizable array)	구조적 차이

✅ 추가 설명

🔷 LinkedList

• 노드 기반 이중 연결 리스트
• 삽입/삭제는 O(1)이지만, 인덱스 기반 접근은 O(n)
• 더 많은 객체 생성(노드) → GC 비용 증가

🔶 ArrayDeque

• 내부적으로 원형 배열 사용
• front와 rear 포인터로 빠르게 이동
• 필요 시 자동으로 배열 확장 (확장은 O(n), 하지만 amortized O(1))
• 더 빠르고 메모리 효율적

ArrayDeque 메서드

✅ 1. 삽입 (Insertion)

위치	안전 버전 (false 반환)	예외 버전 (예외 발생)
앞	offerFirst(e)	addFirst(e)
뒤	offerLast(e) / offer(e)	addLast(e) / add(e)

✅ 2. 삭제 (Removal)

위치	안전 버전 (null 반환)	예외 버전 (예외 발생)
앞	pollFirst() / poll()	removeFirst() / remove()
뒤	pollLast()	removeLast()

✅ 3. 조회 (Access / Peek)

위치	안전 버전 (null 반환)	예외 버전 (예외 발생)
앞	peekFirst() / peek()	getFirst() / element()
뒤	peekLast()	getLast()

✅ 4. 스택 연산 (LIFO)

기능	메서드
push	push(e) → addFirst(e)
pop	pop() → removeFirst()
peek	peek() → peekFirst()

✅ 5. 큐 연산 (FIFO)

기능	메서드
삽입	offer(e) = offerLast(e)
삭제	poll() = pollFirst()
조회	peek() = peekFirst()

✅ 참고 요약

• offer, poll, peek 계열 → 실패 시 null 또는 false, 안전
• add, remove, get, push, pop 계열 → 실패 시 예외 발생