[데이터 구조] 스 택, 대기 열, 쌓 인 python 구현

12752 단어 데이터 구조
[데이터 구조] 스 택, 대기 열, 쌓 인 python 구현
  • 1. 스 택 의 python 실현
  • 1.1. 스 택 의 목록 실현 방법
  • 1.2. 양 방향 대기 열 로 스 택 시 뮬 레이 션
  • 2. 대열 의 python 실현
  • 2.1. 대열 의 목록 실현
  • 2.2, deque 를 사용 하여 대기 열 실현
  • 3. 쌓 인 python 실현
  • 스 택, 대기 열, 더 미 는 기본 적 인 데이터 구조 유형 으로 그 중에서 스 택 은 후진 에서 먼저 나 온 데이터 구조 이다.대기 열 은 선진 적 인 데이터 구조 이다.더 미 는 보통 나무 로 볼 수 있 고 가장 작은 더미 와 가장 큰 더미 로 나 눌 수 있다. 가장 작은 더 미 는 더미 속 의 특정한 노드 의 요소 가 아버지 노드 의 값 보다 크 지 않다 는 것 을 말한다.최대 더 미 는 더미 속 의 어떤 요소 가 부모 노드 의 값 보다 작 지 않다 는 것 을 말한다.
    창고 의 python 구현
    1.1 창고 의 목록 실현 방법
    목록 (list) 은 python 에서 자주 사용 하 는 기본 데이터 구조 입 니 다. 우 리 는 목록 을 사용 하여 스 택 을 모 의 하여 스 택 에 들 어가 고 스 택 을 나 오 는 등 효 과 를 실현 할 수 있 습 니 다.
    stack = []
    #  
    stack.append(1)
    print(stack)
    stack.append(2)
    print(stack)
    stack.append(5)
    print(stack)
    #      
    top = stack[-1]
    print('     :',top)
    #  
    stack.pop()
    print(stack)
    #       
    if stack:
        print('Not Empty')
    else:
        print('Empty')
    

    1.2 양 방향 대기 열 로 스 택 시 뮬 레이 션
    python 내 장 된 모듈 collections 에는 양 방향 대기 열 deque 의 데이터 구조 유형 이 포함 되 어 있 습 니 다. 대기 열의 왼쪽 끝 과 오른쪽 끝 에서 입 대 와 출 대 를 실현 할 수 있 습 니 다. 양 방향 대기 열의 오른쪽 끝 에서 입 대 와 출 대 동작 을 가리 키 면 입 스 택 과 출 스 택 을 모 의 할 수 있 습 니 다.
    from collections import deque
    
    stack = deque()
    #  
    stack.append(1)
    print(stack)
    stack.append(2)
    print(stack)
    #  
    a = stack.pop()
    print(stack)
    print(list(stack))
    
    #       
    if list(stack):
        print('    !')
    else:
        print('   !')
    

    2. 대기 열의 python 실현
    2.1 대기 열의 목록 구현
    목록 끝 에 요 소 를 추가 하여 시 뮬 레이 션 을 할 수 있 습 니 다. 목록 머리 에 요 소 를 삭제 하여 시 뮬 레이 션 을 할 수 있 습 니 다.
    queue = []
    #  
    queue.append(1)
    print(queue)
    queue.append(2)
    print(queue)
    queue.append(5)
    print(queue)
    #  
    queue.pop(0)
    print(queue)
    #        
    if queue:
        print('Not Empty')
    else:
        print('Empty')
    

    2.2, deque 를 사용 하여 대기 열 구현
    from collections import deque
    
    queue = deque()
    #  
    queue.append(1)
    print(queue)
    queue.append(1)
    print(queue)
    queue.append(7)
    print(queue)
    #  
    queue.popleft()
    print(queue)
    #        
    queue.insert(1,3)
    print(queue)
    #        
    if queue:
        print('Not Empty')
    else:
        print('Empty')
    

    3. 쌓 인 python 실현
    python 에 쌓 기 를 실현 하 는 모듈 이 내장 되 어 있어 서 직접 호출 할 수 있 습 니 다.
    import heapq
    
    #  h
    h = [1,4,5,2,7]
    
    # h       
    heapq.heapify(h)
    print(h)
    
    #      
    a = heapq.heappop(h)
    print('     :',a)
    print('    :',h)
    #         val,       
    val = 3
    heapq.heappush(h,val)
    print('    :',h)
    
    #         ,          ,                    。
    val = 4
    heapq.heapreplace(h,val)
    print('    :',h)
    

    좋은 웹페이지 즐겨찾기