[자료구조] Deque와 파이썬의 collections

✔ 덱(deque)이란?

double ended: 양 끝이 닮은, 앞뒤가 없는..이라는 뜻이다. 

따라서 데큐는 양 끝 모두가 출입구가 되므로, 양방향으로 push&pop이 가능하다. (stack은 한쪽으로만 입출력!)

데큐는 큐의 일종으로, FIFO(First In First Out: 먼저 넣은 데이터가 먼저 나오는) 구조이다.

선착순을 떠올리면 직관적으로 이해할 수 있다.

---

📝 덱(deque)의 성질

덱은 가장 앞부분을 가리키는 front와 가장 뒷부분을 가리키는 back이 구성되어있다.

따라서

• push_front
• push_back,
• pop_front
• pop_back

을 모두 활용할 수 있다!!

데큐를 쓰는 이유는 https://wiki.python.org/moin/TimeComplexity 를 읽어보면 시간 복잡도 차이가 많이 난다.

한줄로 요약하자면 list는 원소 삽입, 삭제에 O(n) 시간이 걸리고 deque는 O(1) or O(k)로 상수 시간이 걸린다.

이는 list 혹은 deque의 크기가 커질 수록 프로그램 전체에 영향을 크게 미치기 때문에, 유용한 자료구조인 deque를 사용한다.

---

💻 덱(deque) 구현

구현에 앞서, 기본적인 메소드를 정리해보자.

appendleft() : 덱(deque)의 가장 앞에 원소를 추가. 원소값을 입력값으로 받을 수 있다.

append() : list의 append와 똑같이 기능한다. 오른쪽(가장 뒤쪽)에 원소를 추가한다.

popleft() : 덱(deque)의 가장 앞의 원소를 제거한다. 입력값으로 아무 인자도 받지 않는다! *주의*

pop() : stack의 pop과 똑같다. 마지막 원소를 제거한다.

+ 덱(deque)는 list와 같이 인덱스를 활용할 수 있다.

---

- 덱(deque) 호출, 선언

from collections import deque
deck = deque()

첫번째 코드는 collections라는 모듈에서 deque 라이브러리를 불러와서 사용한다는 뜻이다. 

collections는 파이썬의 다양하고 유용한 기능들이 들어있는 모듈이다.

 

- 전체 코드

import sys
from collections import deque

n = int(sys.stdin.readline())
deck = deque()

for _ in range(n):
    words = sys.stdin.readline().split()
    command = words[0]

    if command == 'push_front':
        deck.appendleft(words[1]) # appendleft

    elif command == 'push_back':
        deck.append(words[1])

    elif command == 'pop_front':
        if len(deck) != 0:
            print(deck[0])
            deck.popleft() # popleft
        else:
            print(-1)

    elif command == 'pop_back':
        if deck:
            print(deck[-1])
            deck.pop()
        else:
            print(-1)

    elif command == 'size':
        print(len(deck))

    elif command == 'empty':
        if len(deck) == 0:
            print(1)
        else:
            print(0)

    elif command == 'front':
        if deck:
            print(deck[0]) 
        else:
            print(-1)
    
    elif command == 'back':
        if deck:
            print(deck[-1]) 
        else:
            print(-1)