用Python實現堆棧

Question

我想用Python實現一個簡單的Python堆棧。我想知道如果有人能讓我知道我的代碼有什麼問題。

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

我糾正了下面的一些問題。另外，抽象編程術語中的'堆棧'通常是一個集合，您可以從頂部添加和刪除，但是您實現它的方式，您將添加到頂部並從底部移除，這使得它成爲隊列。

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

分配到self不會把你的對象到一個列表（如果它這樣做了，對象不會有你的所有的堆棧方法了）。分配給self只是改變一個局部變量。相反，設置一個屬性：

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

和使用屬性，而不是隻是一個裸self：

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

另外，如果你想有一個堆棧，你想pop()而非pop(0)。 pop(0)會將您的數據結構變成（n低效率）隊列。

Answer 3

你的問題是，你從列表的開頭彈出，當你應該從列表的末尾彈出。一個堆棧是一個後進先出的數據結構，這意味着當你從中彈出一些東西時，那些東西將會是你最後推送的東西。看看你的推送功能 - 它將一個項目追加到列表中。這意味着它在列表的最後。但是，當您調用.pop（0）時，您將刪除列表中的第一個項目，而不是您最後追加的項目。從.pop（0）中刪除0應該可以解決您的問題。

Answer 4

我留下的鏈接評論到http://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks，但如果你想擁有，讓你push，pop，is_empty，並size方便的方法自定義類型，我只是繼承list。

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

然而，正如我在評論中說，我可能只是堅持採用了直板list在這裏，因爲所有你真的做的是走樣現有的方法，通常只會讓你的代碼更難使用從長遠來看，因爲它需要人們使用它來學習原始頂部的別名界面。

Answer 5

你的籌碼是一個數組...

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

下面是簡單的實現在Python堆棧。另外，它在任何時間點返回中間元素。

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() 

輸出：

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

Answer 7

Implementing a Stack in Python從算法與數據結構解決問題的書的

Answer 8

的正確實施將包括__iter__也因爲堆棧必須LIFO順序。

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()