deque는 Double-Ended Queue의 약자로, 양쪽 끝에서 삽입과 삭제가 모두 가능한 큐 자료구조이다. 파이썬에서는 collections 모듈에서 deque를 제공하며, 리스트보다 효율적으로 양쪽 끝에서 삽입과 삭제 작업을 처리할 수 있다. 특히, 큐 및 스택을 구현할 때 많이 사용된다.

• 본 페이지는 자료구조 큐에 대해 다루는 페이지 입니다. 자료구조 큐에 대한 내용은 아래 페이지를 참고 하길 바랍니다.

  Queue

리스트로 구현할 때의 문제점

• 리스트의 경우 pop(0)과 같은 작업을 구행할때 리스트의 값을 한칸씩 앞으로 가지고 오기 때문에 O(n)의 시간이 걸려서 리스트의 크기가 커지면 연산에 많은 시간이 소요될 수 있다.

deque로 구현할 때의 장점

• 기존 리스트에서 pop과 동일한 연산을 하는 deque의 popleft 함수는 O(1)의 시간에 수행된다는 장점이 있다.
• 또한 양방향 뎅이터를 처리할 수 있어, 큐뿐만 아니라 스택으로도 사용할 수 있다.
• 내부적으로 이중 연결 리스트로 구현되어 있어, 중간에서 접근은 느리지만 양 끝에서의 연산이 빠르다.

deque의 함수들

• append(x): x를 오른쪽 끝에 추가.
• appendleft(x): x를 왼쪽 끝에 추가.
• pop(): 오른쪽 끝에서 요소를 제거하고 반환.
• popleft(): 왼쪽 끝에서 요소를 제거하고 반환.