Python Language
Deque 모듈

통사론

• dq = deque () # 빈 양단 큐를 생성합니다.
• dq = deque (iterable) # 일부 요소로 deque를 생성합니다.
• dque.append (object) # 객체를 양단 큐의 오른쪽에 추가합니다.
• dque.appendleft (object) # 객체를 양면 큐의 왼쪽에 추가합니다.
• dq.pop () -> object # 가장 오른쪽에있는 객체를 제거하고 반환합니다.
• dq.popleft () -> object # 가장 왼쪽에있는 객체를 제거하고 반환합니다.
• dque.extend (iterable) # 큐의 오른쪽에 몇 개의 엘리먼트를 추가한다.
• dque.extendleft (iterable) # 일부 요소를 양면 큐의 왼쪽에 추가합니다.

매개 변수

비고

다음을 사용하는 기본 deque

이 클래스에서 유용한 주요 메소드는 popleft 와 appendleft

from collections import deque

d = deque([1, 2, 3])
p = d.popleft()        # p = 1, d = deque([2, 3])
d.appendleft(5)        # d = deque([5, 2, 3])

deque 크기 제한

양단 큐를 생성 할 때 maxlen 매개 변수를 사용하여 양단 큐의 크기를 제한하십시오.

from collections import deque
d = deque(maxlen=3)  # only holds 3 items
d.append(1)  # deque([1])
d.append(2)  # deque([1, 2])
d.append(3)  # deque([1, 2, 3])
d.append(4)  # deque([2, 3, 4]) (1 is removed because its maxlen is 3)

양단 큐에 사용할 수있는 메서드

빈 양단 큐 생성하기 :

dl = deque()  # deque([]) creating empty deque

일부 요소로 deque 만들기 :

dl = deque([1, 2, 3, 4])  # deque([1, 2, 3, 4])

deque에 요소 추가하기 :

dl.append(5)  # deque([1, 2, 3, 4, 5])

deque의 왼쪽 요소 추가하기 :

dl.appendleft(0)  # deque([0, 1, 2, 3, 4, 5])

deque에 요소 목록 추가 :

dl.extend([6, 7])  # deque([0, 1, 2, 3, 4, 5, 6, 7])

왼쪽에서 요소 목록 추가 :

dl.extendleft([-2, -1])  # deque([-1, -2, 0, 1, 2, 3, 4, 5, 6, 7])

.pop() 요소를 사용하면 자연스럽게 오른쪽에서 항목이 제거됩니다.

dl.pop()  # 7 => deque([-1, -2, 0, 1, 2, 3, 4, 5, 6])

.popleft() 요소를 사용하여 왼쪽에서 항목을 제거하려면 :

dl.popleft()  # -1 deque([-2, 0, 1, 2, 3, 4, 5, 6])

해당 값으로 요소 제거 :

dl.remove(1)  # deque([-2, 0, 2, 3, 4, 5, 6])

deque의 요소 순서를 바꿉니다.

dl.reverse()  # deque([6, 5, 4, 3, 2, 0, -2])

폭스 퍼스트 검색

Deque는 빠른 대기열 작업 이있는 유일한 Python 데이터 구조입니다. (주 queue.Queue 이 스레드 간의 통신을 의미이기 때문에, 일반적으로 적합하지 않습니다.) 큐의 기본 사용 사례가있다 폭 첫 번째 검색 .

from collections import deque

def bfs(graph, root):
    distances = {}
    distances[root] = 0
    q = deque([root])
    while q:
        # The oldest seen (but not yet visited) node will be the left most one.
        current = q.popleft()
        for neighbor in graph[current]:
            if neighbor not in distances:
                distances[neighbor] = distances[current] + 1
                # When we see a new node, we add it to the right side of the queue.
                q.append(neighbor)
    return distances

우리가 간단한 그래프를 가지고 있다고 가정 해보십시오 :

graph = {1:[2,3], 2:[4], 3:[4,5], 4:[3,5], 5:[]}

이제 시작 위치에서 거리를 찾을 수 있습니다.

>>> bfs(graph, 1)
{1: 0, 2: 1, 3: 1, 4: 2, 5: 2}

>>> bfs(graph, 3)
{3: 0, 4: 1, 5: 1}