Python의 큐 구현 방법(코드 예)

이 기사는 Python의 대기열 구현 방법(코드 예제)에 대한 것입니다. 이는 특정 참조 가치가 있으므로 도움이 필요한 친구에게 도움이 되기를 바랍니다.

파이썬의 경우 기존 메소드를 기반으로 큐 클래스를 구현하는 것은 매우 간단합니다. 큐의 한쪽 끝에서는 삽입이 필요하고 다른 쪽 끝에서는 삭제가 필요하기 때문입니다. 분명히 Python에는 이 두 가지 도구가 있습니다. 대기열의 꼬리를 삭제하려면 pop(0)을 사용할 수 있고, 머리를 삽입하려면 추가를 사용할 수 있습니다. 이런 점에서는 정말 간단하지만 항상 최적의 솔루션을 찾아야 하잖아요? 그래서 우리는 pop 메소드를 사용하지 않습니다. 왜냐하면 파이썬의 내부 구현에서 이 메소드의 복잡성은 O(n)이기 때문입니다. 목록의 첫 번째 요소를 삭제하면 목록의 모든 요소가 앞으로 이동합니다. 이것이 Python이 목록의 무결성을 유지하려는 이유입니다

우리는 대기열을 구현하기 위해 순환 시퀀스 테이블을 사용합니다.

구체적인 아이디어는 다음과 같습니다.

목록의 앞에서 삭제를 시작할 때 헤드 포인터는 요소 영역의 시작점을 따릅니다. 즉, 헤드 포인터는 삭제와 함께 뒤쪽으로 계속 변경되므로 요소가 추가되면서 꼬리 포인터가 목록의 마지막 위치에 도달하면 꼬리 포인터가 목록의 첫 번째 노드(빈 노드)로 다시 이동합니다. 헤드 포인터와 테일 포인터가 수렴한다는 것은 전체 고정 목록이 모두 사용되는 경우를 의미합니다. 여기서는 큐의 저장 공간을 확장하는 메서드도 정의합니다. 이는 큐가 가득 차면 자동으로 이 내부 메서드를 호출합니다. 대기열 공간을 확장합니다.

구현:

분석 후 우리는

• 요소 영역 self._head의 시작 첨자를 지정하는 헤드 포인터를 정의할 수 있음을 알 수 있습니다.

• 요소 영역 길이를 저장하는 변수를 정의합니다. self._num

• 전체 리스트의 길이를 저장하는 변수 self._len

• 물론 큐가 위치한 리스트 변수 self._list

정의한 후 몇 가지 변수가 나온다. 몇 가지 판단을 살펴보자:

• self._num = self._len이면 이때 대기열이 가득 찼음을 의미합니다.

• self._num = 0이면 대기열은 다음과 같습니다. 비어 있음

하나의 대기열에서 지원 여러 가지 작업이 있습니다:

1. 빈 대기열 만들기

2. 대기열이 비어 있는지 확인

3. 대기열의 맨 위에서 값 가져오기

4. 대기열 제거 Operation

5. Enqueue 연산

6. 또한 목록의 길이를 늘리는 내부 메서드를 정의했습니다.

구체적인 구현은 다음과 같습니다.

# _*_ coding: utf-8 _*_

class OverFlowError(ValueError):
    pass

class Queue:
    def __init__(self, init_len=0):
        self._len = init_len
        self._list = [0] * init_len
        self._num = 0 # 计数元素
        self._head = 0 # 头指针

    def is_empty(self):
        return self._num == 0

    def peek(self):
        if self._num == 0:
            raise OverFlowError("取队列首位值，但队列为空")
        return self._list[self._head]

    def enqueue(self, elem):
        if self._num = self._len:
            self._extend()
        self._list[(self._head + self._num) % self._len] = elem
        self._num += 1

    def dequeue(self):
        if self._num == 0:
            raise OverFlowError("队列首位出队列，但队列为空")
        e = self._list[self._head]
        self._head = (self._head + 1) % self._len
        self._num -= 1
        return e

    def _extend(self):
        new_len = self._len * 2
        new_list = [0] * new_len
        i = 0
        p = self._head
        while not p == (self._head + self._num) % self._len:
            new_list[i] = self._list[p]
            i += 1
        self._len = new_len
        self._list = new_list
        self._head = 0

아이디어가 매우 중요하며 어떻게 구현하는지는 중요하지 않습니다. 정말 중요해요, 먼저 구현해 보시고 나면 더 좋은 효과를 보실 수 있을 거예요!

위 내용은 Python의 큐 구현 방법(코드 예)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!