큐(Queue)

큐는 스택과 마찬가지로 데이터를 일시적으로 쌓아 놓는 자료구조이다.

하지만 스택과 다른 점이 있다.
가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출(First In First Out)이라는 부분이다.

생활 속에서 볼 수 있는 예로는 은행 번호표 받고 대기하기, 마트 계산대에서 줄서기 등이 있다.

큐에 데이터를 넣는 작업을 인큐(en-queue)라고 하고, 꺼내는 작업을 디큐(de-queue)라고 한다.

입력 순서대로 데이터 처리가 필요할 때 사용한다.

---

시간복잡도

큐(Queue)의 시간 복잡도는 큐의 구현 방식에 따라 다르다.
일반적으로 큐는 배열(Array)이나 연결 리스트(Linked List)로 구현된다.

배열(Array)로 구현된 큐의 경우, 삽입(Enqueue)과 삭제(Dequeue) 모두 O(1)의 시간 복잡도를 가진다. 이는 배열의 크기를 변경하지 않고 인덱스만 조작하면 되기 때문이다. 하지만 큐의 경우에는 이러한 연속적인 인덱스를 유지하기 위해 데이터의 이동이 필요할 수도 있다. 이 경우, 데이터의 이동에 따라 시간 복잡도는 최악의 경우 O(n)이 될 수 있다.

연결 리스트(Linked List)로 구현된 큐의 경우, 삽입(Enqueue)과 삭제(Dequeue) 모두 O(1)의 시간 복잡도를 가진다. 이는 연결 리스트에서 새로운 노드를 추가하거나 삭제할 때에는 해당 노드만 조작하면 되기 때문이다. 따라서 큐의 경우 연결 리스트를 이용하여 구현하는 것이 일반적으로 더 효율적이다.

따라서 큐의 시간 복잡도는 큐의 구현 방식에 따라 다르지만,
일반적으로 삽입과 삭제 모두 O(1)의 시간 복잡도를 가지고 있다.

---

링 버퍼 (Ring Buffer)로 큐 만들기

링 버퍼 자료구조를 사용하면 배열 요소를 앞쪽으로 옮기지 않아도 된다.
링 버퍼를 사용하여 큐(Queue)를 구현할 경우, 삽입(enqueue)과 삭제(dequeue) 모두 O(1)의 시간 복잡도를 가지므로, 큐의 시간 복잡도도 O(1)이다.
링 버퍼는 아래 그림처럼 배열의 맨 뒤가 맨 앞과 연결되었다고 보는 자료구조이다.

여기서 논리적으로 어떤 요소가 맨 앞의 요소이고 어떤 요소가 맨 뒤의 요소인지 식별하기 위한 변수가 프론트(front)와 리어(rear)이다.

아래는 링 버퍼를 이용하여 큐를 구현한 기본 코드이다. (Chat-GPT)

public class RingBufferQueue {
    private int[] buffer;   // 링 버퍼 배열
    private int front;      // 큐의 첫 번째 요소 인덱스
    private int rear;       // 큐의 마지막 요소 인덱스
    private int size;       // 큐의 크기
    private int count;      // 큐에 저장된 요소의 개수

    public RingBufferQueue(int size) {
        this.buffer = new int[size];
        this.front = 0;
        this.rear = -1;
        this.size = size;
        this.count = 0;
    }

    // 큐에 데이터를 삽입하는 메소드
    public void enqueue(int data) {
        if (count == size) {
            System.out.println("Queue is full");
            return;
        }

        rear = (rear + 1) % size;
        buffer[rear] = data;
        count++;
    }

    // 큐에서 데이터를 삭제하고 반환하는 메소드
    public int dequeue() {
        if (count == 0) {
            System.out.println("Queue is empty");
            return -1;
        }

        int data = buffer[front];
        front = (front + 1) % size;
        count--;

        return data;
    }

    // 큐의 첫 번째 요소를 반환하는 메소드
    public int peek() {
        if (count == 0) {
            System.out.println("Queue is empty");
            return -1;
        }

        return buffer[front];
    }

    // 큐가 비어있는지 확인하는 메소드
    public boolean isEmpty() {
        return count == 0;
    }

    // 큐의 크기를 반환하는 메소드
    public int size() {
        return count;
    }

    public static void main(String[] args) {
        RingBufferQueue queue = new RingBufferQueue(5);

        queue.enqueue(1);
        queue.enqueue(2);
        queue.enqueue(3);
        queue.enqueue(4);
        queue.enqueue(5);

        System.out.println(queue.dequeue());   // 1
        System.out.println(queue.dequeue());   // 2

        queue.enqueue(6);
        queue.enqueue(7);

        System.out.println(queue.dequeue());   // 3
        System.out.println(queue.dequeue());   // 4
        System.out.println(queue.dequeue());   // 5
        System.out.println(queue.dequeue());   // 6
        System.out.println(queue.dequeue());   // 7
    }
}

---

🌌 Chat-GPT의 예제 소스

큐 활용 예제 1

1부터 n까지의 합을 계산

import java.util.LinkedList;
import java.util.Queue;

public class SumOfNumbers {
    public static int sumOfNumbers(int n) {
        if (n < 1) {
            return 0;
        }

        int sum = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(1);

        for (int i = 2; i <= n; i++) {
            int size = queue.size();

            for (int j = 0; j < size; j++) {
                int num = queue.poll();
                sum += num;

                if (i != n) {
                    queue.offer(num * 10 + i);
                }
            }
        }

        while (!queue.isEmpty()) {
            sum += queue.poll();
        }

        return sum;
    }

    public static void main(String[] args) {
        int n = 5;
        int sum = sumOfNumbers(n);
        System.out.println("Sum of numbers from 1 to " + n + " is: " + sum);
    }
}

출력결과

Sum of numbers from 1 to 5 is: 1370

위 코드에서는 Queue를 사용하여 자연수 n을 받아, 1부터 n까지의 합을 계산하는 sumOfNumbers() 메소드를 정의한다. 이 메소드에서는 먼저 1을 Queue에 추가하고, 2부터 n까지 순회하면서 Queue에서 원소를 꺼내어 더해준다. 이 때, 꺼낸 원소에 10을 곱하고 i를 더한 값을 Queue에 추가하여, 다음 자릿수의 수를 생성한다. 이러한 과정을 n-1번 반복한 후, Queue에 남아있는 원소들을 모두 더해주어 최종 합을 계산한다.

큐 활용 예제 2

요세푸스 문제

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Main {

    public static List<Integer> lastRemaining(int n, int k) {
        if (n < 1 || k < 1) {
            return null;
        }

        List<Integer> list = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            list.add(i);
        }

        List<Integer> removedList = new ArrayList<>();
        int index = 0;
        while (list.size() > 1) {
            index = (index + k - 1) % list.size();
            int removed = list.remove(index);
            removedList.add(removed);
        }

        removedList.add(list.get(0));
        return removedList;
    }

    public static void main(String[] args) {
        List<Integer> removedList = lastRemaining(7, 3);
        System.out.println("Removed people: " + removedList);
        System.out.println("Last remaining person: " + removedList.get(removedList.size() - 1));
    }

}

위 코드에서는 List를 사용하여 요세푸스 문제를 해결하는 lastRemaining() 메소드를 정의하고, 이 메소드를 main() 메소드에서 호출하여 마지막으로 남은 사람의 번호와 제거된 사람의 번호를 출력한다.
Removed people로 제거된 사람들을 제거 순서대로 나열하고, 마지막에 남은 사람을 Last remaining person으로 표시한다.

출력결과

Removed people: [3, 6, 2, 7, 5, 1, 4]
Last remaining person: 4