덱
덱 (Deque)
덱(Deque)은 'Double-ended Queue'의 줄임말로, 큐의 양쪽 끝(front, rear)에서 모두 데이터의 삽입(enqueue)과 삭제(dequeue)가 가능한 자료구조입니다. 스택과 큐의 특징을 모두 가지고 있어, 두 자료구조의 기능을 포함하는 더 유연한 활용이 가능합니다.
↔️ 덱의 특징과 주요 연산
- 개념 (Concept) : 스택처럼 LIFO(후입선출) 방식으로도, 큐처럼 FIFO(선입선출) 방식으로도 동작할 수 있는 일반화된 자료구조입니다.
- 주요 연산 (Operations)
> * `addFirst(item)`: 덱의 가장 앞부분에 데이터를 추가합니다. > * `addLast(item)`: 덱의 가장 뒷부분에 데이터를 추가합니다. > * `removeFirst()`: 덱의 가장 앞부분에서 데이터를 제거하고 반환합니다. > * `removeLast()`: 덱의 가장 뒷부분에서 데이터를 제거하고 반환합니다. > * `getFirst()`: 덱의 가장 앞부분에 있는 데이터를 제거하지 않고 확인합니다. > * `getLast()`: 덱의 가장 뒷부분에 있는 데이터를 제거하지 않고 확인합니다.
🛠️ 덱의 구현 방법
- 이중 연결 리스트 (Doubly Linked List)
> * '방식': 각 노드가 이전 노드와 다음 노드를 모두 가리키는 이중 연결 리스트를 사용하여 구현하는 것이 가장 일반적입니다. > * '이유': 양쪽 끝 노드에 대한 참조(head, tail)를 유지하면, 양 끝에서의 삽입/삭제 연산을 모두 O(1)의 시간 복잡도로 수행할 수 있습니다.
- 동적 배열 (Dynamic Array / Circular Array)
> * '방식': 배열을 원형으로 사용하여 구현합니다. 배열의 시작과 끝이 연결되어 있다고 가정하고, front와 rear 포인터를 이동시킵니다. > * '이유': 배열의 끝에 도달했을 때 다시 앞으로 돌아와 빈 공간을 활용할 수 있어 공간 효율성이 좋습니다. 하지만 배열이 가득 차면 리사이징(resizing)이 필요하여 일시적인 성능 저하가 발생할 수 있습니다.
💡 개발자 핵심 Point
- 덱은 스택과 큐의 기능을 모두 포함하는 유연한 자료구조로, 복잡한 알고리즘 문제에서 유용하게 사용됩니다.
- 활용 사례
> * 슬라이딩 윈도우 최솟값/최댓값 찾기 : 특정 크기의 윈도우를 이동시키면서, 윈도우 내의 최솟값이나 최댓값을 O(1)에 찾을 수 있습니다. 덱에는 원소의 인덱스나 값을 저장하며, 특정 규칙에 따라 양 끝에서 원소를 제거/추가합니다. > * 웹 브라우저의 앞으로 가기/뒤로 가기 : 이중 연결 리스트로 구현된 덱을 사용하면 양방향 탐색을 효율적으로 구현할 수 있습니다. > * 작업 훔치기 (Work Stealing) 스케줄링 : 멀티스레드 환경에서, 특정 스레드가 자신의 작업 큐를 모두 처리했을 때 다른 스레드의 덱(작업 큐)의 뒤쪽(가장 오래된 작업)부터 작업을 '훔쳐와' 처리함으로써 전체 시스템의 처리량을 높입니다.
- 대부분의 언어에서 표준 라이브러리로 제공됩니다. (e.g., Java의 `ArrayDeque`, `LinkedList`, Python의 `collections.deque`)
