[atraub]

Hey everybody, I wrote a couple of snippets recently, one for a stack and one for a queue. One thing I wanted to be careful of was to restrict the functionality of the datastructures, i.e. you can't add an element to the bottom of a stack... then it's not a stack anymore.

Of the functionality I included, there was at least one function that I debated on implementing... reverse. Should you be able to reverse a Queue or a Stack? On one hand, after you reverse a queue, it still operates on FIFO, however, none the first element you added will now be the last one you remove, which certainly is not FIFO.

What if I made reverse return a copy of the queue rather than make it in-place?

What do you guys think? Should I keep it or pitch it? What other functions do you think these data structures should have that might not seem obvious?

Also, feel free to lament over stupid implementations of these structures

This post has been edited by atraub: 06 May 2012 - 08:53 PM

[dorknexus]

If you are trying to write a general purpose Stack structure then stick to the essentials and let your users extend the functionality where they need it.

[atraub]

I guess you're right, it's hard to resist the urge to be fancy though

[baavgai]

For stack, push and pop. For a stack you really don't need any more than that. You can always pop, decide you don't want it, and push it back restoring the state of the stack. Though you might be tempted to add peek.

For a queue, it's pretty much to same. I've seen enqueue and dequeue or just add and remove. For a queue you do need a peek, because a value removed can't be put back in place.

For both, I like to see "empty" or "hasMore". Though, of course, your method for removing an item should have some way of dealing with empty. Which means your peek should also deal with empty.

That's about it. I don't like seeing size in these things; it adds complexity to what's really very simple. The user can count if they need to.

Note, in the modern world of programming, these are best suited to be interfaces. The underlying code could be a panacea that addresses all kinds of collection operations.

[ishkabible]

Well, I think there should be a way to traverse the elements of the stack without copying the whole structure so just push and pop would be a no go for me. C++ has iterator methods 'begin' and 'end' that allow you to traverse its elements and using iterators you can efficiently reverse it(and much more)

I agree with the design philosophy of "minimal complete interface" so long as it's complete which to me means providing an abstraction to meddle with the details of the structure in a generic way.

for stack:
*push
*pop
*is empty or size(size can act as 'is empty' if 0 is considered false in the language. I prefer size)
*begin(C++ solution, python may beg a different solution)
*end(see above)
**size(I would like to see it personally)

queue is same just push and pop have different meanings

This post has been edited by ishkabible: 07 May 2012 - 06:38 AM

[atraub]

Thanks for the input. It is hard to resist the urge to put in more stuff, if only to show off . So far, here is a list of my functions for stack, queue has essentially the same functions:

__author__ = "atraub"
__date__= "5/5/2012"


class Stack:
    """Implements a basic stack class in Python using a list"""
    def __init__(self, *elements):
        """intializes a stack *elements allow you to include elements in stack constructor"""
        self.__stack = list(elements)
            
    def push(self,element):
        """add element to the end of the stack"""
        self.__stack.append(element)
            
    def pop(self):
        """remove and return last element from stack"""
        if len(self.__stack) == 0:
            raise IndexError("pop from empty stack")
        return self.__stack.pop()
        
    def peek(self):
        """view top element of stack"""
        if len(self.__stack) == 0:
            raise IndexError("can't view top element of empty stack")
        return self.__stack[-1]

    def isEmpty(self):
        """returns true if stack is empty"""
        return len(self.__stack) == 0

    def count(self,value):
        """counts the number of occurences of a specified value in a stack"""
        return self.__stack.count(value)

    def extend(self, iterable):
        """allows you to add an iterable to the end of stack"""
        self.__stack.extend(iterable)

    def index(self,value):
        """finds the index of a specified value"""
        try:
            return self.__stack.index(value)
        except ValueError:
            raise ValueError(str(value)+" not in stack")

    def clear(self):
        """empties the stack"""
        self.__stack = []

    def __len__(self):
        """returns the length of the stack"""
        return len(self.__stack)

    def __str__(self):
        """returns a string representation of a stack for printing"""
        return str(self.__stack)

    def __repr__(self):
        """creates a string representation of a stack"""
        return repr(self.__stack)

    def __add__(self,iterable):
        """overloads the + operator for adding iterables to stacks"""
        return Stack(*(self.__stack + (list(iterable))))

    def __iter__(self):
        """gets an iterator for a stack"""
        return iter(self.__stack)

    def __contains__(self,element):
        """check if element exists in stack, overloads the 'in' operator"""
        return element in self.__stack

The methods beginning with 2 underscores are python builtin methods that I'm overloading (ok Python doesn't support method overloading, but for simplicity, it's overloading). I had originally based it off of Python's list (it's version of array list) so I was essentially cloning all the methods that were similar (which is why I initially had reverse).

Are Extend and count over the top? I kinda like them, extends allow you to easily plug another queue on the back of an existing one... too much?

__iter__ creates an iterator, which is how we can accomplish looping through the stack, I'm lookin at you ishkabible

This post has been edited by atraub: 07 May 2012 - 07:42 AM

[ishkabible]

I don't know what 'extend' does(nvm, you explained I just didn't read) 'extend', 'count' and 'index' seem strange to me. however, you might keep methods that allow you to do certain task faster(because C does them and not python) if they are idiomatic methods(as those seem to be).

above all containers should be idiomatic and consistent(with other containers) so code for containers can be reused.

This post has been edited by ishkabible: 07 May 2012 - 07:24 AM

[atraub]

index too? I guess that makes sense, who cares what the index of a value is if it's a stack, I'll remove it... same is basically true for count I suppose.

I can get rid of extend, __add__ basically does a non-inplace extend.

This post has been edited by atraub: 07 May 2012 - 07:40 AM

[jon.kiparsky]

I agree with the "let the user extend" philosophy.
Stacks and queues are ADTs, which means they should do exactly what their contract says they do. No more, no less.

[atraub]

Alright, I'll give the people what they want, here's what I'm going to submit:

__author__ = "atraub"
__date__= "5/5/2012"


class Stack:
    """Implements a basic stack class in Python using a list"""
    def __init__(self, *elements):
        """intializes a stack *elements allow you to include elements in stack constructor"""
        self.__stack = list(elements)
            
    def push(self,element):
        """add element to the end of the stack"""
        self.__stack.append(element)
            
    def pop(self):
        """remove and return last element from stack"""
        if len(self.__stack) == 0:
            raise IndexError("pop from empty stack")
        return self.__stack.pop()
        
    def peek(self):
        """view top element of stack"""
        if len(self.__stack) == 0:
            raise IndexError("can't view top element of empty stack")
        return self.__stack[-1]

    def isEmpty(self):
        """returns true if stack is empty"""
        return len(self.__stack) == 0

    def hasMore(self):
        """returns true if stack is not empty"""
        return len(self.__stack) != 0

    def clear(self):
        """empties the stack"""
        self.__stack = []

    def __len__(self):
        """returns the length of the stack"""
        return len(self.__stack)

    def __str__(self):
        """returns a string representation of a stack for printing"""
        return str(self.__stack)

    def __repr__(self):
        """creates a string representation of a stack"""
        return repr(self.__stack)

    def __add__(self,iterable):
        """overloads the + operator for adding iterables to stacks"""
        return Stack(*(self.__stack + (list(iterable))))

    def __iter__(self):
        """gets an iterator for a stack"""
        return iter(self.__stack)

This post has been edited by atraub: 07 May 2012 - 07:50 AM

[atraub]

Hmmm I noticed something interesting, in Python, the constructor for list says that you can pass in an iterable or nothing as a Parameter, for my stack, you can pass in anything.

What happens is, if you pass an iterable (say, a string) as a parameter for a list, python will automatically unpack it for you. So

>>> list("hi") #produces
['h', 'i']

My stack allows you to pass in as many parameters as you want, and expects you to unpack them if you want to, for example

>>> Stack("hi") #produces
['hi']

If you want to unpack it, you'd say

>>> Stack(*"hi") #produces
['h', 'i']

but mine allows you to do this:

>>> Stack(1,2,3,4,5)
[1, 2, 3, 4, 5]
>>> list(1,2,3,4,5)
Traceback (most recent call last):
  File "<pyshell#28>", line 1, in <module>
    list(1,2,3,4,5)
TypeError: list() takes at most 1 argument (5 given)

bah! My way is better, but I know I should follow the conventions of the language... what do you guys think?

This post has been edited by atraub: 07 May 2012 - 08:03 AM

[ishkabible]

I think list already has that in a special syntax([1,2,3,4,5]) so it doesn't need it in the explicit constructor; also can't you have both, just do a little type checking(that's a common idiom in Lua at least)?

in Lua you might have something like

function stack.new(x,...)
  if ... then
    self.__stack = {...} --unpacks the '...' into an array
  else
    --iterate over 'x'
  end
end

*'--' denotes a comment

This post has been edited by ishkabible: 08 May 2012 - 06:32 AM

[atraub]

Haha my original version did that, guess I'll put that back in

Yup

__author__ = "atraub"
__date__= "5/8/2012"


class Stack:
    """Implements a basic stack class in Python using a list"""
    def __init__(self, *elements):
        """intializes a stack, elements allow you to include elements in stack constructor"""
        #allows a list or tuple to be converted into a stack
        if len(elements) == 1:
            try:
                test = iter(elements[0]) #check if the only element is iterable
                self.__stack = list(elements[0])#if it is, make it into a stack
            except TypeError as e:
                self.__stack = elements#if not, put it in the stack
        else:
            self.__stack = list(elements)

    def push(self,element):
        """add element to the end of the stack"""
        self.__stack.append(element)
            
    def pop(self):
        """remove and return last element from stack"""
        if len(self.__stack) == 0:
            raise IndexError("pop from empty stack")
        return self.__stack.pop()
        
    def peek(self):
        """view top element of stack"""
        if len(self.__stack) == 0:
            raise IndexError("can't view top element of empty stack")
        return self.__stack[-1]

    def isEmpty(self):
        """returns true if stack is empty"""
        return len(self.__stack) == 0

    def hasMore(self):
        """returns true if stack is not empty"""
        return len(self.__stack) != 0

    def clear(self):
        """empties the stack"""
        self.__stack = []

    def __len__(self):
        """returns the length of the stack"""
        return len(self.__stack)

    def __str__(self):
        """returns a string representation of a stack for printing"""
        return str(self.__stack)

    def __repr__(self):
        """creates a string representation of a stack"""
        return repr(self.__stack)

    def __add__(self,iterable):
        """overloads the + operator for adding iterables to stacks"""
        return Stack(*(self.__stack + (list(iterable))))

    def __iter__(self):
        """gets an iterator for a stack"""
        return iter(self.__stack)

This post has been edited by atraub: 08 May 2012 - 07:32 PM

[atraub]

aaaand it's up: