Implementierung eines Stacks

Stellt hier eure Projekte vor.
Internetseiten, Skripte, und alles andere bzgl. Python.
Benutzeravatar
ms4py
User
Beiträge: 1178
Registriert: Montag 19. Januar 2009, 09:37

Implementierung eines Stacks

Beitragvon ms4py » Mittwoch 11. Februar 2009, 08:56

Vielleicht kann es ja jemand brauchen. Hab es so nebenher gemacht, während ich eine Programmdokumentation geschrieben hab.

Code: Alles auswählen

class Stack(object):
   def __init__(self):
      self.list = []

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

   def pop(self):
      return self.list.pop()

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

   def isEmpty(self):
      return not bool(len(self.list))
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Beitragvon rayo » Mittwoch 11. Februar 2009, 09:40

Eine Liste ist nicht unbedingt optimal für einen Stack. Besser wäre mit einer deque, die Gründe warum stehen auch dort.

Gruss
Benutzeravatar
BlackVivi
User
Beiträge: 762
Registriert: Samstag 9. Dezember 2006, 14:29
Kontaktdaten:

Beitragvon BlackVivi » Mittwoch 11. Februar 2009, 09:43

Die Methode isEmpty hält sich nicht an PEP8 (müsste is_empty heißen...)

Außerdem is sie ein bissel zu kompliziert.

Code: Alles auswählen

def is_empty(self):
    return not bool(self.list)


Das reicht schon. (Man könnte sogar bool() weglassen, aber... find's dann nich mehr ganz so eindeutig.)
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5554
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Telfs (Tirol)
Kontaktdaten:

Beitragvon gerold » Mittwoch 11. Februar 2009, 09:49

Hallo!

Wenn eine Liste als Stack genügt, dann könnte man von einer Liste ableiten.

Code: Alles auswählen

class Stack(list):

    def push(self, item):
        self.append(item)
   
    def top(self):
        return self.pop(0)

Im Falle der Liste als Basis, würde ich "is_empty" komplett weglassen. Das prüft man sowiso von außen.

Code: Alles auswählen

stack = Stack()
if stack:
    ...



mfg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Benutzeravatar
ms4py
User
Beiträge: 1178
Registriert: Montag 19. Januar 2009, 09:37

Beitragvon ms4py » Mittwoch 11. Februar 2009, 09:59

Soll ja der Spezifikation des ADTs Stack gerecht werden.
Deshalb halte ich mich auch nicht an die PEP8.
Und deshalb kann ich auch keine Liste ableiten, weil dann die anderen Operationen auch möglich sind.

Aber Danke für die optimierte isEmpty-Methode!

Edit: Wie gesagt, ist eh nur Spielerei für den Anhang der Doku. Im echten Programm benutze ich direkt eine Liste. Braucht also nicht so viel Wind um die ganze Sache machen ;)

Edit2: Und da meine maximale Stack-Größe bisher auf 20 begrenzt ist, spielt das mit der Komplexität (Gründe für deque) eigentlich auch keine Rolle...
Benutzeravatar
ms4py
User
Beiträge: 1178
Registriert: Montag 19. Januar 2009, 09:37

Beitragvon ms4py » Mittwoch 11. Februar 2009, 10:16

Ok, hab mir nochmal mein Programm angeschaut. Für den Einsatz von "deque" musste ich außer dem import genau eine Zeile ändern.
statt stack = [] steht jetzt stack = deque().
Da die Methoden gleich heißen, hab ich jetzt doch die deque genommen.
Jetzt muss ich nur in der Doku wieder einiges ändern *grml*

Naja hier noch der neue Stack-Code mit deque und Super-Komplexität^^

Code: Alles auswählen

#!/usr/bin/env python
from collections import deque

class Stack(object):
   def __init__(self):
      self.list = deque()
   def push(self, item):
      self.list.append(item)
   def pop(self):
      return self.list.pop()
   def top(self):
      return self.list[-1]
   def isEmpty(self):
      return not bool(self.list)


Edit: Und nein, ich werde auch nicht von der deque ableiten ;)
So lass ich es jetzt...
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 11. Februar 2009, 10:34

ice2k3 hat geschrieben:Edit: Und nein, ich werde auch nicht von der deque ableiten ;)

Warum nicht? Und warum nicht PEP8-konform?
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
ms4py
User
Beiträge: 1178
Registriert: Montag 19. Januar 2009, 09:37

Beitragvon ms4py » Mittwoch 11. Februar 2009, 10:41

ice2k3 hat geschrieben:Soll ja der Spezifikation des ADTs Stack gerecht werden.
Deshalb halte ich mich auch nicht an die PEP8.
Und deshalb kann ich auch keine Liste ableiten, weil dann die anderen Operationen auch möglich sind.


Die Spezifikation bezieht sich eben auf meine Info-Vorlesung.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 11. Februar 2009, 17:55

Und wo würde das vererben stören?
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
ms4py
User
Beiträge: 1178
Registriert: Montag 19. Januar 2009, 09:37

Beitragvon ms4py » Mittwoch 11. Februar 2009, 18:09

Weil zur Spezifikation z.B. nicht stack.popleft() gehört, sondern nur die 4 implementierten Methoden. Wenn ich das mit Generalisierung löse, werden alle Methoden mitvererbt, die ich gar nicht haben will.
Was ist daran nicht zu verstehen?!
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 11. Februar 2009, 18:16

ice2k3 hat geschrieben:Was ist daran nicht zu verstehen?!

Jetzt wo du es erklärt hast ist es verständlich. Davor nicht. Muss aber generell eine ziemlich miese Spezifikation sein, denn die Klasse hat ja auch so noch reihenweise Attribute die nicht zur Spezifikation gehören.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
Hyperion
Moderator
Beiträge: 7471
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Beitragvon Hyperion » Mittwoch 11. Februar 2009, 18:31

Spricht etwas gegen:

Code: Alles auswählen

In [44]: class Foo(object):
   ....:     def bar(self):
   ....:         pass
   ....:
   ....:

In [45]: f = Foo()

In [46]: f.bar()

In [47]: f.test()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)

/home/nelson/<ipython console> in <module>()

AttributeError: 'Foo' object has no attribute 'test'

In [48]: class Foo(object):
   ....:     def test(self):
   ....:         raise AttributeError()
   ....:
   ....:

In [49]: f = Foo()

In [50]: f.test()
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)

/home/nelson/<ipython console> in <module>()

/home/nelson/<ipython console> in test(self)

AttributeError:

Ist zwar nicht wirklich sensationell, aber man könnte doch so die geerbten Methoden quasi verstecken? Aber vermutlich kommt man über die Elternklasse dann immer noch an die Methoden fällt mir grad ein ...

Wobei ich das Problem auch nicht so sehe: Solange die Methoden vorhanden sind, die man haben möchte / muss, stört es doch eigentlich nicht, wenn es auch noch "mehr" gibt?!? Das geht so ein wenig in die Richtung Java-Konzepte-Diskussion, die wir neulich im Offtopic hatten.
Benutzeravatar
ms4py
User
Beiträge: 1178
Registriert: Montag 19. Januar 2009, 09:37

Beitragvon ms4py » Mittwoch 11. Februar 2009, 18:35

Und wo ist das Problem, wenn ich die deque nicht als Basisklasse nehme?!
Außer dass ich die pop-Methode neu definieren muss. Und das ist ja wohl nicht der Rede wert.
Ja, die Diskussion wird langsam seltsam...

[ironie]Ohja, und ich hab natürlich zwei Instanzen im Speicher statt einem, DAS ist natürlich ein ausschlaggebendes Argument.[/ironie]
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 11. Februar 2009, 18:41

ice2k3 hat geschrieben:Und wo ist das Problem, wenn ich die deque nicht als Basisklasse nehme?!

Keines, es wäre halt eleganter. Scheint dir aber recht egal zu sein.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
DasIch
User
Beiträge: 2404
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Beitragvon DasIch » Mittwoch 11. Februar 2009, 18:42

ice2k3 hat geschrieben:Und wo ist das Problem, wenn ich die deque nicht als Basisklasse nehme?!

Es ist unelegant → schlechter Code.

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder