python, generic functions

Question

How to create generic stack in python? My stack implementation in python:

class Node(object):
    def __init__(self, d):
        self.data = d
        self.nextNode = None

class Stack(object):
    def __init__(self):
        self.top = None

    def push(self, item):
        newNode = Node(item)
        newNode.nextNode = self.top
        self.top = newNode

    def pop(self):
        if self.top == None:
            return None
        item = self.top.data
        self.top = self.top.nextNode
        return item

Now I am putting objects of class Node, but how implement generic Stack so that I can put there anything. For example, if I want create new type of nodes

class NodeWithMin:
    def __init__(self, value, minval):
        self.data = value
        self.minval = minval

And be able create stack based on these type of nodes, so it should be something like this (of course it does not work):

class StackWithMin(qs.Stack):
    def push(self, val):
        if self.peek() != None:
            minval = min(self.peek().value, val)
        else:
            minval = val
        qs.Stack.push(NodeWithMinV2(val, minval))

any idea?

EDIT: it did not work because I have next error:

unbound method push() must be called with Stack instance as first argument (got NodeWithMinV2 instance instead)

I missed self

What do you mean it doesn't work? It looks like you're doing it correctly. — Joe
– Joe, Commented Aug 24, 2012 at 22:43
Why are you trying to roll your own stack instead of using a Python list? list.append(element) to push, element = list.pop() to pop. — Russell Borogove
– Russell Borogove, Commented Aug 24, 2012 at 22:46
Maybe @capoluca is trying to learn how to do generics (or the equivalent) in Python through a well-known data structure? — Joe
– Joe, Commented Aug 24, 2012 at 22:47
Python's list is a generic container. No need to invent a Node class to wrap Python objects. This seems like a Java programmer refusing to use Python's dynamic typing. — Ned Batchelder
– Ned Batchelder, Commented Aug 25, 2012 at 0:58

dstromberg · Accepted Answer · 2012-08-24 22:53:34Z

2

You can just use a list, but I totally understand how you might want something better abstracted.

You can also use a deque, in the collections module. It can add or remove from either end, and is better abstracted than a list.

What you have looks good. If you want to put something with a minimum in it, just create a new class, and pass instances of it into your push method as the item argument.

I'm kind of guessing here, but if what you want is a priority queue, where you can pop the least valued node rather than just the thing at a given end by push chronology, you could check out the heapq module. It's not terrifically abstracted either, but it works, and it's fast, and there's nothing to stop you from abstracting it better yourself.

answered Aug 24, 2012 at 22:53

dstromberg

7,2432 gold badges31 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

python, generic functions

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related