CS학습2026년 8월 16일

Deque: 양쪽 끝에서 삽입/삭제가 모두 효율적인 자료구조

Deque는 Double-ended Queue의 약자로, 배열이나 연결 리스트를 사용하여 구현할 수 있다. 스택과 큐의 특징을 모두 가지며, 양쪽 끝에서 O(1) 시간 복잡도로 데이터에 접근하고 수정할 수 있다는 장점이 있다. 따라서 다양한 상황에서 유연하게 활용될 수 있는 자료구조이다.

송민성3분 읽기

1. 개념

Deque (Double-ended Queue)는 양쪽 끝(front와 rear)에서 삽입과 삭제가 모두 가능한 추상 데이터 타입(Abstract Data Type)이다. 일반적인 Queue는 한쪽 끝에서만 삽입/삭제가 가능하고, Stack은 LIFO(Last In First Out) 방식으로 작동하지만, Deque는 이러한 제약 없이 양방향으로 접근이 가능하다.

2. 왜 사용하는가

유연성: 스택과 큐의 기능을 모두 제공하므로 상황에 따라 적절하게 활용할 수 있다.
효율적인 연산: 양 끝에서의 삽입/삭제는 O(1) 시간 복잡도로 매우 빠르다.
문제 해결: 특정 알고리즘이나 문제 해결 시 효율적인 자료구조로 활용될 수 있다 (예: sliding window maximum).

3. 동작 원리

Deque는 일반적으로 배열 또는 연결 리스트를 사용하여 구현된다.

배열 기반 Deque: 고정된 크기의 배열을 사용하며, front와 rear 포인터를 관리하여 데이터의 삽입/삭제 위치를 추적한다. 배열이 가득 차면 확장이 필요하다.
연결 리스트 기반 Deque: 각 노드가 데이터를 저장하고 다음 노드를 가리키는 방식으로 구현된다. 배열 기반보다 유연하지만, 추가적인 메모리 공간을 사용한다.

4. 코드 예제

python

class Deque:
    def __init__(self):
        self.items = []

    def is_empty(self):
        return len(self.items) == 0

    def add_front(self, item):
        self.items.insert(0, item)

    def add_rear(self, item):
        self.items.append(item)

    def remove_front(self):
        if not self.is_empty():
            return self.items.pop(0)
        else:
            return None # or raise an exception

    def remove_rear(self):
        if not self.is_empty():
            return self.items.pop()
        else:
            return None # or raise an exception

    def size(self):
        return len(self.items)

# 사용 예시
d = Deque()
d.add_rear(4)
d.add_rear('dog')
d.add_front('cat')
d.add_front(True)
print(d.size())  # Output: 4
print(d.remove_rear()) # Output: dog
print(d.remove_front()) # Output: True

5. 시간 복잡도 또는 성능 특성

| 연산 | 배열 기반 | 연결 리스트 기반 | | ----------- | -------- | ------------- | | add_front | O(n) | O(1) | | add_rear | O(1) | O(1) | | remove_front| O(n) | O(1) | | remove_rear | O(1) | O(1) |

배열 기반: add_front 및 remove_front 연산은 배열의 모든 요소를 이동해야 하므로 O(n)의 시간 복잡도를 가진다. 배열이 가득 차면 재할당이 필요하므로 추가적인 비용이 발생할 수 있다.
연결 리스트 기반: 모든 연산이 O(1)의 시간 복잡도를 가지지만, 추가적인 메모리 공간을 사용한다.

6. 실무 사용 사례

웹 브라우저 히스토리: 뒤로 가기/앞으로 가기 기능 구현에 활용될 수 있다.
Undo/Redo 기능: 편집기의 undo 및 redo 기능을 구현하는 데 사용될 수 있다.
Sliding Window Maximum: 배열에서 특정 크기의 윈도우 내 최대값을 찾는 알고리즘에 효율적으로 사용될 수 있다. (O(n) 시간 복잡도)

7. 주의할 점

배열 기반 Deque의 확장: 배열이 가득 차면 확장이 필요하며, 이 과정에서 성능 저하가 발생할 수 있다.
메모리 관리: 연결 리스트 기반 Deque는 메모리를 동적으로 할당하므로, 메모리 누수가 발생하지 않도록 주의해야 한다.

8. 핵심 정리

Deque는 양쪽 끝에서의 삽입/삭제 연산이 효율적인 자료구조이며, 스택과 큐의 기능을 모두 제공한다. 배열 또는 연결 리스트를 사용하여 구현할 수 있으며, 각 구현 방식은 성능 특성이 다르므로 상황에 맞게 선택해야 한다. 실무에서는 웹 브라우저 히스토리, Undo/Redo 기능, Sliding Window Maximum 등 다양한 분야에서 활용된다.