1. Queue
- 정의: Queue는 "선입선출(First-In-First-Out, FIFO)" 방식의 자료구조입니다. 즉, 먼저 들어온 데이터가 먼저 나가는 구조입니다.
- 사용 방법: add() 또는 offer() 메서드로 큐의 끝에 요소를 추가하고, remove() 또는 poll() 메서드로 큐의 앞에서 요소를 제거합니다.
- 대표적 구현체: LinkedList, PriorityQueue, ArrayBlockingQueue
- 주요 메서드
add(): 큐의 끝에 요소를 추가합니다. 큐의 크기가 제한되어 있고 가득 찬 경우 예외를 던집니다.
offer(): 큐의 끝에 요소를 추가합니다. 큐의 크기가 제한되어 있고 가득 찬 경우 false를 반환합니다.
remove(): 큐의 앞에서 요소를 제거하고 반환합니다. 큐가 비어있으면 예외를 던집니다.
poll(): 큐의 앞에서 요소를 제거하고 반환합니다. 큐가 비어있으면 null을 반환합니다.
peek(): 큐의 앞에 있는 요소를 반환하되, 큐에서 제거하지 않습니다. - 사용 사례
작업 대기열(Task Queue): 작업을 순차적으로 처리해야 할 때, 예를 들어 프린터 작업 대기열이나 요청 처리 대기열에서 사용합니다.
BFS 알고리즘: 너비 우선 탐색(Breadth-First Search) 알고리즘에서 노드를 탐색할 때 Queue를 사용합니다.
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.offer(1);
queue.offer(2);
queue.offer(3);
System.out.println(queue.poll()); // 출력: 1
System.out.println(queue.peek()); // 출력: 2
}
}2. Stack
- 정의: Stack은 "후입선출(Last-In-First-Out, LIFO)" 방식의 자료구조입니다. 즉, 나중에 들어온 데이터가 먼저 나가는 구조입니다.
- 사용 방법: push() 메서드로 스택의 맨 위에 요소를 추가하고, pop() 메서드로 스택의 맨 위에서 요소를 제거합니다.
- 대표적 구현체: java.util.Stack 클래스
- 주요 메서드
push(): 스택의 맨 위에 요소를 추가합니다.
pop(): 스택의 맨 위에서 요소를 제거하고 반환합니다. 스택이 비어있으면 예외를 던집니다.
peek(): 스택의 맨 위에 있는 요소를 반환하되, 스택에서 제거하지 않습니다.
empty(): 스택이 비어있는지를 반환합니다. - 사용 사례
수식 계산기: 수식을 후위 표기법(Reverse Polish Notation)으로 변환하여 계산할 때 스택을 사용합니다.
재귀적인 알고리즘: 재귀적인 문제를 반복 구조로 풀 때, 호출 스택을 모방하여 스택을 사용합니다.
브라우저의 뒤로 가기 기능: 사용자가 방문한 페이지를 스택에 저장해 두었다가 뒤로 가기 요청 시 pop하여 페이지를 보여주는 기능에 사용됩니다.
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 출력: 3
System.out.println(stack.peek()); // 출력: 2
}
}
3. Deque
- 정의: Deque는 "양방향 큐(Double-Ended Queue)"의 약자로, 큐의 앞과 뒤 양쪽에서 삽입과 삭제가 모두 가능한 자료구조입니다. 따라서 Deque는 Queue와 Stack의 특성을 모두 가질 수 있습니다.
- 사용 방법: Deque 인터페이스는 큐의 양쪽에서 삽입과 삭제를 처리할 수 있는 여러 메서드를 제공합니다.
- 대표적 구현체: ArrayDeque, LinkedList
- 주요 메서드
addFirst(): 덱의 앞에 요소를 추가합니다.
addLast(): 덱의 뒤에 요소를 추가합니다.
removeFirst(): 덱의 앞에서 요소를 제거하고 반환합니다.
removeLast(): 덱의 뒤에서 요소를 제거하고 반환합니다.
getFirst(): 덱의 앞에 있는 요소를 반환하되, 덱에서 제거하지 않습니다.
getLast(): 덱의 뒤에 있는 요소를 반환하되, 덱에서 제거하지 않습니다. - 사용 사례
덱을 사용한 큐 또는 스택 대체: Deque는 큐와 스택의 역할을 모두 할 수 있으므로, 이 두 가지 기능을 모두 필요로 하는 경우에 유용합니다.
이중 끝 스택 알고리즘: 양방향에서 삽입 및 삭제가 필요한 알고리즘에 사용됩니다.
Sliding Window: 특정 범위 내에서 최대값이나 최소값을 찾는 슬라이딩 윈도우 알고리즘에서 유용하게 사용할 수 있습니다.
import java.util.ArrayDeque;
import java.util.Deque;
public class DequeAsStack {
public static void main(String[] args) {
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // 출력: 3
System.out.println(stack.peek()); // 출력: 2
}
}
4. Stack vs Deque: 무엇을 사용할까?
Stack을 사용하는 이점
- 간단한 API: Stack 클래스는 간단한 API를 제공하여 사용이 직관적입니다.
- 레거시 코드와의 호환성: 기존에 작성된 코드에서 Stack을 사용하고 있다면 호환성을 유지할 수 있습니다.
Deque를 사용하는 이유
- 더 나은 성능 및 유연성: Deque는 큐와 스택의 모든 기능을 지원하며, 더 나은 성능을 제공합니다.
- 현대적인 설계: Deque는 API가 일관되고 설계가 현대적이어서 유지보수성이 높습니다.
- 양방향 기능 제공: 스택과 큐의 기능을 모두 필요로 하는 경우 유용합니다.
5. Stack의 동시성 문제(성능 저하)와 대안
Stack 클래스는 동기화 메서드를 통해 스레드 안전성을 보장하지만, 이는 성능 저하를 초래할 수 있습니다. 따라서, 멀티스레드 환경에서 스택이 필요하다면, 동시성을 제공하는 다른 컬렉션을 고려하는 것이 좋습니다.
ConcurrentLinkedDeque: 스레드 안전한 Deque 구현체로, Deque의 양방향 기능을 그대로 사용하면서도 동시성을 보장합니다.
import java.util.concurrent.ConcurrentLinkedDeque;
public class ConcurrentDequeExample {
public static void main(String[] args) {
ConcurrentLinkedDeque<Integer> deque = new ConcurrentLinkedDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(deque.pop()); // 출력: 3
}
}Deque의 구현체 ArrayDeque와 LinkedList 비교
- 메모리 효율성: ArrayDeque는 내부적으로 크기가 가변적인 배열을 사용하여 요소를 저장합니다. 이 배열은 요소가 추가됨에 따라 동적으로 확장됩니다. 반면, LinkedList는 각 요소를 저장할 때 추가적인 객체(노드)와 그 안에 두 개의 포인터(이전 노드와 다음 노드)를 사용해야 하므로 메모리 사용량이 더 많습니다. 이로 인해 ArrayDeque는 일반적으로 더 적은 메모리를 사용합니다.
- 캐시 적중률: ArrayDeque는 배열을 사용하기 때문에 요소가 메모리 상에서 연속적으로 저장됩니다. 이는 CPU 캐시의 효율성을 높이고, 메모리 접근 속도를 향상시킬 수 있습니다. 반면, LinkedList의 노드는 메모리 상에 분산되어 저장되기 때문에 캐시 적중률이 낮아질 수 있습니다.
- 상수 시간 복잡도: ArrayDeque는 요소의 추가와 제거 작업에서 상수 시간(Amortized O(1))이 걸립니다. 특히, 양쪽 끝에서의 추가 및 제거 작업이 빠릅니다. 반면, LinkedList는 특정 위치에 있는 요소를 추가하거나 제거할 때 양방향으로 리스트를 탐색해야 하는 경우 O(n)의 시간이 소요될 수 있습니다.
- 더 나은 성능: 실제 사용에서 ArrayDeque는 대부분의 작업에서 LinkedList보다 더 나은 성능을 보입니다. 특히 중간에서의 삽입, 삭제 작업이 많이 일어나지 않는 경우에는 ArrayDeque가 압도적으로 빠릅니다.
6. 결론: 언제 어떤 자료구조를 선택해야 할까?
- FIFO 구조가 필요할 때: 순차적으로 작업을 처리해야 하는 경우 Queue를 사용
- LIFO 구조가 필요할 때: 최근에 추가된 데이터를 먼저 처리해야 하는 경우 Stack을 사용하거나, 더 현대적이고 유연한 대안으로 Deque를 사용
- 양방향 삽입/삭제가 필요할 때: Deque를 사용하여 양쪽에서 데이터를 효율적으로 처리
대부분의 새로운 개발에서는 Deque를 사용하는 것이 권장됩니다. Deque는 큐와 스택의 기능을 모두 제공하며, 성능과 유연성 면에서 Stack보다 우수하기 때문입니다. 그러나 간단한 스택 기능이 필요하거나 레거시 코드와의 호환성이 중요한 경우에는 Stack을 사용할 수 있습니다. 각 자료구조의 특성을 잘 이해하고, 구체적인 요구 사항에 맞춰 적절한 자료구조를 선택하는 것이 중요합니다.
안녕하세요. 블로그를 시작하게 되었습니다! 앞으로 유용한 정보와 좋은 내용을 많이 공유할게요:)