큐 (Queue)
프로그래밍에서 큐(Queue)는 데이터를 순서대로 처리하는 자료구조로, FIFO(First In, First Out) 방식으로 동작한다. 즉, 먼저 추가된 데이터가 가장 먼저 제거된다. 큐는 작업 스케줄링, BFS(너비 우선 탐색), 대기열 관리 등에서 사용된다. 이번 포스팅은 큐의 기본 개념부터 자바에서의 구현, 활용 알고리즘, 심화 주제까지 다룬다.
큐를 이해하면 데이터를 순차적으로 처리하고 복잡한 문제를 효율적으로 해결할 수 있다. 하나씩 알아보자.
큐의 정의와 특징
큐는 데이터를 한쪽 끝에서 추가하고 반대쪽 끝에서 제거하는 자료구조이다. 데이터를 추가하는 연산을 인큐(enqueue), 제거하는 연산을 디큐(dequeue)라고 한다. 큐의 앞쪽은 프론트(front), 뒤쪽은 리어(rear)라 부른다.
큐의 장점은 다음과 같다:
- 순차 처리: FIFO 방식으로 데이터 처리 순서를 보장한다.
- 빠른 연산: 인큐와 디큐가 O(1) 시간에 수행된다.
- 다양한 활용: 작업 대기열, BFS, 캐시 구현 등에 유용하다.
단점은 다음과 같다:
- 제한된 접근: 프론트와 리어만 접근 가능하며, 중간 데이터 접근은 불가능하다.
- 고정 크기 배열 사용 시 제한: 동적 크기 조정이 필요하다.
- 비연속적 메모리: 연결 리스트 기반 구현 시 캐시 활용도가 낮다.
큐의 종류
큐는 구현 방식과 동작에 따라 여러 가지로 나뉜다. 아래는 주요 형태와 구조를 도식화한 그림이다.
1. 배열 기반 큐(Array-based Queue)
고정 크기 배열을 사용해 큐를 구현한다. 메모리 효율이 높지만 크기 제한이 있다.
[Front] [1] [2] [3] [Rear]
↑ ↑
Front Rear
2. 연결 리스트 기반 큐(Linked List-based Queue)
연결 리스트를 사용해 동적으로 크기를 조정한다.
[Front] → [Node|data:1|next] → [Node|data:2|next] → [Node|data:3|null]
3. 원형 큐(Circular Queue)
배열의 끝과 처음을 연결해 공간을 효율적으로 사용한다.
[3] [2] [1] [ ]
↑ ↑
Rear Front
이 포스팅에서는 배열 기반 큐와 원형 큐를 중심으로 설명하며, 필요 시 연결 리스트 기반을 다룬다.
자바에서 원형 큐 구현
원형 큐는 배열 기반 큐의 공간 낭비를 줄인다. 아래는 원형 큐의 자바 구현이다.
class CircularQueue {
private int[] arr;
private int front;
private int rear;
private int capacity;
private int size;
public CircularQueue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
size = 0;
}
// 인큐: 큐에 데이터 추가
public void enqueue(int data) {
if (size == capacity) {
System.out.println("Queue is Full");
return;
}
rear = (rear + 1) % capacity;
arr[rear] = data;
size++;
}
// 디큐: 큐에서 데이터 제거
public int dequeue() {
if (size == 0) {
System.out.println("Queue is Empty");
return -1;
}
int data = arr[front];
front = (front + 1) % capacity;
size--;
return data;
}
// 프론트 데이터 확인
public int peek() {
if (size == 0) {
System.out.println("Queue is Empty");
return -1;
}
return arr[front];
}
// 비어 있는지 확인
public boolean isEmpty() {
return size == 0;
}
}
이 코드는 원형 큐로, 인큐, 디큐, 피크, 비어 있음 확인 기능을 포함한다.
큐의 기본 연산
큐의 주요 연산은 다음과 같다:
1. 인큐(Enqueue)
큐의 리어에 데이터를 추가한다.
public void enqueue(int data) {
if (size == capacity) {
System.out.println("Queue is Full");
return;
}
rear = (rear + 1) % capacity;
arr[rear] = data;
size++;
}
2. 디큐(Dequeue)
큐의 프론트에서 데이터를 제거하고 반환한다.
public int dequeue() {
if (size == 0) {
System.out.println("Queue is Empty");
return -1;
}
int data = arr[front];
front = (front + 1) % capacity;
size--;
return data;
}
3. 피크(Peek)
프론트 데이터를 제거하지 않고 반환한다.
public int peek() {
if (size == 0) {
System.out.println("Queue is Empty");
return -1;
}
return arr[front];
}
4. 비어 있음 확인(IsEmpty)
큐가 비어 있는지 확인한다.
public boolean isEmpty() {
return size == 0;
}
큐의 시간 복잡도
큐의 주요 연산의 시간 복잡도는 다음과 같다:
- 인큐(Enqueue): O(1)
- 디큐(Dequeue): O(1)
- 피크(Peek): O(1)
- 비어 있음 확인(IsEmpty): O(1)
연결 리스트 기반 큐도 동일한 시간 복잡도를 가지지만, 메모리 할당/해제 비용이 추가된다.
연결 리스트 기반 큐 구현
연결 리스트를 사용한 큐는 동적 크기 조정이 가능하다.
class LinkedQueue {
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node front;
private Node rear;
public LinkedQueue() {
front = rear = null;
}
public void enqueue(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
return;
}
rear.next = newNode;
rear = newNode;
}
public int dequeue() {
if (front == null) {
System.out.println("Queue is Empty");
return -1;
}
int data = front.data;
front = front.next;
if (front == null) rear = null;
return data;
}
public int peek() {
if (front == null) {
System.out.println("Queue is Empty");
return -1;
}
return front.data;
}
public boolean isEmpty() {
return front == null;
}
}
연결 리스트 기반 큐는 배열 기반 큐와 달리 크기 제한이 없지만, 노드 생성 비용이 추가된다.
큐를 활용한 알고리즘
큐는 BFS, 작업 스케줄링, 슬라이딩 윈도우 등에서 사용된다.
1. BFS(너비 우선 탐색)
그래프에서 노드를 레벨 순서로 탐색한다.
import java.util.LinkedList;
public void bfs(int start, int[][] graph, boolean[] visited) {
LinkedQueue queue = new LinkedQueue();
queue.enqueue(start);
visited[start] = true;
while (!queue.isEmpty()) {
int v = queue.dequeue();
System.out.print(v + " ");
for (int u : graph[v]) {
if (!visited[u]) {
queue.enqueue(u);
visited[u] = true;
}
}
}
}
2. 슬라이딩 윈도우 최대값
배열에서 크기 k의 슬라이딩 윈도우의 최대값을 찾는다.
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
LinkedQueue deque = new LinkedQueue();
for (int i = 0; i < nums.length; i++) {
while (!deque.isEmpty() && deque.peek() < i - k + 1) {
deque.dequeue();
}
while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.dequeueLast();
}
deque.enqueue(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peek()];
}
}
return result;
}
3. 작업 스케줄링
작업 대기열을 큐로 관리한다.
public void processTasks(int[] tasks) {
LinkedQueue queue = new LinkedQueue();
for (int task : tasks) {
queue.enqueue(task);
}
while (!queue.isEmpty()) {
int task = queue.dequeue();
System.out.println("Processing task: " + task);
}
}
심화 주제: 큐 최적화
큐를 효율적으로 사용하려면 몇 가지 기법을 고려해야 한다.
1. 원형 큐 사용
배열 기반 큐에서 공간 낭비를 줄이기 위해 원형 큐를 사용한다.
2. 동적 배열 사용
배열 기반 큐에서 크기를 동적으로 확장한다.
public void enqueue(int data) {
if (size == capacity) {
int[] newArr = new int[capacity * 2];
for (int i = 0; i < size; i++) {
newArr[i] = arr[(front + i) % capacity];
}
arr = newArr;
front = 0;
rear = size - 1;
capacity *= 2;
}
rear = (rear + 1) % capacity;
arr[rear] = data;
size++;
}
3. 메모리 관리
연결 리스트 기반 큐에서 노드를 재사용하거나 가비지 컬렉션에 도움을 준다.
큐의 한계와 대안
큐는 접근이 제한적이며, 중간 데이터 조작이 불가능하다. 자바에서는 java.util.LinkedList와 java.util.ArrayDeque를 제공한다.
import java.util.LinkedList;
LinkedList<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
int front = queue.poll(); // 1
ArrayDeque는 큐와 덱으로 사용 가능하며, 성능이 더 우수하다.
import java.util.ArrayDeque;
ArrayDeque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
queue.offer(2);
int front = queue.poll(); // 1
문제
큐를 활용한 알고리즘을 연습하기 위해 난이도별 문제를 제시하고, 자바 코드로 해답을 제공한다.
난이도 하: 큐 연산
시간 제한: 1 초 | 메모리 제한: 256 MB | 제출: 100,000 | 정답: 80,000 | 맞힌 사람: 70,000 | 정답 비율: 80.000%
정수 연산이 주어진다. 연산은 “enqueue x” (x를 큐에 추가) 또는 “dequeue” (큐에서 프론트 값을 제거하고 출력)이다. 모든 연산을 수행한 결과를 출력한다.
입력
첫째 줄에 연산 수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N줄에 “enqueue x” (x는 -1,000 ≤ x ≤ 1,000) 또는 “dequeue”가 주어진다.
출력
각 “dequeue” 연산의 결과를 한 줄에 하나씩 출력한다. 큐가 비어 있으면 -1을 출력한다.
입력 예시
5
enqueue 1
enqueue 2
dequeue
enqueue 3
dequeue
출력 예시
1
2
문제 출처: 자체 제작
해답
해답 펼치기
import java.util.Scanner;
public class QueueOperations {
static class CircularQueue {
private int[] arr;
private int front;
private int rear;
private int capacity;
private int size;
CircularQueue(int size) {
arr = new int[size];
capacity = size;
front = 0;
rear = -1;
size = 0;
}
void enqueue(int data) {
rear = (rear + 1) % capacity;
arr[rear] = data;
size++;
}
int dequeue() {
if (size == 0) return -1;
int data = arr[front];
front = (front + 1) % capacity;
size--;
return data;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
CircularQueue queue = new CircularQueue(N);
sc.nextLine();
for (int i = 0; i < N; i++) {
String operation = sc.nextLine();
if (operation.startsWith("enqueue")) {
int x = Integer.parseInt(operation.split(" ")[1]);
queue.enqueue(x);
} else {
System.out.println(queue.dequeue());
}
}
sc.close();
}
}
난이도 중: 작업 스케줄링
작업 목록이 주어진다. 각 작업은 처리 시간이 필요하며, 큐를 사용해 작업을 순차적으로 처리한다. 모든 작업을 처리하는 데 걸리는 총 시간을 계산한다.
입력
첫째 줄에 작업 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. 각 정수는 작업의 처리 시간(1 ≤ 시간 ≤ 1,000)을 나타낸다.
출력
모든 작업을 처리하는 데 걸리는 총 시간을 출력한다.
입력 예시
3
2 3 1
출력 예시
6
문제 출처: 자체 제작
해답
해답 펼치기
import java.util.Scanner;
public class TaskScheduling {
static class LinkedQueue {
static class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
private Node front;
private Node rear;
LinkedQueue() {
front = rear = null;
}
void enqueue(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
return;
}
rear.next = newNode;
rear = newNode;
}
int dequeue() {
if (front == null) return -1;
int data = front.data;
front = front.next;
if (front == null) rear = null;
return data;
}
boolean isEmpty() {
return front == null;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
LinkedQueue queue = new LinkedQueue();
int totalTime = 0;
for (int i = 0; i < N; i++) {
int time = sc.nextInt();
queue.enqueue(time);
}
while (!queue.isEmpty()) {
totalTime += queue.dequeue();
}
System.out.println(totalTime);
sc.close();
}
}
난이도 상: 슬라이딩 윈도우 최대값
정수 배열과 윈도우 크기 k가 주어진다. 크기 k의 슬라이딩 윈도우가 배열을 이동하며 각 윈도우의 최대값을 구하는 프로그램을 작성한다.
입력
첫째 줄에 배열의 길이 N (1 ≤ N ≤ 100,000)과 윈도우 크기 k (1 ≤ k ≤ N)이 주어진다. 둘째 줄에 N개의 정수가 공백으로 구분되어 주어진다. 모든 정수는 -1,000보다 크거나 같고, 1,000보다 작거나 같다.
출력
각 윈도우의 최대값을 공백으로 구분해 출력한다.
입력 예시
8 3
1 3 -1 -3 5 3 6 7
출력 예시
3 3 5 5 6 7
문제 출처: LeetCode "Sliding Window Maximum"
해답
해답 펼치기
import java.util.Scanner;
public class SlidingWindowMax {
static class Deque {
static class Node {
int data;
Node next;
Node prev;
Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
private Node front;
private Node rear;
Deque() {
front = rear = null;
}
void addLast(int data) {
Node newNode = new Node(data);
if (rear == null) {
front = rear = newNode;
return;
}
newNode.prev = rear;
rear.next = newNode;
rear = newNode;
}
void removeFirst() {
if (front == null) return;
front = front.next;
if (front == null) rear = null;
else front.prev = null;
}
void removeLast() {
if (rear == null) return;
rear = rear.prev;
if (rear == null) front = null;
else rear.next = null;
}
int getFirst() {
if (front == null) return -1;
return front.data;
}
int getLast() {
if (rear == null) return -1;
return rear.data;
}
boolean isEmpty() {
return front == null;
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int k = sc.nextInt();
int[] nums = new int[N];
for (int i = 0; i < N; i++) {
nums[i] = sc.nextInt();
}
int[] result = new int[N - k + 1];
Deque deque = new Deque();
for (int i = 0; i < N; i++) {
while (!deque.isEmpty() && deque.getFirst() < i - k + 1) {
deque.removeFirst();
}
while (!deque.isEmpty() && nums[deque.getLast()] < nums[i]) {
deque.removeLast();
}
deque.addLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.getFirst()];
}
}
for (int max : result) {
System.out.print(max + " ");
}
System.out.println();
sc.close();
}
}
마무리
큐는 FIFO 방식으로 데이터를 관리하는 자료구조로, 인큐와 디큐 연산이 빠르다. 배열 기반, 연결 리스트 기반, 원형 큐의 구현, 기본 연산, 시간 복잡도, 활용 알고리즘, 최적화 기법을 다뤘다. 자바의 LinkedList와 ArrayDeque와의 비교를 통해 한계와 대안을 살펴봤다. 문제를 통해 큐를 조작하는 방법을 익혔으니, 이를 바탕으로 더 복잡한 문제를 해결해보자.
'코딩 공부 > 알고리즘(자바)' 카테고리의 다른 글
| 기본 자료구조 - 해시 테이블 (Hash Table) (0) | 2025.05.08 |
|---|---|
| 기본 자료구조 - 덱 (Deque) (3) | 2025.05.06 |
| 기본 자료구조 - 스택 (Stack) (0) | 2025.05.03 |
| 기본 자료구조 - 연결 리스트 (Linked List) (1) | 2025.05.03 |
| 기본 자료구조 - 배열 (Array) (1) | 2025.04.04 |