[자료구조] 덱(Deque) 개념 및 코드

 

오늘은 자료구조 중 하나인 덱(Deque)에 대해 알아보겠습니다.

덱은 스택, 큐와 아주 유사한 자료구조이며, 스택/큐의 단점을 보완하고 장점을 가져왔기 때문에 유용하게 쓰입니다.

 

 

목차

📃 덱(Deque) 개념

📃 덱(Deque) 코드

📃 덱(Deque) 예제

 

 

 

덱(Deque) 개념

 

📌 정의

덱은 스택/큐와 같은 일차원의 선형 자료구조입니다.

스택과 큐 연산을 모두 지원하기에, 양 끝에서 삽입과 삭제가 가능한 자료구조입니다. 내부가 double-linked list(양방향 연결 리스트)로 구현되어 있습니다.

 

 

 

📌 시간 복잡도 O(1)

양방향 연결 리스트로 구현되어 있어, 양 끝 요소의 추가/삭제가 O(1)를 만족합니다.

그에 반해 List는 고정된 사이즈의 메모리를 갖는 배열로, 첫 번째 요소를 삭제하면 모든 원소가 앞으로 이동하기 때문에 시간 복잡도가 O(n)이 됩니다.

 

 

 

 

덱(Deque) 코드

 

 

📌 import deque

덱은 양방향 연결 리스트를 통해 직접 구현할 수도 있지만, 파이썬 자체에서 패키지를 지원합니다. collections 패키지에서 deque를 임포트 해줍니다. 또한 deque 객체를 생성해줍니다.

from collections import deque

dequeue = deque()

 

 

📌 Method

 

(1) 삽입 - append(x), appendleft(x)

append()는 뒤로 삽입하며, appendleft()는 앞으로 삽입합니다.

dequeue.append('a')
# dequeue = ['a']


dequeue.appendleft('b')
# dequeue = ['b','a']

 

 

(2) 추출 - pop(), popleft()

pop()은 맨 오른쪽의 요소를 삭제하고,  popleft()는 맨 왼쪽의 요소를 삭제합니다. 요소가 없으면 IndexError가 발생합니다.

# dequeue = ['a', 'b', 'c', 'd']


dequeue.pop()
# dequeue = ['a', 'b', 'c']


dequeue.appendleft()
# dequeue = ['b', 'c']

 

 

(3) 모두 삭제 - clear()

덱에 있는 모든 요소를 삭제합니다.

# dequeue = ['a', 'b', 'c', 'd']


dequeue.clear()
# dequeue = []

 

 

(4) 개수 세기 - count(x)

덱에 있는 x의 개수를 셉니다.

# dequeue = ['a', 'b', 'c', 'd']


dequeue.count('a')
# 1

 

 

(5) 연속적 삽입 - extend(iterable), extendleft(iterable)

iterable 한 값을 넣으면, 해당 값의 요소들이 큐에 삽입됩니다. extend()는 오른쪽, extendleft()는 왼쪽에 삽입됩니다.

deque.extend('abcde')
# deque = ['a','b','c','d','e']


deque.extendleft('abcde')
# deque = ['e','d','c','b','a','a','b','c','d','e']

 

 

(6) 인덱스 반환 - index(x, start, stop)

x의 인덱스를 반환하는 함수입니다. start, stop 인수는 생략할 수 있습니다. start부터 찾기 시작하며, stop-1까지만 찾고 종료합니다.

# dequeue = [1,2,3,4,5,6]


dequeue.index(1)
# 0


dequeue.index(3, 2)
# 2


dequeue.index(3, 2, 3)
# index 2에서 찾기 시작해서, 3이 되기 전에 끝내겠다.
# ValueError : 3 is not in list

 

 

(7) 특정 위치에 삽입 - insert(location, x)

사용자가 원하는 장소(index)에 직접 x를 삽입할 수 있습니다.

# dequeue = [1,2,3,4]


dequeue.insert(2, 100)
# dequeue = [1,2,100,3,4]

 

 

(8) remove(x), reverse(), rotate(n) 

remove(x)는 처음으로 등장하는 x 요소를 삭제합니다.

reverse()는 deque를 거꾸로 재배치하는 함수입니다.

rotate(n)은 n만큼 deque를 오른쪽으로 회전하는 함수입니다.

 

 

 

 

 

지금까지 덱(deque) 개념과 코드에 대해 알아보았습니다.

고생하셨습니다.