덱 (Deque)

덱 (Deque) 자료 구조

덱(Deque, Double-Ended Queue)은 큐와 스택의 특성을 모두 가지고 있으며, 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조이다. 덱은 다음과 같은 두 가지 유형이 있다.

1. 입력 제한 덱 (Input-Restricted Deque): 한쪽 끝에서만 삽입이 가능하고, 양쪽 끝에서 삭제가 가능하다.
2. 출력 제한 덱 (Output-Restricted Deque): 양쪽 끝에서 삽입이 가능하고, 한쪽 끝에서만 삭제가 가능하다.

덱의 주요 연산

덱은 다음과 같은 주요 연산을 지원한다.

1. Add to Front (addFront): 덱의 앞쪽 끝에 요소를 추가한다.
2. Add to Rear (addRear): 덱의 뒤쪽 끝에 요소를 추가한다.
3. Remove from Front (removeFront): 덱의 앞쪽 끝에서 요소를 제거하고 반환한다.
4. Remove from Rear (removeRear): 덱의 뒤쪽 끝에서 요소를 제거하고 반환한다.
5. Peek Front (peekFront): 덱의 앞쪽 끝에 있는 요소를 제거하지 않고 반환한다.
6. Peek Rear (peekRear): 덱의 뒤쪽 끝에 있는 요소를 제거하지 않고 반환한다.
7. isEmpty: 덱이 비어 있는지 확인한다.
8. isFull: 덱이 가득 찼는지 확인한다 (고정 크기의 덱인 경우).

덱의 활용 예

덱은 다양한 문제 해결에 유용하게 사용될 수 있다.

1. 슬라이딩 윈도우 문제 (Sliding Window Problems): 고정 크기의 창을 사용하여 배열이나 리스트의 부분 집합을 반복적으로 처리할 때 유용하다. 예를 들어, 최대 슬라이딩 윈도우 문제에서 덱을 사용하여 윈도우 내에서 최대값을 효율적으로 찾을 수 있다.
2. 대기열 관리 (Queue Management): 덱은 양쪽 끝에서 삽입과 삭제가 가능하기 때문에 대기열 관리에 유연성을 제공한다. 예를 들어, 고객 서비스 대기열에서 새로 온 고객을 뒤에 추가하고, VIP 고객을 앞에 추가할 수 있다.
3. 이중 스택 (Double-Ended Stack): 덱은 큐와 스택의 기능을 모두 제공하기 때문에 이중 스택으로 사용할 수 있다. 예를 들어, 스택의 두 끝에서 데이터를 삽입하고 삭제하는 경우에 유용하다.
4. 캐시 구현 (Cache Implementation): 덱은 LRU (Least Recently Used) 캐시와 같은 캐시 알고리즘을 구현하는 데 사용될 수 있다. 가장 최근에 사용된 항목을 앞쪽에 추가하고, 가장 오래된 항목을 뒤쪽에서 제거할 수 있다.
5. 문자열 조작 (String Manipulation): 덱을 사용하여 문자열의 회문(팰린드롬) 여부를 확인하거나, 문자열을 뒤집는 등의 작업을 효율적으로 수행할 수 있다.

덱의 이론적 특성

1. 시간 복잡도: 덱의 주요 연산은 모두 평균적으로 O(1) 시간 복잡도를 가진다. 즉, 요소의 삽입과 삭제가 덱의 양쪽 끝에서 상수 시간 내에 이루어진다.
2. 공간 복잡도: 덱은 사용하는 데이터 구조에 따라 공간 복잡도가 결정된다. 배열 기반 덱은 고정된 크기의 배열을 사용하며, 연결 리스트 기반 덱은 동적 메모리 할당을 사용한다.
3. 데이터 순서: 덱은 요소를 양쪽 끝에서 삽입하고 삭제할 수 있기 때문에, 요소의 순서를 유연하게 관리할 수 있다. 이는 다양한 알고리즘과 문제 해결에 유용하게 사용될 수 있다.

덱의 구현 방식

배열 기반 덱:

• 장점: 인덱스를 통해 요소에 빠르게 접근할 수 있습니다.
• 단점: 크기가 고정되어 있으며, 크기를 초과하면 재할당이 필요합니다. 또한, 배열의 앞쪽 끝에서 요소를 삽입하거나 삭제할 때 요소들을 이동시켜야 합니다.

덱의 활용 예시: 슬라이딩 윈도우 최대값 문제

덱을 사용하여 슬라이딩 윈도우 최대값 문제를 해결하는 방법을 예로 들어보겠다. 주어진 배열과 윈도우 크기 k에 대해, 윈도우 내에서 최대값을 찾는 문제이다.

1. 배열의 처음부터 끝까지 순회하면서, 덱을 사용하여 현재 윈도우의 최대값을 유지한다.
2. 덱의 앞쪽에는 현재 윈도우 내의 최대값을 유지하고, 뒤쪽에는 나머지 값들을 유지한다.
3. 새로운 요소가 추가될 때마다 덱의 뒤쪽에서 현재 값보다 작은 값들을 제거한다.
4. 덱의 앞쪽에서 최대값을 유지한다.

이러한 방식으로 덱을 사용하여 슬라이딩 윈도우 내의 최대값을 효율적으로 찾을 수 있다.

 

구현 코드

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

    def isEmpty(self) -> bool:
        return len(self._values) == 0

    def addFront(self, value):
        self._values.insert(0, value)

    def addRear(self, value):
        self._values.append(value)

    def removeFront(self):
        if self.isEmpty():
            return None
        return self._values.pop(0)

    def removeRear(self):
        if self.isEmpty():
            return None
        return self._values.pop()

    def peekFront(self):
        if self.isEmpty():
            return None
        return self._values[0]

    def peekRear(self):
        if self.isEmpty():
            return None
        return self._values[-1]

    def __str__(self) -> str:
        return f"Deque: {self._values}"

deque = Deque()

# Add elements to the rear
deque.addRear(10)
deque.addRear(20)
deque.addRear(30)
print(deque)  # Deque: [10, 20, 30]

# Add elements to the front
deque.addFront(5)
deque.addFront(1)
print(deque)  # Deque: [1, 5, 10, 20, 30]

# Peek front and rear
print(deque.peekFront())  # 1
print(deque.peekRear())   # 30

# Remove elements from the front
print(deque.removeFront())  # 1
print(deque.removeFront())  # 5
print(deque)  # Deque: [10, 20, 30]

# Remove elements from the rear
print(deque.removeRear())  # 30
print(deque)  # Deque: [10, 20]

# Check if deque is empty
print(deque.isEmpty())  # False

# Remove remaining elements
deque.removeFront()
deque.removeFront()
print(deque)  # Deque: []
print(deque.isEmpty())  # Output: True

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms