Stack class from a nice document

TrustyTony 0 Tallied Votes 848 Views Share

Not my code but I think free to share.

This is intended as beginning point of learning classes or learning data structures.

Read the document
http://mcsp.wartburg.edu/zelle/python/python-first.html

As first exercise, this does not work instead of the while loop in test part:

for i in numbers: print i

Traceback (most recent call last):
File "D:\Python Projects\Tests\stack.py", line 39, in <module>
for i in numbers: print i
TypeError: iteration over non-sequence

Do you find a way to make it work?

class Stack:
    """ 
Here is example of simple Python class from document
http://mcsp.wartburg.edu/zelle/python/python-first.html
which I recommend to read as it helps evangelize virtues of Python

This is intended as start to experiment classes as python has pop() for lists
which is better than fixed stack.

This is not pythonic code, but can you make one class, which is more pythonic,
can be used in for loop etc.
"""

    def __init__(self,size):
        self.data = [None]*size
        self.size = 0

    def push(self,item):
        self.data[self.size] = item
        self.size = self.size + 1    

    def pop(self):
        self.size = self.size - 1
        return self.data[self.size]    

    def is_empty(self):
        return self.size == 0

    def is_full(self):     
        return self.size == len(self.data)

## testing
if __name__=="__main__":
        
    numbers=Stack(100)
    for i in range(10):
        numbers.push(i)

    while not numbers.is_empty(): print numbers.pop()
Gribouillis 1,391 Programming Explorer Team Colleague

Note that if you actually need stacks or fifos in your program, the built-in type collections.deque http://docs.python.org/py3k/library/collections.html?highlight=deque#deque-objects is an efficient implementation whith atomic append and pop.

TrustyTony 888 pyMod Team Colleague Featured Poster

And in that python document is some nice recipe and also a hook to experiment:

The rotate() method provides a way to implement deque slicing and deletion. For example, a pure Python implementation of del d[n] relies on the rotate() method to position elements to be popped:

def delete_nth(d, n):
    d.rotate(-n)
    d.popleft()
    d.rotate(n)

To implement deque slicing, use a similar approach applying rotate() to bring a target element to the left side of the deque. Remove old entries with popleft(), add new entries with extend(), and then reverse the rotation. With minor variations on that approach, it is easy to implement Forth [Edit: /wiki/Forth_%28programming_language%29 ] style stack manipulations such as dup, drop, swap, over, pick, rot, and roll.

TrustyTony 888 pyMod Team Colleague Featured Poster

Notice that example methods first parameter was not self but d.

You can decide what you call yourself.

jcao219 18 Posting Pro in Training

Well, if you want to be able to do this: for i in numberstack , you have to write the stack like this:

class Stack:
    """doc omitted"""

    def __init__(self,size):
        self.data = [None]*size
        self.size = 0

    def push(self,item):
        self.data[self.size] = item
        self.size = self.size + 1    

    def pop(self):
        self.size = self.size - 1
        return self.data[self.size]    

    def is_empty(self):
        return self.size == 0

    def is_full(self):     
        return self.size == len(self.data)
    def __iter__(self):
        for i in range(len(self.data)):
            yield self.data[i]

if __name__ == "__main__":
        
    numbers=Stack(100)
    for i in range(100):
        numbers.push(i)

    for x in numbers:
        print x
TrustyTony 888 pyMod Team Colleague Featured Poster

Change range of first for loop until 20.

What happens?

Tony

jcao219 18 Posting Pro in Training

Try it yourself :)

TrustyTony 888 pyMod Team Colleague Featured Poster

Ok. I tell you, if the hint was not enough.
You should not use range(len(self.data)) but range(self.size) Here my own code including __iter__

class Stack:
    """ 
Here is example of simple Python class from document
http://mcsp.wartburg.edu/zelle/python/python-first.html
which I recommend to read as it helps evangelize virtues of Python

This is intended as start to experiment classes as python has pop() for lists
which is better than fixed stack.

This is not pythonic code, but can you make one class, which is more pythonic,
can be used in for loop etc.
"""

    def __init__(self,size):
        self.data = [None]*size
        self.size = 0

    def push(self,item):
        self.data[self.size] = item
        self.size = self.size + 1    

    def pop(self):
        self.size = self.size - 1
        return self.data[self.size]    

    def is_empty(self):
        return self.size == 0

    def is_full(self):     
        return self.size == len(self.data)

    def __iter__(self):
        for i in range(self.size):
            yield self.data[i]

## testing
if __name__=="__main__":
        
    numbers=Stack(100)
    for i in range(10):
        numbers.push(i)

    for i in numbers: print i
TrustyTony 888 pyMod Team Colleague Featured Poster

I ran into one code, which used poster's own stack class and I wanted to prove how well it worked compared to my own code. I thought to not search and replace and recode around the code, but to do enough implementation based on list.

First I tried:

>>> stack = list
>>> stack.push = list.append

Traceback (most recent call last):
  File "<pyshell#1>", line 1, in <module>
    stack.push = list.append
TypeError: can't set attributes of built-in/extension type 'list'
>>>

No go? No problem, let's inherit:

class stack(list):
    def push(self,x):
        self.append(x)

Let's try to run it. Error code:

expons[expStack.top] += 1
AttributeError: 'stack' object has no attribute 'top'

Ok, it should have attribute for topmost value without removing it. We'll just do one calculated property for it.

@property
    def  top(self):
        return self[-1]

And voila! The program run after simple implementation of prod product of a sequence like sum statement:

from operator import mul
prod = lambda x: reduce(mul, x)
>>> stack([1,2,3,4])
[1, 2, 3, 4]
>>> s = stack([1,2,3,4])
>>> s
[1, 2, 3, 4]
>>> s.pop()
4
>>> s
[1, 2, 3]
>>> s.top
3
>>> type(s)
<class '__main__.stack'>
>>> s
[1, 2, 3]
>>> s.push(4)
>>> s
[1, 2, 3, 4]
>>>

Better name would have been Stack according to Python naming conventions, but the original code used that. Also list built in type deviates from the convention (like other built in types).

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.