[자료구조] Deque (데크) - 정의, 예제, 시간복잡도, 장단점

# 자료구조 시리즈

1. Array (배열)
2. Linked List (연결 리스트)
3. Stack (스택)
4. Queue (큐)
5. Tree (Binary / Segment)
6. Graph (그래프)
7. Deque (데크)
8. Heap (힙)
9. Trie (트라이)

---

자료구조(Data Structure)에서는 자료에 효율적으로 접근하고 수정할 수 있도록, 데이터를 구성하고 저장하는 방법을 공부합니다. 자료구조는 데이터의 형태에 따라 크게 선형과 비선형으로 구분됩니다. 선형 자료구조는 데이터가 일렬로 나열되어 있는 반면, 비선형 자료구조는 데이터가 특정한 형태를 띄고 있다는 것이 핵심입니다. 전자의 예시로는 Array, Linked List, Stack, Queue 등이 있으며 후자에는 Tree, Graph 등이 있습니다.

 

Deque (데크)

---

1. 정의

// Java
Deque<Integer> deque = new LinkedList<>();

 

  Deque(데크)는 Double-ended Queue의 줄임말로, 앞과 뒤 모든 방향에서 데이터를 처리할 수 있는 양방향 자료구조입니다. 구현에 따라 Stack(LIFO) 또는 Queue(FIFO)로도 사용할 수 있고 구현체로 ArrayDeque, LinkedList가 있습니다. 선입선출 방식으로 작동하는 Queue가 양쪽에서 원소를 삽입/삭제 가능하다고 보면 됩니다. 따라서 push/pop 연산이 빈번한 알고리즘에서 List에 비해 훨씬 빠른 속도를 보여줍니다. 또한 Stack에서는 오래된 프로세스, Queue에서 최근에 들어온 프로세스에 우선순위를 주는 것이 불가능한데 Deque에서는 모두 가능하다는 이점을 갖습니다.

https://itchbo.tistory.com/113

 

  Python에서는 collections 패키지에 deque 라이브러리가 포함되어 있습니다.

# Python

from collections import deque

queue = deque()

## append(x): 큐의 뒤로 삽입
queue.append('b') # queue = ['b']
queue.append('c') # queue = ['b', 'c']

## appendleft(x): 큐의 앞으로 삽입
queue.appendleft('a') # queue = ['a', 'b', 'c']

## copy(): 얕은 복사
copied_queue = queue.copy() # copied_queue = ['a', 'b', 'c']

## extend(iterable): iterable한 값들이 하나씩 큐의 오른쪽에 append
queue.extend('lft') # queue = ['a', 'b', 'c', 'l', 'f', 't']

## index(x, start: int): start 위치로부터 x 위치를 반환
print(queue.index('b', 1)) # 4
print(queue.index('b', 3, 4)) # ValueError: 'b' is not in deque

## clear(): 큐의 모든 요소를 삭제
queue.clear() # queue = []

 

  Java에서의 Deque는 Interface(인터페이스)로 구현되어 있습니다. Deque 자료구조의 메소드를 정의한 인터페이스를 구현한 클래스로는 ArrayDeque, LinkedList, LinkedBlockingDeque, ConcurrentLinkedDeque, LinkedList 등이 있습니다.

 

Deque 인터페이스의 메소드

 1) addFirst
  - Deque 앞에 원소 삽입
  - Deque를 Stack으로 사용할 때 push 명령어와 동일
  - 용량 제한 시 Exception 발생

 2) offerFirst
  - Deque 앞에 원소 삽입
  - 정상적으로 삽입되면 true, 용량 제한 등 실패 시 false 반환

 3) addLast (= add)
  - Deque 뒤에 원소 삽입
  - 용량 제한 시 Exception 발생

 4) offerLast (= offer)
  - Deque 뒤에 원소 삽입
  - 정상적으로 삽입되면 true, 용량 제한 등 실패 시 false 반환 

 5) removeFirst
  - Deque 앞에서 원소를 추출하여 반환하고, 해당 원소를 Deque에서 제거
  - Deque를 Stack으로 사용할 때 pop 명령어와 동일
  - 빈 Deque는 Exception 발생

 6) pollFirst
  - Deque 앞에서 원소를 추출하여 반환하고, 해당 원소를 Deque에서 제거
  - 빈 Deque는 null 반환

 7) removeLast (= remove)
  - Deque 뒤에서 원소를 추출하여 반환하고, 해당 원소를 Deque에서 제거
  - 빈 Deque는 Exception 발생

 8) pollLast (= poll)
  - Deque 뒤에서 원소를 추출하여 반환
  - 빈 Deque는 null 반환

 9) getFirst
  - Deque 앞에서 원소를 추출하여 반환
  - 빈 Deque는 Exception 발생

 10) peekFirst
  - Deque 앞에서 원소를 추출하여 반환
  - 빈 Deque는 null 반환

 11) getLast (= get)
  - Deque 뒤에서 원소를 추출하여 반환
  - 빈 Deque는 Exception 발생

 12) peekLast (= peek)
  - Deque 뒤에서 원소를 추출하여 반환
  - 빈 Deque는 null 반환

 

* Deque 자료구조를 순회하는 방법은 아래처럼 가능합니다.

// Java

// for문
for (String e : deque1) {
  System.out.println(e);
}

// Iterator
Iterator<String> iterator = deque1.iterator();
while (iterator.hasNext()) {
  Stirng e = iterator.next();
  System.out.println(e);
}

// reverseIterator
Iterator<String> reverseIterator = deque1.descendingIterator();
while (reverseIterator.hasNext()) {
  String e = reverseIterator.next();
  System.out.println(e);
}

반응형

---

2. Deque의 시간복잡도

1. 삽입/삭제
 - 원소를 앞/뒤에 삽입/삭제하는 경우 O(1)

2. 탐색
 - 원소를 탐색하는 경우 index를 통해 접근할 수 있으므로 O(1)

 * Array를 사용하여 구현한 ArrayDeque는 LinkedList를 이용했을 때보다 캐시 효율이 높고, Random Access 시의 속도가 빠르다고 합니다. 하지만 Array는 크기 제한이 있기 때문에 Linked List를 사용하면 Deque의 길이가 가변적인 경우, 앞뒤에서 삽입/삭제가 빈번할 때 자료구조를 재정의할 필요가 없습니다. 

 

* 일반적으로 Stack은 순차적으로 데이터를 삽입/삭제하므로 Array 기반인 ArrayList 컬렉션 클래스로 의 구현이 적합하고 Queue는 데이터를 꺼낼 때 항상 제일 먼저 저장된 데이터를 삭제하기 때문에 데이터의 추가/삭제 시간복잡도가 O(1)인 Linked List가 적합합니다.

---

3. Deque의 장단점

  1) 장점

1. 공통
 - 자료구조의 앞/뒤에서 데이터를 삽입/삭제할 수 있어 효율적입니다.

2. ArrayDeque
 - 양 끝에서의 데이터 삽입/삭제 속도가 빠릅니다.
 - Array 기반이므로 Deque 내 원소 Random Access 속도가 빠릅니다.
 - LinkedList 기반에 비해 메모리 소비가 적습니다.

3. LinkedListDeque
 - 새로운 원소 삽입 시, 메모리를 재할당하지 않고 새로운 단위의 메모리 블록을 할당하여 삽입합니다.

---

   2) 단점

1. ArrayDeque
 - 양 끝이 아닌 곳에서의 삽입/삭제 속도가 List보다 느립니다.
 - 연속 메모리 공간이 아니기 때문에 원소들 간의 포인터 연산이 불가능합니다.
 - Deque 크기를 늘려야 하는 상황에서는 새로운 Array를 정의하여 원소를 복제해야 합니다.

2. LinkedListDeque
 - ArrayDeque에 비해 양끝에서의 데이터 삽입/삭제 속도가 느리고, 메모리 소비가 큽니다.
 - Deque 내 원소에 대한 Random Access 속도가 느립니다.

 

---

* 백준 문제(7576) 가운데, 익은 토마토를 아래처럼 Deque를 사용하여 풀 수 있지만 List에 담게 되면 시간 초과로 문제 풀이에 실패하게 됩니다.

 

from collections import deque


def solution(m, n, tomatoes):
    count = 0  # Count number of days
    deq = deque()
    # deq = list()
    D = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def search(row, col):
        searched_list = []

        for i, j in D:
            if (row + i < N and col + j < M) and (row + i >= 0 and col + j >= 0):
                if tomatoes[row + i][col + j] == 0:
                    tomatoes[row + i][col + j] = 1
                    searched_list.append((row + i, col + j))

        return searched_list

    # Add all riped tomatoes
    for r in range(N):
        for c in range(M):
            if tomatoes[r][c] == 1:
                deq.append((r, c))

    # Search begin
    while deq:
        for _ in range(len(deq)):
            r, c = deq.popleft()
            for tomato in search(r, c):
                deq.append(tomato)
        count += 1

    # Check unriped tomato(es) after search
    for r in range(N):
        for c in range(M):
            if tomatoes[r][c] == 0:
                return -1

    return count - 1


if __name__ == "__main__":
    M, N = map(int, input().split(" "))
    tomatoes = [[int(n) for n in input().split(" ")] for _ in range(N)]
    print(solution(M, N, tomatoes))

 

 

---

참고자료 
 - https://itchbo.tistory.com/113
 - https://yoongrammer.tistory.com/43
 - https://opentutorials.org/module/1335/8821 
 - https://code-lab1.tistory.com/2 
 - https://gitub.com/Seogeurim/CS-study

 

 

[GitHub] 깃허브 잔디 심는 법 - GitHub Contributions

[인공지능] 생성 모델 (Generative AI Model)이란? (1) : AutoEncoder, VAE, GAN

[Kubernetes] CKA(Certified Kubernetes Administration) 자격증 후기/접수 방법/출제 범위/할인바우처 (+CKAD, CKS