Реализация стека с Python

Question

Я пытаюсь реализовать простой стек с 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) превратит вашу структуру данных в (неэффективную) очередь.

Answer 3

Ваша проблема в том, что вы выходите из начала списка, когда вы должны появляться в конце списка. Стек представляет собой структуру данных Last-In First-Out, что означает, что когда вы что-то вытаскиваете из нее, это что-то будет тем, что вы нажали последним. Взгляните на вашу функцию push - она ​​добавляет элемент в список. Это означает, что оно идет в конце списка. Однако, когда вы вызываете .pop (0), вы удаляете первый элемент в списке, а не тот, который вы последний раз добавляли. Удаление 0 из .pop (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

Ниже приводится простая реализация стека в питона. Кроме того, он возвращает средний элемент в любой момент времени.

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