Python에서 Deque를 사용한 스택 및 대기열의 간단한 구현

2022년 8월 6일 https://rivea0.github.io/blog에서 원래 게시됨

abstract data types 중 이전에 접했을 가능성이 가장 높은 두 가지는 stacks 및 queues 입니다. 한 가지 중요한 측면은 스택의 경우 LIFO(후입선출), 대기열의 경우 FIFO(선입선출)와 같이 요소를 삽입하고 제거할 때 동작에 있어 각각의 원칙이 다르다는 것입니다. 스택을 사용하면 삽입된 마지막 항목이 가장 먼저 나가므로 스택의 한쪽 끝에서 푸시 및 팝합니다. 대기열을 사용하면 실생활의 대기열과 유사하게 삽입된 첫 번째 항목이 먼저 제거되므로 대기열에 넣기 및 대기열에서 빼기 작업은 대기열의 반대쪽 끝에서 수행됩니다.

"double-ended queue"또는 deque —"deck"으로 발음됨 —을 사용하면 언제든지 양쪽 끝에서 항목을 대기열에 넣거나 대기열에서 빼거나 ​​푸시 및 팝할 수 있습니다. 내부적으로 doubly-linked list로 구현된 삽입 및 삭제 작업은 O(1), 일정한 시간이 걸립니다. 이것은 또한 deque가 훌륭한 또 다른 이유입니다. 동일한 목표를 위해 Pythonlist을 사용할 수도 있다고 상상할 수 있습니다. end), 작업은 O(n) 시간이 걸리므로 그다지 좋지 않습니다.

한번 살펴보겠습니다. list 를 사용하면 스택이 다음과 같이 구현된 것을 볼 수 있습니다*:

class Stack:
    """Stack implementation as a list."""

    def __init__(self):
        """Create new stack."""
        self._items = []

    def is_empty(self):
        """Check if the stack is empty."""
        return not bool(self._items)

    def push(self, item):
        """Add an item to the stack."""
        self._items.append(item)

    def pop(self):
        """Remove an item from the stack."""
        return self._items.pop()

    def peek(self):
        """Get the value of the top item in the stack."""
        return self._items[-1]

    def size(self):
        """Get the number of items in the stack."""
        return len(self._items)

그리고 다음과 같은 대기열:

class Queue:
    """Queue implementation as a list."""

    def __init__(self):
        """Create new queue."""
        self._items = []

    def is_empty(self):
        """Check if the queue is empty."""
        return not bool(self._items)

    def enqueue(self, item):
        """Add an item to the queue."""
        self._items.insert(0, item)

    def dequeue(self):
        """Remove an item from the queue."""
        return self._items.pop()

    def size(self):
        """Get the number of items in the queue."""
        return len(self._items)

여기서는 목록 대신 deque를 사용하려고 하므로 간단히 살펴보겠습니다.

선택적으로 iterable을 인수로 전달하여 deque 객체를 초기화할 수 있습니다. collections 모듈에 있으므로 가져와야 합니다.

from collections import deque

d = deque([7, 3, 0, 1])
print(d) # deque([7, 3, 0, 1])

empty_d = deque()
print(empty_d) # deque([])

또한 문자열은 시퀀스라는 점을 기억하십시오. 이 경우 deque는 다음과 같습니다.

d = deque('hey')
print(d) # deque(['h', 'e', 'y'])

또한 maxlen 인수를 제공하여 deque에 원하는 항목의 최대 길이를 지정하여 제한할 수 있습니다.

이것은 간단한 예이지만 어떻게 작동하는지 이해해 봅시다.

from collections import deque

d = deque([4, 5, 3, 1, 8], maxlen=3)
print(d) # deque([3, 1, 8], maxlen=3)

d = deque([4, 5, 3, 1, 8], maxlen=4)
print(d) # deque([5, 3, 1, 8], maxlen=4)

iterable의 항목이 한쪽 끝에서 추가되므로 다른 항목(예: maxlen=3의 경우 4와 5)을 제거하면 반대쪽 끝에서 제거됩니다.

물론 a deque의 효율성은 appendleft() 및 popleft() 메서드에서 비롯되며 시간 복잡도 측면에서 a list보다 우수합니다.

from collections import deque

d = deque([7, 11])
d.appendleft(3)
print(d) # deque([3, 7, 11])

d.appendleft(1)
print(d) # deque([1, 3, 7, 11])

first_i = d.popleft()
print(first_i) # 1
print(d) # deque([3, 7, 11])

또한 append() 및 pop() 메서드는 일반 list처럼 오른쪽에서/오른쪽으로 작업을 수행합니다.

from collections import deque

d = deque([2, 4, 6])
d.append(8)
print(d) # deque([2, 4, 6, 8])

first_popped = d.pop()
second_popped = d.pop()

print(f'Popped {first_popped} first, then {second_popped} second.')
# -> Popped 8 first, then 6 second.

print(d) # deque([2, 4])

이제 양쪽에서 추가 및 팝 작업을 보았으므로 기사 시작 부분의 list 버전과 유사하게 대기열을 먼저 구현해 보겠습니다.

from collections import deque

class Queue:
    """Queue implementation as a deque."""

    def __init__(self):
        """Create new queue."""
        self._items = deque()

    def is_empty(self):
        """Check if the queue is empty."""
        return not bool(self._items)

    def enqueue(self, item):
        """Add an item to the queue."""
        self._items.append(item)

    def dequeue(self):
        """Remove an item from the queue."""
        return self._items.popleft()

    def size(self):
        """Get the number of items in the queue."""
        return len(self._items)

스택 버전의 경우 동일한 끝에서 추가하고 팝해야 하므로 append()를 사용하는 pop() 및 list 메서드도 처음에는 괜찮아 보일 수 있습니다. 그러나 위의 이전 스택 버전을 수정하여 deque로 구현해 보겠습니다.

from collections import deque

class Stack:
    """Stack implementation as a deque."""

    def __init__(self):
        """Create new stack."""
        self._items = deque()

    def is_empty(self):
        """Check if the stack is empty."""
        return not bool(self._items)

    def push(self, item):
        """Add an item to the stack."""
        self._items.append(item)

    def pop(self):
        """Remove an item from the stack."""
        return self._items.pop()

    def peek(self):
        """Get the value of the top item in the stack."""
        return self._items[-1]

그다지 달라진 것 같지는 않지만 appendleft()와 함께 popleft()를 사용하여 다른 쪽 끝을 사용하는 것도 상상할 수 있습니다.

우리는 deque를 사용하여 스택과 대기열을 생성하는 매우 간단한 방법을 살펴보았지만 물론 훨씬 더 자세히 알아볼 수 있습니다. The official documentation이 가장 먼저 가는 곳이고, 주제에 대한 Real Python article도 확인할 수 있습니다. 많은 것들과 마찬가지로 무엇을 달성하고 싶은지는 여러분에게 달려 있으며 양방향 대기열은 고려해야 할 툴킷의 또 다른 도구일 뿐입니다.

* 목록으로 구현된 스택 및 대기열의 예는 Brad Miller and David Ranum's wonderful book on algorithms and data structures에서 가져온 것입니다.