본 시리즈는 프로그래밍 자료구조의 개념을 정리하고 실습을 진행해보는 시리즈입니다.
- 실습은 다음과 같은 개발환경 및 버전에서 진행하였습니다.
- IDE : IntelliJ IDEA (Ultimate Edition)
- Java : JDK 21 (corretto-21)
- Python : 3.9 (conda env)
자료구조 - Deque
0. 서론: Deque란?
Deque(Double-Ended Queue, 데크, 덱)은 양방향에서 데이터를 삽입하고 제거할 수 있는 자료구조입니다.
- 일반적인 큐(Queue)는 FIFO(First In, First Out) 방식으로 동작하며, 스택(Stack)은 LIFO(Last In, First Out) 방식으로 동작합니다.
- 반면에, Deque는 양쪽 끝에서 데이터를 삽입하거나 제거할 수 있어 스택과 큐의 특성을 모두 가집니다.
- Deque는 다양한 상황에서 효율적으로 사용될 수 있으며, 큐와 스택의 기능을 모두 활용해야 하는 경우에 특히 유용합니다.
Deque의 특징
Deque는 양쪽 끝에서 삽입과 삭제가 가능한 구조로, 다음과 같은 주요 연산을 지원합니다:
addFirst(item): 덱의 앞쪽에 데이터를 추가합니다.addLast(item): 덱의 뒤쪽에 데이터를 추가합니다.removeFirst(): 덱의 앞쪽에서 데이터를 제거합니다.removeLast(): 덱의 뒤쪽에서 데이터를 제거합니다.peekFirst(): 덱의 앞쪽에 있는 데이터를 확인합니다.peekLast(): 덱의 뒤쪽에 있는 데이터를 확인합니다.isEmpty(): 덱이 비어 있는지 확인합니다.
이처럼 Deque는 양쪽 끝에서 데이터를 처리할 수 있기 때문에, 스택이나 큐보다 유연한 자료구조로, 양방향에서 데이터를 처리해야 하는 다양한 알고리즘에서 중요한 역할을 합니다.
Deque의 활용
Deque는 다음과 같은 상황에서 매우 유용하게 사용됩니다:
- 양방향 탐색이 필요한 문제: 덱의 앞과 뒤에서 동시에 데이터를 처리할 수 있기 때문에, 양방향으로 데이터를 처리해야 하는 문제에서 효과적입니다.
- 스케줄링 알고리즘: 양방향에서 작업을 추가하거나 제거해야 할 때 덱이 적합합니다.
- 캐시 구현: LRU(Least Recently Used) 알고리즘을 구현할 때, 덱을 사용하여 가장 최근에 사용된 항목을 앞쪽이나 뒤쪽으로 빠르게 이동시키는 데 활용할 수 있습니다.
이처럼 Deque는 큐와 스택의 기능을 모두 지원하면서도 더 유연한 사용이 가능하다는 점에서, 다양한 프로그래밍 문제에서 강력한 도구로 사용될 수 있습니다.
1-1. Deque 개념과 구현 - Java
1-1.1 Java Deque Interface
Java에서 Deque는 Queue와 Stack의 특성을 모두 가지며, 양쪽 끝에서 삽입 및 삭제가 가능한 자료구조입니다.
- Java에서는
Deque인터페이스를 제공하며, 이를 구현한 대표적인 클래스들이 ArrayDeque와 LinkedList입니다.
Deque 인터페이스
Deque 인터페이스는 양방향 큐 연산을 위한 메서드들을 제공합니다.
- 이 메서드들은 양쪽 끝(앞쪽과 뒤쪽)에서 데이터를 삽입하거나 삭제하는 기능을 지원하며, 이를 통해
Deque는 큐(Queue)와 스택(Stack)의 기능을 모두 구현할 수 있습니다. - 참고로
Queue인터페이스를 상속 받는 인터페이스이기 때문에Queue의 메서드들도 함께 구현되어있어서 동일한 메서드 명으로 사용 가능합니다.- 또한 추가적으로 Stack 메서드인
push()와pop()도 구현되어 있습니다.
- 또한 추가적으로 Stack 메서드인
주요 Deque 구현체
- ArrayDeque
- 원형 배열 기반으로 구현된
Deque자료구조입니다. - 크기가 동적으로 확장되는 원형 배열을 사용하여, 배열이 가득 찼을 때 크기를 자동으로 확장합니다.
- 주요 연산들이 O(1) 시간 복잡도를 가지며, 매우 빠른 성능을 제공합니다.
ArrayDeque는 스레드 안전하지 않지만, 대부분의 상황에서 빠르고 효율적이기 때문에Deque구현체로 자주 사용됩니다.- Java의
ArrayDeque는 기본적으로 큐와 스택으로 모두 사용될 수 있습니다. - 배열의 크기가 가득 찼을 때 재할당 비용이 발생할 수 있다는 단점이 있지만, 그 외에는 메모리 오버헤드가 적고 성능이 뛰어납니다.
- LinkedList
- 연결 리스트 기반으로 구현된
Deque자료구조입니다. - 각 노드가 다른 노드와 연결되어 있으며, 노드를 동적으로 추가하거나 제거할 수 있습니다.
- 삽입 및 삭제 연산이 빈번할 때 효율적으로 사용되며, 각 연산의 시간 복잡도는 O(1)입니다.
- 하지만 각 노드가 추가적인 메모리 공간(포인터)을 사용하므로, 메모리 사용량이
ArrayDeque보다 더 큽니다. - 스택, 큐 또는 양방향 큐로 사용될 수 있으며, 필요에 따라 다양한 방식으로 데이터를 처리할 수 있습니다.
ArrayDeque와 LinkedList 비교
ArrayDeque는 배열 기반이므로 연속된 메모리를 사용해 매우 빠른 인덱싱을 지원하며, 메모리 오버헤드가 적습니다. 하지만 배열의 크기가 가득 차면 크기 재조정이 발생할 수 있고 이때만 성능이 약간 저하됩니다.- 반면에
LinkedList는 동적 크기 조절이 자연스럽게 가능하지만, 각 노드마다 포인터가 필요하므로 메모리 오버헤드가 큽니다.
성능 면에서는 ArrayDeque가 일반적으로 더 빠르고 효율적입니다. 그렇기 때문에, ArrayDeque는 Java에서 Deque로 구현할 때 가장 널리 사용됩니다.
1-1.2 Deque 인터페이스의 주요 메서드
1. 데이터 삽입 메서드
Deque는 데이터를 앞쪽 또는 뒤쪽에 삽입할 수 있는 다양한 메서드를 제공합니다. 이 메서드들은 큐와 스택의 모든 삽입 방식들을 지원합니다.
addFirst(E e): 덱의 앞쪽에 요소를 추가합니다. 삽입에 실패할 경우 예외를 던집니다.addLast(E e): 덱의 뒤쪽에 요소를 추가합니다. 삽입에 실패할 경우 예외를 던집니다.offerFirst(E e): 덱의 앞쪽에 요소를 삽입하고, 성공 여부를 true/false로 반환합니다. 예외를 던지지 않습니다.offerLast(E e): 덱의 뒤쪽에 요소를 삽입하고, 성공 여부를 true/false로 반환합니다. 예외를 던지지 않습니다.
2. 데이터 삭제 메서드
Deque는 양방향에서 데이터를 삭제하는 여러 메서드를 제공합니다. 이를 통해 큐의 dequeue 및 스택의 pop 기능을 지원합니다.
removeFirst(): 덱의 앞쪽에서 요소를 제거하고 반환합니다. 제거할 요소가 없으면 예외를 던집니다.removeLast(): 덱의 뒤쪽에서 요소를 제거하고 반환합니다. 제거할 요소가 없으면 예외를 던집니다.pollFirst(): 덱의 앞쪽에서 요소를 제거하고 반환합니다. 덱이 비어있을 경우 null을 반환합니다.pollLast(): 덱의 뒤쪽에서 요소를 제거하고 반환합니다. 덱이 비어있을 경우 null을 반환합니다.
3. 데이터 조회 메서드
데이터를 삭제하지 않고 현재 덱의 앞쪽 또는 뒤쪽 요소를 확인하는 메서드입니다.
peekFirst(): 덱의 앞쪽에 있는 요소를 반환하지만, 제거하지는 않습니다. 덱이 비어 있으면 null을 반환합니다.peekLast(): 덱의 뒤쪽에 있는 요소를 반환하지만, 제거하지는 않습니다. 덱이 비어 있으면 null을 반환합니다.
4. 스택 연산을 지원하는 메서드
Deque는 스택과 유사하게 동작하는 메서드도 제공합니다.
push(E e): 덱의 앞쪽에 데이터를 삽입하는 스택 연산입니다.- 즉, addFirst()와 동일하게 동작합니다.
pop(): 덱의 앞쪽에서 데이터를 제거하고 반환하는 스택 연산입니다.- removeFirst()와 동일하게 동작합니다.
5. 기타 메서드
isEmpty(): 덱이 비어있는지 여부를 확인하는 메서드로, 비어 있으면 true를 반환하고, 요소가 있으면 false를 반환합니다.size(): 덱에 있는 요소의 개수를 반환합니다.iterator(): 덱의 요소들을 앞쪽부터 차례대로 순회하는 반복자를 반환합니다.descendingIterator(): 덱의 요소들을 뒤쪽부터 차례대로 순회하는 반복자를 반환합니다.
Queue와 Stack의 기능 통합
Deque는 Queue 인터페이스를 상속받으면서 큐의 기본 연산인 offer, poll, peek 등을 모두 지원합니다. 또한 스택의 push()와 pop() 메서드도 제공하여, 큐와 스택의 장점을 모두 통합한 유연한 자료구조입니다.
- Deque는 스택으로 사용할 때는 LIFO(Last In, First Out) 방식으로 동작하며, 큐로 사용할 때는 FIFO(First In, First Out) 방식으로 동작합니다.
- 이 덕분에 다양한 데이터 처리 상황에서 매우 유용하게 사용될 수 있습니다.
1-1.3 Java Deque 코드 예시
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
public class DequeExample {
public static void main(String[] args) {
// ArrayDeque 사용
Deque<Integer> arrayDeque = new ArrayDeque<>();
// 데이터 삽입
arrayDeque.addFirst(10);
arrayDeque.addLast(20);
arrayDeque.addLast(30);
// 데이터 확인
System.out.println(arrayDeque.peekFirst()); // 10 출력
System.out.println(arrayDeque.peekLast()); // 30 출력
// 데이터 제거
System.out.println(arrayDeque.removeFirst()); // 10 출력
System.out.println(arrayDeque.removeLast()); // 30 출력
// LinkedList 사용
Deque<Integer> linkedListDeque = new LinkedList<>();
// 데이터 삽입
linkedListDeque.addFirst(40);
linkedListDeque.addLast(50);
// 데이터 확인
System.out.println(linkedListDeque.peekFirst()); // 40 출력
System.out.println(linkedListDeque.peekLast()); // 50 출력
}
}1-2. Deque 개념과 구현 - Python
Python에서는 collections.deque 모듈을 사용하여 Deque를 구현할 수 있습니다.
- 이 자료구조는 Python의 표준 라이브러리에서 제공하며, 양방향에서 빠르게 데이터를 추가하거나 제거할 수 있는 효율적인 양방향 큐를 지원합니다.
collections.deque
- Python의
deque는 양방향 삽입과 삭제를 O(1)의 시간 복잡도로 처리할 수 있습니다. - 리스트(
list)와 달리 양쪽 끝에서의 삽입과 삭제가 매우 효율적으로 처리되며, 이는 스택과 큐의 기능을 모두 제공하기 위해 설계되었습니다. - Python의
deque는 원형 버퍼로 구현되어 있어 양방향 큐 연산이 모두 O(1) 시간 복잡도를 보장합니다. - 스레드 안전성을 제공하며, 멀티스레드 환경에서도 안전하게 사용할 수 있습니다.
1-2.1 Python Deque 주요 메서드
append(x): 덱의 뒤쪽에 데이터를 추가합니다.appendleft(x): 덱의 앞쪽에 데이터를 추가합니다.pop(): 덱의 뒤쪽에서 데이터를 제거하고 반환합니다.popleft(): 덱의 앞쪽에서 데이터를 제거하고 반환합니다.extend(iterable): 뒤쪽에 여러 데이터를 한 번에 추가합니다.extendleft(iterable): 앞쪽에 여러 데이터를 한 번에 추가합니다.rotate(n): 덱을n만큼 회전시킵니다. 양수는 오른쪽으로, 음수는 왼쪽으로 회전합니다.
1-2.2 Python Deque 코드 예시
from collections import deque
# deque 생성
d = deque()
# 데이터 삽입
d.append(10) # 뒤쪽에 삽입
d.appendleft(20) # 앞쪽에 삽입
d.append(30) # 뒤쪽에 삽입
# 데이터 확인
print(d[0]) # 20 출력 (덱의 맨 앞 요소)
print(d[-1]) # 30 출력 (덱의 맨 뒤 요소)
# 데이터 제거
print(d.popleft()) # 20 출력 (앞쪽에서 제거)
print(d.pop()) # 30 출력 (뒤쪽에서 제거)
# 덱 상태 출력
print(d) # deque([10])
1-2.3 Python Deque와 List의 차이
- 리스트(list)는 앞쪽에서 요소를 삽입하거나 삭제할 때 O(n)의 시간 복잡도가 발생합니다. 반면에,
deque는 양쪽 끝에서의 삽입과 삭제가 O(1)로 매우 효율적입니다.- 따라서, 양방향에서 삽입 및 삭제가 빈번한 상황에서는
deque가 훨씬 더 적합한 자료구조입니다.
- 따라서, 양방향에서 삽입 및 삭제가 빈번한 상황에서는
- 하지만 랜덤 접근(random access)이 필요한 경우, deque는 리스트보다 느릴 수 있습니다.
deque는 인덱스를 사용한 접근이 O(n)이기 때문입니다.
2. Deque 활용 사례
Deque는 큐와 스택의 모든 연산을 효율적으로 지원하기 때문에 다양한 알고리즘과 문제에서 유용하게 활용됩니다. 아래는 대표적인 활용 사례들입니다:
2.1 양방향 탐색 알고리즘
- BFS(너비 우선 탐색)나 DFS(깊이 우선 탐색)에서 큐나 스택을 사용해 탐색을 구현하는데,
Deque는 이 두 가지 모두를 지원하므로 양방향 탐색이 필요한 알고리즘에서 매우 효과적으로 사용할 수 있습니다. - 예를 들어, 최단 경로 탐색 문제에서 탐색의 양방향 처리가 필요할 경우
Deque를 사용하면 효율적으로 양쪽 끝에서 데이터를 처리할 수 있습니다.
2.2 캐시 구현 (LRU 캐시)
- LRU(Least Recently Used) 알고리즘에서 가장 최근에 사용된 데이터를 관리하는 데
Deque가 자주 사용됩니다.- 캐시에서 가장 오래된 데이터를 제거하고, 새로운 데이터를 추가하는 작업을 효율적으로 처리할 수 있습니다.
- Deque의
addFirst()와removeLast()메서드를 통해 캐시의 앞쪽에서 데이터를 추가하고, 뒤쪽에서 오래된 데이터를 제거하는 방식으로 동작합니다.
2.3 스케줄링 알고리즘
- 라운드 로빈 스케줄링이나 이중 방향 스케줄링에서도
Deque가 활용됩니다.- 예를 들어, 작업 큐에서 양쪽에서 작업을 추가하거나 제거해야 하는 경우에
Deque가 유용하게 사용됩니다.
- 예를 들어, 작업 큐에서 양쪽에서 작업을 추가하거나 제거해야 하는 경우에
2.4 문자열 회문 검사
Deque를 사용하여 문자열이 회문(앞뒤로 같은 문자열)인지 확인할 수 있습니다.- 문자열의 양 끝에서 한 글자씩 비교하면서 검사하는데, 이때
Deque의 양방향 접근이 매우 효율적입니다.
- 문자열의 양 끝에서 한 글자씩 비교하면서 검사하는데, 이때
from collections import deque
def is_palindrome(s):
d = deque(s)
while len(d) > 1:
if d.popleft() != d.pop():
return False
return True
print(is_palindrome("racecar")) # True
print(is_palindrome("hello")) # False2.5 슬라이딩 윈도우 최댓값 문제
- 슬라이딩 윈도우 알고리즘에서
Deque를 사용하여 윈도우 안의 최댓값을 구하는 문제를 효율적으로 해결할 수 있습니다.Deque를 사용하면 현재 윈도우 내에서 가장 큰 값을 빠르게 찾아낼 수 있습니다.
from collections import deque
def sliding_window_max(nums, k):
d = deque()
result = []
for i, n in enumerate(nums):
while d and nums[d[-1]] <= n:
d.pop()
d.append(i)
if d[0] == i - k:
d.popleft()
if i >= k - 1:
result.append(nums[d[0]])
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7]
k = 3
print(sliding_window_max(nums, k)) # [3, 3, 5, 5, 6, 7]3. Deque의 시간 및 공간 복잡도
Deque는 연속된 배열 또는 연결 리스트를 기반으로 구현되어, 대부분의 연산들이 상수 시간에 처리됩니다.
Deque의 연산들은 양방향 큐의 특성 덕분에 삽입/삭제/조회 모두 상수 시간 복잡도를 가집니다.- 이는 큐나 스택보다 유연하며, 삽입 및 삭제 연산에서 빠른 성능을 제공합니다.
3.1 큐 및 스택의 시간 복잡도 비교
Deque는 큐와 스택의 기능을 모두 제공하는 자료구조로, 그 연산들은 모두 상수 시간 복잡도를 보장합니다.
큐와 스택의 주요 연산과 Deque의 시간 복잡도를 비교해 보면 다음과 같습니다:
| 자료구조 | 삽입 연산 | 삭제 연산 | 조회 연산 |
|---|---|---|---|
| Queue (FIFO) | O(1) | O(1) | O(1) |
| Stack (LIFO) | O(1) | O(1) | O(1) |
| Deque | O(1) | O(1) | O(1) |
3.2 공간 복잡도
Deque의 공간 복잡도는 저장하는 데이터의 개수에 비례하여 O(n)입니다.
- 배열 기반 Deque는 크기가 커질 때 메모리를 재할당해야 할 수 있지만, 이는 대부분의 경우 빠르게 처리됩니다.
- 연결 리스트 기반 Deque는 각 노드가 추가적인 메모리 공간을 필요로 하지만, 크기 조절이 자연스럽게 이루어집니다.
마무리
이번 포스팅에서는 Deque(더블 엔디드 큐) 자료구조의 개념과 구현 방법을 Java와 Python에서 각각 살펴보았습니다.
Deque는 큐와 스택의 기능을 모두 제공하면서도 더 유연한 자료구조로, 다양한 프로그래밍 문제에서 중요한 역할을 합니다.- Java에서는
ArrayDeque와LinkedList를 사용하여Deque를 구현할 수 있으며, 성능 면에서는ArrayDeque가 더 효율적이기 때문에 더 많이 사용됩니다. - Python에서는
collections.deque를 사용하여 양방향 큐 연산을 매우 효율적으로 처리할 수 있으며, 스레드 안전성도 지원합니다.
- Java에서는
다음 포스팅에서는 선형 자료구조 중 Hash를 기반으로 동작하는 Hashtable에 대해서 다뤄보려 합니다.
일 때문에 포스팅은 잠시 쉬어요 ㅠ 바쁘다 바빠 모두들 화이팅! // Machine Learning (AI) Engineer & BackEnd Engineer (Entry)