기본 데이터 구조: 스 택, 대기 열 - Python 구현

기본 데이터 구조: 스 택, 대기 열 - Python 구현
지난 절 에 우 리 는 데이터 구조의 순서 와 체인 식 저장 구 조 를 중심 으로 소 개 했 습 니 다. 그러면 이번 에는 스 택 과 대기 열 이라는 가장 기본 적 인 선형 논리 구 조 를 실현 하 겠 습 니 다.
스 택 과 대기 열 에 대한 가장 간단 한 설명 이자 그들의 가장 핵심 적 인 성격 입 니 다. 바로:

스 택 - 후진 선 출

대열 - 선진 선발

한 가지 간단 한 비 유 는 창고 가 책 한 권 을 한 상자 에 차례대로 쌓 아 놓 고 상자 에 넣 은 것 이 먼저 꺼 내 는 것 과 같다 는 것 이다.대열 은 줄 을 서 는 것 과 같 고, 먼저 줄 을 서 는 사람 이 먼저 대접 을 받는다.
이것 은 논리 적 인 두 가지 데이터 구조 로 앞에서 말 한 순서 표 와 링크 두 가지 저장 구조 에 대응 합 니 다. 우 리 는 프로 그래 밍 을 통 해 데이터 구 조 를 실현 할 때 상기 두 가지 표를 계승 하여 순서 스 택, 순서 스 택, 체인 스 택, 체인 스 택 을 파생 시 킬 수 있 습 니 다.또는 스 택 과 대기 열의 기본 클래스 를 단독으로 실현 하고 다 중 계승 (c + \ Python) 또는 조합 (자바) 두 가 지 를 결합 하여 상기 네 가지 데이터 구 조 를 얻 을 수 있 습 니 다.
Python 의 list 를 사용 하여 순서 스 택 과 순서 대기 열 을 실현 하 는 것 은 매우 간단 합 니 다. 우 리 는 이전 절 에 있 는 순서 표를 계승 하고 스 택 이나 대기 열 에 있 는 함 수 를 추가 하면 됩 니 다.

#   ：   
class List:

    def __init__(self):
        self.list = []

    def __str__(self):
        return str(self.list)

    def put(self, item):
        self.list.append(item)

    def size(self):
        return len(self.list)

    def isEmpty(self):
        return self.list == []

#   ：   
class ListStack(List):

    def pop(self):
        if self.isEmpty():
            return None
        else:
            return self.list.pop(-1)


#   ：    
class ListQueue(List):

    def dequeue(self):
        if self.isEmpty():
            return None
        else:
            return self.list.pop(0)

Python 기본 데이터 구조 list 의 방법 append 와 pop 을 사용 하여 입 출력 을 실현 합 니 다. pop 방법의 index 매개 변 수 를 바 꾸 면 스 택 과 출 대기 열의 논 리 를 실현 할 수 있 습 니 다.

#  
s=ListStack()
q=ListQueue()
for i in range(0,10):
    s.put(i)
    q.put(i)
print("Stack:",s)
print("Queue:",q)
for i in range(0,5):
    print("Stack pop:",s.pop())
    print("Queue dequeue:",q.dequeue())
print("Stack:",s)
print("Queue:",q)

#  
Stack: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Queue: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Stack pop: 9
Queue dequeue: 0
Stack pop: 8
Queue dequeue: 1
Stack pop: 7
Queue dequeue: 2
Stack pop: 6
Queue dequeue: 3
Stack pop: 5
Queue dequeue: 4
Stack: [0, 1, 2, 3, 4]
Queue: [5, 6, 7, 8, 9]

링크 기본 클래스 를 계승 하여 체인 스 택 과 체인 대기 열 을 얻 을 수 있 습 니 다. 지난 편 에서 언급 한 바 와 같이 우 리 는 rear 필드 를 추가 하여 꼬리 부분 을 삽입 할 수 있 습 니 다. 그러나 삭제 할 때 우 리 는 rear 를 앞으로 이동 시 켜 야 합 니 다. 전체 시 계 를 옮 겨 다 니 지 않도록 우 리 는 양 방향 링크 가 필요 합 니 다. node 구조 에서 last 를 추가 하여 앞의 노드 를 가리 키 도록 해 야 합 니 다.그러나 사실 링크 의 첫 번 째 연결 을 양 방향 순환 링크 로 구성 하면 우 리 는 rear 가 아니 라 head. last 로 끝 점 을 찾 을 수 있다.
아래 의 양 방향 순환 목록 기본 클래스 의 내부 방법 을 약간 수정 하고 디자인 방향 은 위의 순서 방법 에 비해 달라 집 니 다.

#       
class DoubleLoopLinked:

    class __Node:
        item = None
        next = None
        last = None

        def __init__(self, item, n, l):
            self.item = item
            self.next = n
            self.last = l

    def __init__(self):
        self.__head = self.__Node(None, None, None)
        self.__size = 0

    def __str__(self):
        p = self.__head.next
        l = []
        while p != self.__head:
            l.append(p.item)
            p = p.next
        return str(l)

    #Python              ，          
    #                       （         def _function(self)）
    #         ，      （     ）  
    #        ，   ，pycharm      protected member,             
    #    
    def _insertToTail(self, item):
        if self.isEmpty():
            node = self.__Node(item, self.__head, self.__head)
            self.__head.next = node
            self.__head.last = node
        else:
            node = self.__Node(item, self.__head, self.__head.last)
            self.__head.last.next = node
            self.__head.last = node
        self.__size += 1

    #    
    def _insertToHead(self, item):
        if self.isEmpty():
            node = self.__Node(item, self.__head, self.__head)
            self.__head.next = node
            self.__head.last = node
        else:
            node = self.__Node(item, self.__head.next, self.__head)
            self.__head.next.last = node
            self.__head.next = node
        self.__size += 1

    #      
    def _popHead(self):
        if self.isEmpty():
            return None
        else:
            node = self.__head.next
            self.__head.next = node.next
            node.next.last = self.__head
            self.__size -= 1
            it = node.item
            del node
            return it

    #      
    def _popTail(self):
        if self.isEmpty():
            return None
        else:
            node = self.__head.last
            self.__head.last = node.last
            node.last.next = self.__head
            self.__size -= 1
            it = node.item
            del node
            return it

    def size(self):
        return self.__size

    def isEmpty(self):
        return self.__size == 0

우 리 는 스 택 과 대기 열 을 실현 할 때 기본 클래스 가 제공 하 는 방법 만 사용 해 야 합 니 다.

#   ：   
class LinkedStack(DoubleLoopLinked):

    def push(self,item):
        self._insertToTail(item)

    def pop(self):
        return self._popTail()


#   ：    
class LinkedQueue(DoubleLoopLinked):

    def enqueue(self,item):
        self._insertToTail(item)

    def dequeue(self):
        return self._popHead()

테스트 결 과 는 순서 저장 방식 과 같다.