Python에서 스택 클래스 생성

이 구현에서는 기본 제공 목록 대신 링크 된 목록을 사용합니다. 성능 향상을 위해 어떤 버전을 사용합니까?Python에서 스택 클래스 생성

class Stack: 
    top = '' 
    def __init__(self,data=None,next=None): 
     self.data = data 
     self.next = next 
    def pop(self): 
     if self.top != None: 
      item = self.top.getvalue() 
      self.top = self.top.next 
      return item 
     else: 
      return 
    def push(self,data): 
     t = Stack(data) 
     t.next = self.top 
     self.top = t 
    def peek(self): 
     return self.top.getvalue() 
    def getvalue(self): 
     return self.data 

s = Stack() 
s.push('bottom') 
s.push('middle') 
s.push('top') 
popped = s.pop() 
print(popped) 
top = s.peek() 
print(top)

출력 :
최고
중간

출처

2014-09-10 PressPlay

당신은 학습 운동으로이 일을하고 있는가? 아니면 일반적으로 사용 가능한 새로운 데이터 구조를 만들려고하십니까? https://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks –

항상 그렇듯이 사용 사례를 측정하십시오. (빌트인 목록 유형보다 훨씬 느릴 것입니다.) –

내장 된 목록을 기반으로 스택 클래스는 훨씬 더 나은 성능을 가질 것, 예를 들어, timeit 모듈

class StackEmptyError(Exception): 
    pass 

class ListBasedStack(list): 
    push = list.append 

    def pop(self): 
     try: 
      return super(ListBasedStack, self).pop() 
     except IndexError: 
      raise StackEmptyError 

    def peek(self): 
     try: 
      return self[-1] 
     except IndexError: 
      raise StackEmptyError

측정 실행 시간 :

>>> import timeit 
>>> stmt = ''' 
s = Stack() 
s.push('bottom') 
s.push('middle') 
s.push('top') 
s.peek() 
s.pop()''' 

# test built-in list stack class 
>>> timeit.repeat(stmt, 'from __main__ import ListBasedStack as Stack') 
[1.4590871334075928, 1.4085769653320312, 1.3971672058105469] 

# test OP stack class 
>>> timeit.repeat(stmt, 'from __main__ import Stack') 
[5.018421173095703, 4.971158981323242, 4.990453004837036]

내장 된 목록 기반 클래스는 약 3.5 배 빠른 연결리스트 하나보다. 더 빨리 여전히 (약 5 배 빠른) 당신이 Stack 작업에 제기 IndexError 예외를 필요에 대한 까다로운하지 않은 경우

그리고, :

는

class MinimalistStack(list): 
    push = list.append 
    def peek(self): 
     return self[-1] 

>>> timeit.repeat(stmt, 'from __main__ import MinimalistStack as Stack') 
[0.9379069805145264, 0.9144589900970459, 0.9160430431365967]

출처

2014-09-10 12:29:13 mhawke

Python에서 스택 클래스 생성

답변

관련 문제