用 Python 实现堆栈

Implementing Stack with Python

提问by user2687481

I am trying to implement a simple stack with Python using arrays. I was wondering if someone could let me know what's wrong with my code.

我正在尝试使用数组用 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

采纳答案by Brionius

I corrected a few problems below. Also, a 'stack', in abstract programming terms, is usually a collection where you add and remove from the top, but the way you implemented it, you're adding to the top and removing from the bottom, which makes it a queue.

我纠正了下面的几个问题。此外，在抽象编程术语中，“堆栈”通常是您在顶部添加和删除的集合，但是您实现它的方式是在顶部添加和从底部删除，这使其成为一个队列.

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 peek(self):
         if self.isEmpty():
             raise Exception("Stack empty!")
         return self.container[-1]  # View element at top of the stack

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

     def show(self):
         return self.container  # display the entire stack as list


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

回答by user2357112 supports Monica

Assigning to selfwon't turn your object into a list (and if it did, the object wouldn't have all your stack methods any more). Assigning to selfjust changes a local variable. Instead, set an attribute:

分配给self不会将您的对象转换为列表（如果确实如此，该对象将不再拥有您的所有堆栈方法）。分配给self只是改变了一个局部变量。相反，设置一个属性：

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

and use the attribute instead of just a bare self:

并使用该属性而不仅仅是一个裸self：

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

Also, if you want a stack, you want pop()rather than pop(0). pop(0)would turn your data structure into a(n inefficient) queue.

此外，如果你想要一个堆栈，你想要pop()而不是pop(0). pop(0)会将您的数据结构变成（n 低效）队列。

回答by Zach

Your problem is that you're popping from the beginning of the list, when you should be popping from the end of the list. A stack is a Last-In First-Out data structure, meaning that when you pop something from it, that something will be whatever you pushed on last. Take a look at your push function - it appends an item to the list. That means that it goes at the end of the list. When you call .pop(0), however, you're removing the first item in the list, not the one you last appended. Removing the 0 from .pop(0) should solve your problem.

你的问题是你从列表的开头弹出，而你应该从列表的末尾弹出。堆栈是后进先出的数据结构，这意味着当您从中弹出某些内容时，该内容将是您最后推送的内容。看看您的推送功能 - 它会将一个项目附加到列表中。这意味着它位于列表的末尾。但是，当您调用 .pop(0) 时，您将删除列表中的第一项，而不是上次附加的项。从 .pop(0) 中删除 0 应该可以解决您的问题。

回答by Silas Ray

I left a comment with the link to http://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks, but if you want to have a custom type that gives you push, pop, is_empty, and sizeconvenience methods, I'd just subclass list.

我离开的链接评论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

However, as I said in the comments, I'd probably just stick with a straight listhere, as all you are really doing is aliasing existing methods, which usually only serves to make your code harder to use in the long run, as it requires people using it to learn your aliased interface on top of the original.

但是，正如我在评论中所说，我可能只是list在这里坚持，因为您真正要做的只是对现有方法进行别名，这通常只会使您的代码从长远来看更难使用，因为它需要人们使用它来学习您在原始界面之上的别名界面。

回答by kpie

Your stack is an array...

你的堆栈是一个数组...

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)

回答by Harish Talanki

Below is the simple implementation of stack in python. In addition, it returns the middle element at any point in time.

下面是python中stack的简单实现。此外，它会在任何时间点返回中间元素。

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

Output:

输出：

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

回答by Seth

Implementing a Stack in Pythonfrom the book of Problem Solving with Algorithms and Data Structures

《用算法和数据结构解决问题》一书中的用 Python 实现堆栈

回答by mythicalcoder

The proper implementation would include __iter__also since Stack needs to be LIFO order.

正确的实现还包括__iter__因为 Stack 需要是 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()

回答by Joshua Enos

Below is my implementation

下面是我的实现

class Stack:
    def __init__(self):
        self.items = list()
    def is_empty(self):
        return self.items == []
    def peek(self):
        if self.is_empty():
            print('Cannot peek empty stack')
            return
        else:
            return self.items[-1]
    def pop(self):
        if self.is_empty():
            print('Cannot pop an empty stack')
            return
        else:
            return self.items.pop()
    def size(self):
        return len(self.items)
    def push(self,data):
        self.items.append(data)

回答by Grijesh Chauhan

I would like to share my version of the stack implementation that inherits Python List. I believe iteration on a stack should be happening in LIFO order. Additionally, an iteration on pop-all()should be provided to iterate while poping all elements. I have also added stack.clear()to empty a stack (like we have in deque.clear()in collections module). I have also override __repr__for debugging purpose:

我想分享我的继承 Python List 的堆栈实现版本。我相信堆栈上的迭代应该以 LIFO 顺序进行。此外，pop-all()应提供迭代以在弹出所有元素时进行迭代。我还添加stack.clear()了清空堆栈（就像我们deque.clear()在集合模块中所做的那样）。我还覆盖__repr__了调试目的：

class Stack(list):

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

    def top(self):
        return self[-1]

    def size(self):
        return len(self)

    def isempty(self):
        return self.size() == 0

    def __iter__(self):
        """ iter in lifo """
        return super(Stack, self).__reversed__()

    def __reversed__(self):
        return super(Stack, self).__iter__()

    def popall(self):
        try:
            while True:
                yield self.pop()
        except IndexError:
            pass

    def clear(self):
        del self[:]

    def __repr__(self):
        if not self:
            return '%s()' % self.__class__.__name__
        return '%s(%s)' % (self.__class__.__name__, super(Stack, self).__repr__())

Here is how you can use it:

以下是如何使用它：

stack = Stack(range(5))
print "stack: ", stack  # stack:  Stack([0, 1, 2, 3, 4])

print "stack.pop() => ", stack.pop() # stack.pop() =>  4
print "stack.push(20) " # stack.push(20) 
stack.push(20)
for item in stack:
    print item  # prints 20, 3, 2... in newline
print "stack: ", stack # stack:  Stack([0, 1, 2, 3, 20])
print "stack pop all..."
for item in stack.popall(): # side effect to clear stack
    print item
print "stack: ", stack # stack:  Stack()

Primary, I implemented it to use to solve a programming problem next greater element.

初级，我实现了它用来解决编程问题下一个更大的元素。