Implementing Stack with Python

问题:

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.

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

回答1:

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

回答2:

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

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

and use the attribute instead of just a bare 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.

回答3:

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 size convenience methods, I'd just subclass 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 list here, 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.

回答4:

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

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

回答5:

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.

回答6:

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)

回答7:

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

  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]

回答8:

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

回答9:

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)

回答10:

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:

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.