[데이터 구조와 활용] 덱

1. 덱

 (1) Deque 이란

  : 양 쪽 끝에서 삽입과 삭제가 가능한 선형 데이터 구조 (큐나 스택보다 유연함)

  - 덱의 주요 연산

연산	설명	시간복잡도
push_front(x)	덱의 앞쪽에 x 추가	O(1)
push_back(x)	덱의 뒷쪽에 x 추가	O(1)
pop_front()	덱의 앞쪽 원소 제거	O(1)
pop_back()	덱의 뒷쪽 원소 제거	O(1)
front()	덱의 맨 앞 원소 확인	O(1)
back()	덱의 맨 뒤 원소 확인	O(1)
is_empty()	덱이 비어있는지 확인	O(1)

(2) 덱의 활용 사례

  - 웹 브라우저 앞뒤 이동 기능

  - Palindrome(회문) 검사 > 괄호 검사

2. 덱 구현

(1) 리스트를 사용한 덱 구현

deque = [] deque.append(10) deque.append(20) deque.append(30) print(deque)  # 10 20 30 deque.insert(0, 40) deque.insert(0, 50) print(deque) # 50 40 10 20 30 pitem = deque.pop() print(pitem) # 30 print(deque) # 50 40 10 20  pitem = deque.pop(0) print(pitem) # 50 print(deque) # 40 10 20

 * 문제점 : insert 및 pop(0)의 경우 모두 O(n)의 시간 복잡도 소요

(2) 순환 덱

 - 배열의 크기를 초과하지 않으면서 원소를 효율적으로 추가 및 제거 할 수 있다

 - front와 rear를 조정하려 리스트와 처음과 끝이 연결되어있는 것처럼 동작함

size = 5 deque = [None] * size front, rear = 0, 0 deque[rear] = 10 rear = ( rear+1) % size deque[rear] = 20 rear = ( rear+1) % size print(deque) # 10 20 none none none front = (front -1 _ size) % size deque[front] = 30 print(deque) # 10 20 none none 30 rear = (rear -1 + size) % size deque[rear] = None print(deque) # 10 None None None 30 deque[front]  = None front = (front +1)%size print(deque) # 10 None None None None

 * 인덱스를 사용하는 순환 덱을 사용할 경우 입출력 및 len 확인, 최단값 확인 모두 시간 복잡도 O(1)로 변경됨

3. 덱 활용

 - collections.deque를 활용 [ append, appendleft, pop, popleft ]

 - deque가 list보다 빠른 이유 : insert(0, x)나 pop(0)에 시간복잡도가 O(n)인 리스트에 비해

                                              연결 리스트 기반으로 모든 입출력을 O(1)로 맞춘 deque가 빠르게 작동함

(1) BOJ28279

import collections import sys input = sys.stdin.readline n = int(input()) q = collections.deque() for _ in range(n):     data = list(map(int, input().split()))     if data[0] == 1 :         q.appendleft(data[1])     elif data[0] == 2 :         q.append(data[1])     elif data[0] == 3 :         if len(q) == 0 :             print(-1)         else :             print(q.popleft())     elif data[0] == 4 :         if len(q) == 0 :             print(-1)         else :             print(q.pop())     elif data[0] == 5 :         print(len(q))     elif data[0] == 6 :         if len(q) == 0 :             print(1)         else :             print(0)     elif data[0] == 7 :         if len(q) == 0 :             print(-1)         else :             print(q[0])     elif data[0] == 8 :         if len(q) == 0 :             print(-1)         else :             print(q[-1])

(2) BOJ6119

import collections import sys input = sys.stdin.readline n = int(input()) q = collections.deque() i = 1 for _ in range(n):     data = list(input().split())     if data[0] == 'A' :         if data[1] == 'L' :             q.appendleft(i)             i += 1         else :             q.append(i)             i += 1     elif data[0] == 'D' :         if data[1] == 'R' :             for _ in range(int(data[2])) :                 q.pop()         else :             for _ in range(int(data[2])) :                 q.popleft() for x in q :     print(x)

(3) BOJ2346 

import collections import sys input = sys.stdin.readline n = int(input()) l = list(map(int, input().split())) q = collections.deque() for i in range(1,n+1) :     q.append((i,l[i-1])) for _ in range(n) :     if len(q) == 0 :         break     else :         (res, des) = q.popleft()         print(res, end =" ")     if des > 0 :         for i in range(des-1) :             if len(q) == 0 :                 break             x, mid = q.popleft()             q.append((x, mid))     else :         for i in range(des*(-1)) :             if len(q) == 0 :                 break             x, mid = q.pop()             q.appendleft((x, mid))