1. 큐(Queue)

• 선입선출(FIFO; First-In, First-Out) 구조의 자료구조
  : 가장 먼저 저장된 데이터부터 가장 먼저 꺼내는 방식의 자료구조
• 일반적으로 연결 리스트를 사용하여 구현
  : 항상 첫번째 데이터부터 삭제하므로, 배열에서는 삭제로 인해 생긴 빈 공간을 채우는 추가작업이 요구되지만 연결 리스트에서는 삭제할 노드의 앞뒤 노드의 연결만 바꾸면 되기 때문
• 다음과 같은 기능을 구현할 때 활용
  : 최근 사용 문서, 인쇄작업 대기열, 버퍼 등

---

2. 큐 구현

• 전체 구현 코드는 여기에서 확인 가능

큐의 주요 기능 정의

Queue 인터페이스

package datastructure.queue;

public interface Queue<E> {

    boolean isEmpty();  // 큐가 비어있는지를 확인
    void enqueue(E e);  // 큐에 데이터를 저장
    E dequeue();        // 큐에서 데이터를 삭제
    E peek();           // 큐의 맨 앞에 저장된 데이터를 반환

    void clear();       // 큐에 저장된 모든 데이터 삭제
    int getSize();      // 큐에 저장된 데이터의 개수 반환
    void dump();        // 큐에 저장된 모든 데이터 출력
}

배열을 사용한 큐 구현

ArrayBaseQueue 클래스

package datastructure.queue;

import java.util.Arrays;

public class ArrayBaseQueue<E> implements Queue<E> {

    private static final int DEFAULT_CAPACITY = 11;     // 큐의 최대 용량의 초기값

    private final Object[] elements;    // 데이터를 저장할 배열
    private final int max;

    private int front;      // 큐의 첫번째 데이터가 되는 인덱스 번호
    private int rear;       // 큐의 마지막 데이터가 되는 인덱스 번호
    private int size;       // 큐에 저장된 데이터의 개수 = 큐의 길이

    // 배열 기반 큐 생성
    public ArrayBaseQueue() {
        this(DEFAULT_CAPACITY);
    }
    public ArrayBaseQueue(int capacity) {
        // 1. 큐의 front, rear에 해당하는 인덱스 번호와 최대 용량, 저장된 데이터의 개수를 0으로 초기화
        size = front = rear = 0;

        // 2. 큐의 최대 용량 초기화
        max = capacity;

        // 3. 최대 용량만큼의 길이를 갖는 배열 생성
        elements = new Object[capacity];
    }

    // 현재 큐가 빈 큐가 되는 조건
    @Override
    public boolean isEmpty() {
        return size <= 0;
    }

    // 가득 찬 큐가 되는 조건
    // 배열 기반 큐에서만 사용 가능한 메서드
    public boolean isFull() {
        return size >= max;
    }

    @Override
    public void enqueue(E e) {
        if (!isFull()) {
            // 1. 큐에 데이터를 저장 가능한 경우 큐의 꼬리에 해당되는 인덱스에 데이터를 저장
            // 2. 데이터 저장 후 꼬리에 해당되는 인덱스는 1 증가
            elements[rear++] = e;

            // 3. 큐의 길이가 1 증가
            size++;

            // 4. 큐의 마지막 데이터가 배열의 마지막 인덱스에 저장된 경우 다음에 데이터를 추가할 인덱스는 0번으로 조정
            // (구현한 배열 기반 큐는 원형 배열 리스트: 배열에서의 enqueue, dequeue의 효율성을 높이기 위함)
            if (rear == max) {
                rear = 0;
            }
        }
    }

    @Override
    public E dequeue() {
        // 1-1. 빈 큐일 경우 null을 반환
        if (isEmpty()) {
            return null;
        }

        // 1-2. 큐의 머리에 해당되는 인덱스를 1 증가시켜 첫번째 데이터를 큐에서 삭제
        // 이 메서드를 호출할 예제 코드에서는 큐 객체 생성 이후 별도의 형변환을 수행하지 않음
        @SuppressWarnings("unchecked")
        E data = (E) elements[front++];

        // 2. 큐의 길이는 1 감소
        size--;

        // 3. 큐의 첫번째 데이터가 배열의 마지막 인덱스인 경우, 큐의 두번째 데이터가 0번 인덱스가 되도록 조정
        if (front == max) {
            front = 0;
        }
        // 4. 삭제한 데이터를 반환
        return data;
    }

    @Override
    public E peek() {
        // 빈 큐일 경우 null을 반환
        if (isEmpty()) {
            return null;
        }

        // 큐의 첫번째 데이터를 반환
        // 이 메서드를 호출할 예제 코드에서는 형변환을 수행하지 않음
        @SuppressWarnings("unchecked")
        E data = (E) elements[front];
        return data;
    }

    @Override
    public void clear() {
        // 큐에 저장된 데이터를 모두 삭제
        Arrays.fill(elements, null);
        // 큐의 첫번째/마지막 데이터의 인덱스, 큐의 길이를 0으로 초기화
        size = front = rear = 0;
    }

    // 큐에 저장된 데이터의 개수를 반환(데이터의 길이 != 큐의 최대 용량)
    @Override
    public int getSize() {
        return size;
    }

    // 큐의 기능을 수행하는 배열의 길이를 반환
    // 배열 기반 큐에서만 사용 가능한 기능
    public int getCapacity() {
        return max;
    }

    @Override
    public void dump() {
        // 빈 큐인 경우
        if (isEmpty()) {
            System.out.println("Queue is empty!!");
            return;
        }
        // 큐에 저장된 데이터를 저장된 순서대로 모두 출력
        for (int i = 0; i < size; i++) {
            System.out.print(elements[(i + front) % max] + " ");
        }
        System.out.println();
    }
}

실행용 코드 및 실행 결과

package datastructure.queue;

public class ArrayBaseQueueMain {

    public static void main(String[] args) {
        // 배열 기반 큐 생성
        // ArrayBaseQueue의 고유 기능도 활용하기 위해 Queue로 업캐스팅하지 않고 실행
        ArrayBaseQueue<Integer> queue = new ArrayBaseQueue<>(6);

        // 큐가 꽉 찬 상태가 되도록 정수 데이터를 추가
        for (int i = 1; i <= 6; i++) {
            queue.enqueue(i);
        }

        // 큐의 최대 용량, 저장된 데이터의 수, 저장된 데이터, 큐의 포화 여부 출력
        System.out.printf("Queue capacity: %d, length: %d\n", queue.getCapacity(), queue.getSize());
        queue.dump();
        if (queue.isFull()) {
            System.out.println("Queue is full!!");
        }
        System.out.println();

        // 큐에 저장된 데이터를 1개씩 삭제
        System.out.println("Removing data from queue...");
        while (!queue.isEmpty()) {
            System.out.printf("first data: %d, Queue size: %d\n", queue.peek(), queue.getSize());
            queue.dequeue();
        }
        System.out.println();

        // 모든 데이터 삭제 후 빈 큐가 되었는지 확인
        System.out.printf("Queue capacity: %d, length: %d\n", queue.getCapacity(), queue.getSize());
        queue.dump();
        System.out.println();


        // 동일한 데이터를 큐에 저장한 후, 저장된 데이터를 모두 삭제
        for (int i = 1; i <= 6; i++) {
            queue.enqueue(i);
        }
        System.out.printf("Queue capacity: %d, length: %d\n", queue.getCapacity(), queue.getSize());
        queue.dump();
        if (queue.isFull()) {
            System.out.println("Queue is full!!");
        }
        System.out.println();

        // 데이터를 모두 삭제
        System.out.println("Clearing queue...");
        queue.clear();
        System.out.printf("Queue capacity: %d, length: %d\n", queue.getCapacity(), queue.getSize());
        queue.dump();
    }
}

---

연결리스트를 사용한 큐 구현

LinkedListBaseQueue 클래스

package datastructure.queue;

import datastructure.util.Node2;

public class LinkedListBaseQueue<E> implements Queue<E> {

    // 덱 구현에서도 활용하기 위해 이중 연결 리스트로 구현
    private Node2<E> head;  // 큐의 첫번째 노드를 가리키는 변수
    private Node2<E> tail;  // 큐의 마지막 노드를 가리키는 변수
    private int size;       // 큐에 저장된 데이터의 개수 = 큐의 길이

    public LinkedListBaseQueue() {
        head = tail = null;
    }

    // 빈 큐가 되는 조건
    @Override
    public boolean isEmpty() {
        return head == null;
    }

    @Override
    public void enqueue(E e) {
        // 1. 새로운 데이터를 저장할 노드 생성
        Node2<E> newNode = new Node2<>(e, tail, null);
        
        if (isEmpty()) {
            // 2-1. 빈 큐인 경우 새로운 데이터는 첫번째 노드
            head = newNode;
        } else {
            // 2-2. 빈 큐가 아니면 새로운 노드는 기존의 마지막 노드의 바로 다음 위치에 저장
            tail.setNext(newNode);
        }
        // 3. 큐의 꼬리 노드를 새로 추가된 노드로 갱신
        tail = newNode;
        
        // 4. 큐의 길이 1 증가
        size++;
    }

    @Override
    public E dequeue() {
        if (!isEmpty()) {
            // 1. 저장된 노드가 존재하면 삭제할 데이터를 별도로 저장
            E removedData = head.getData();
            
            // 2. 큐의 머리 노드를 두번째 노드로 갱신하여 기존의 첫번째 노드와 큐 간의 연결을 해제
            head = head.getNext();
            
            // 3. 큐의 길이는 1 감소
            size--;
            
            // 4. 삭제된 데이터를 반환
            return removedData;
        }
        return null;
    }

    @Override
    public E peek() {
        // 큐의 첫번째 노드에 저장된 데이터를 반환(빈 큐면 null 반환)
        return isEmpty() ? null : head.getData();
    }

    @Override
    public void clear() {
        // 큐에 저장된 모든 노드를 제거
        while (!isEmpty()) {
            dequeue();
        }
    }

    // 현재 큐에 저장된 노드의 개수를 반환
    @Override
    public int getSize() {
        return size;
    }

    
    // 큐에 저장된 모든 데이터를 출력
    @Override
    public void dump() {
        if (isEmpty()) {
            System.out.println("Empty queue!");
            return;
        }
        Node2<E> ptr = head;
        while (ptr != null) {
            System.out.print(ptr.getData() + " ");
            ptr = ptr.getNext();
        }
        System.out.println();
    }
}

실행용 코드 및 실행 결과

package datastructure.queue;

public class LinkedListBaseQueueMain {

    public static void main(String[] args) {
        Queue<Integer> queue = new LinkedListBaseQueue<>();

        // 연결리스트 기반 큐에 1~5의 정수를 저장
        for (int i = 1; i <= 5; i++) {
            queue.enqueue(i);
        }

        // 데이터 추가 후 큐의 길이, 저장된 데이터 출력
        System.out.printf("Queue length: %d\n", queue.getSize());
        queue.dump();
        System.out.println();

        // 큐에 저장된 데이터를 1개씩 제거
        System.out.println("Removing data from queue:");
        while (!queue.isEmpty()) {
            System.out.printf("first data: %d, Queue length: %d\n", queue.peek(), queue.getSize());
            queue.dequeue();
        }
        System.out.println();

        // 현재 큐가 빈 큐인지 확인
        System.out.printf("Queue length: %d\n", queue.getSize());
        queue.dump();
        System.out.println();

        // 동일한 데이터를 큐에 추가한 후 큐에 저장된 데이터를 모두 삭제
        for (int i = 1; i <= 5; i++) {
            queue.enqueue(i);
        }
        System.out.printf("Queue length: %d\n", queue.getSize());
        queue.dump();
        System.out.println();

        System.out.println("Clearing data from queue:");
        queue.clear();
        System.out.printf("Queue length: %d\n", queue.getSize());
        queue.dump();
    }
}

---

3. Java 언어에서의 큐

• Java에서는 큐 자료구조에 관한 별도의 클래스를 제공하는 대신,
  java.util.Queue 인터페이스에서 큐의 기능을 정의하고
  컬렉션 객체(주로 java.util.LinkedList)에서 그 구체적인 기능을 구현
• java.util.LinkedList, java.util.ArrayDeque 등의 컬렉션 클래스 인스턴스를 java.util.Queue 인터페이스 타입 참조변수로 업캐스팅하는 방식으로 사용

실제 사용 예시

Queue<Integer> queueExample1 = new LinkedList<>();	// 연결리스트 기반 큐 사용 시
Queue<Integer> queueExample2 = new ArrayDeque();	// 배열 기반 큐 사용 시

ps) java.util.ArrayDeque의 주요 메서드는 덱에 관한 내용을 정리할 때 주로 다룰 예정

---

Reference

• Do-it! 자료구조와 함께 배우는 알고리즘 입문(Bohyoh Shibata 지음, 강민 옮김)
• 윤성우의 열혈 자료구조(윤성우 지음)
• 자바의 정석 3판(남궁성 지음)