Implementing Stack with Python

Question

Próbuję zaimplementować prosty stos z Python za pomocą tablic. Zastanawiałem się, czy ktoś mógłby mi powiedzieć, co jest nie tak z moim kodem.

class myStack: 
    def __init__(self): 
     self = [] 

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

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

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

    def size(self): 
     return len(self) 

    s = myStack() 
    s.push('1') 
    s.push('2') 
    print(s.pop()) 
    print s 

Answer 1

Poprawiłem kilka problemów poniżej. Również "stos", w terminologii programowania abstrakcyjnego, jest zwykle zbiorem, w którym dodajesz i usuwasz z góry, ale sposób, w jaki go zaimplementowałeś, dodajesz do góry i usuwasz od dołu, co sprawia, że ​​jest kolejką .

class myStack: 
    def __init__(self): 
     self.container = [] # You don't want to assign [] to self - when you do that, you're just assigning to a new local variable called `self`. You want your stack to *have* a list, not *be* a list. 

    def isEmpty(self): 
     return self.size() == 0 # While there's nothing wrong with self.container == [], there is a builtin function for that purpose, so we may as well use it. And while we're at it, it's often nice to use your own internal functions, so behavior is more consistent. 

    def push(self, item): 
     self.container.append(item) # appending to the *container*, not the instance itself. 

    def pop(self): 
     return self.container.pop() # pop from the container, this was fixed from the old version which was wrong 

    def size(self): 
     return len(self.container) # length of the container 

s = myStack() 
s.push('1') 
s.push('2') 
print(s.pop()) 
print s 

Answer 2

Przypisanie do self nie zmieni swój obiekt na liście (a jeśli tak, obiekt nie będzie miał wszystkie swoje metody stosu dłużej). Przypisanie do self powoduje jedynie zmianę zmiennej lokalnej. Zamiast tego, należy ustawić atrybut:

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

i użyć atrybutu zamiast tylko gołe self:

def push(self, item): 
    self.stack.append(item) 

Ponadto, jeśli chcesz stos, chcesz pop() zamiast pop(0). pop(0) przekształciłby twoją strukturę danych w (nieefektywną) kolejkę.

Answer 3

Twój problem polega na tym, że pojawiasz się od początku listy, kiedy powinieneś pojawiać się na końcu listy. Stos jest strukturą danych Last-In First-Out, co oznacza, że ​​gdy coś z niej wyskoczysz, to coś będzie tym, co nałożyłeś ostatnio. Spójrz na swoją funkcję push - dołącza element do listy. Oznacza to, że pojawia się na końcu listy. Podczas wywoływania .pop (0) usuwasz pierwszy element z listy, a nie ostatni element. Usunięcie 0 z .pop (0) powinno rozwiązać twój problem.

Answer 4

Zostawiłem komentarz z linkiem do http://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks, ale jeśli chcesz mieć typ niestandardowy, który daje push, pop, is_empty i size metod wygody bym tylko podklasy list.

class Stack(list): 
    def push(self, item): 
     self.append(item) 
    def size(self): 
     return len(self) 
    def is_empty(self): 
     return not self 

Jednak, jak powiedziałem w komentarzach, ja pewnie po prostu trzymać się prostej list tutaj, jak wszystko co robi jest naprawdę aliasing istniejących metod, które zwykle służy tylko do kodu trudniejszy w obsłudze na dłuższą metę, ponieważ wymaga od osób, które go używają, nauczyć się interfejsu aliasu na początku oryginału.

Answer 5

Twój stack jest tablicą ...

class stacked(): # Nodes in the stack 
    def __init__(self,obj,next): 
     self.obj = obj 
     self.next = next 
    def getObj(self): 
     return(self.obj) 
    def getNext(self): 
     return(self.next) 

class stack(): # The stack itself 
    def __init__(self): 
     self.top=None 
    def push(self,obj): 
     self.top = stacked(obj,self.top) 
    def pop(self): 
     if(self.top == None): 
      return(None) 
     r = self.top.getObj() 
     self.top = self.top.getNext() 
     return(r) 

Answer 6

Poniżej jest prosta implementacja stosu w Pythonie. Ponadto zwraca środkowy element w dowolnym momencie.

class Stack: 
     def __init__(self): 
      self.arrList = [] 

     def isEmpty(self): 
      if len(self.arrList): 
       return False 
      else: 
       return True 

     def push(self, val): 
      self.arrList.append(val) 

     def pop(self): 
      if not self.isEmpty(): 
       self.arrList[len(self.arrList)-1] 
       self.arrList = self.arrList[:len(self.arrList)-1] 
      else: 
       print "Stack is empty" 

     def returnMiddle(self): 
      if not self.isEmpty(): 
       mid = len(self.arrList)/2 
       return self.arrList[mid] 
      else: 
       print "Stack is empty" 

     def listStack(self): 
      print self.arrList 

    s = Stack() 
    s.push(5) 
    s.push(6) 
    s.listStack() 
    print s.returnMiddle() 
    s.pop() 
    s.listStack() 
    s.push(20) 
    s.push(45) 
    s.push(435) 
    s.push(35) 
    s.listStack() 
    print s.returnMiddle() 
    s.pop() 
    s.listStack() 

wyjściowa:

[5, 6] 
6 
[5] 
[5, 20, 45, 435, 35] 
45 
[5, 20, 45, 435] 

Answer 7

Implementing a Stack in Python z książki rozwiązywania problemów z algorytmów i struktur danych

Answer 8

Właściwa realizacja obejmowałyby __iter__ również od Stos musi być LIFO zamówienie.

class Stack: 
    def __init__(self): 
     self._a = [] 

    def push(self, item): 
     self._a.append(item) 

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

    def isEmpty(self): 
     return len(self._a) == 0 

    def __iter__(self): 
     return reversed(self._a) 

    def __str__(self): 
     # return str(list(reversed(self._a))) 
     return str(list(iter(self))) 

def main(): 
    stack = Stack() 
    stack.push('a') 
    stack.push('b') 
    stack.push('c') 
    stack.pop() 
    print(stack) 
    if stack: 
     print("stack not empty") 
    stack.pop() 
    stack.pop() 
    if stack.isEmpty(): 
     print("stack empty") 

if __name__ == '__main__': 
    main()