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