[Python] Deque(덱/데크)

Deque(덱/데크, Double Ended Queue)

• Deque(덱/데크)는 데이터 값을 저장하는 기본적인 구조로, 일차원의 선형 자료구조이다.
• Deque(덱/데크)는 Stack(스택)과 Queue(큐)의 연산을 모두 지원한다.
• Deque(덱/데크)와 Queue(큐)의 차이점
  • Queue(큐)는 FIFO(선입선출) 방식이다.
  • 이때, 양방향 Queue(큐)를 Deque(덱/데크)라고 한다.
  • 따라서 Deque(덱/데크)는 양쪽 방향에서 element를 추가하고 제거할 수 있다.
    
    • 양방향 연결리스트(Doubly Linked List)로 구성되어 있다.
• Deque(덱/데크)의 장점
  • 양 끝 element의 append와 pop이 압도적으로 빠르다.
  • container(컨테이너)의 양 끝 element에 접근하여 삽입이나 삭제를 하는 경우, 아래와 같이 Deque(덱/데크)을 사용하는 것이 아주 효율적이다.   

    일반 리스트(list)	Deque(덱/데크)
    O(n)	O(1)

  • 대부분의 경우, Deque(덱/데크)는 list(리스트) 보다 월등한데, 특히 push/pop 연산이 빈번하게 발생하는 알고리즘에서 월등한 속도를 보여준다.

Deque(덱/데크) 사용법

• 아래 코드와 같이 import하여 사용한다.

from collections import deque

d = deque()

• Deque(덱/데크)의 method(메소드)
  • deque.append(item) : item을 데크의 오른쪽 끝에 삽입한다.
  • deque.appendleft(item) : item을 데크의 왼쪽 끝에 삽입한다.
  • deque.pop() : 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
  • deque.popleft() : 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
  • deque.extend(array) : 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
  • deque.extendleft(array) : 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
  • deque.remove(item) : item을 데크에서 찾아 삭제한다.
  • deque.rotate(num) : 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).
• method(메서드) 사용법에 대해서는 백준 덱 문제 풀이를 함께 보면 쉽게 이해할 수 있다.
• method(메서드) 중 rotate() 사용은 아래 코드와 같다.

d = deque([1, 2, 3, 4, 5])

d.rotate(1)
print(d) # 5, 1, 2, 3, 4

d.rotate(-1)
print(d) # 1, 2, 3, 4, 5

https://techblogs.tistory.com/68

[Algorithm] 백준 10866번 덱 (Python)