How do you do a Drop-Out Stack in python?

Question

I know you guys like getting specific questions about something, but I can't figure out exactly what it is that I'm doing wrong. Maybe it's a lack of understanding, so I thought I could use some more sets of eyes. I'm trying to make what is called a Drop-Out stack in python, Where the value entered at the top pops out the value on the bottom, much like the process used by an Undo function in a program. When I push a new value to the stack, the oldest one should go Bye-Bye.

Here is my Node class:

class Node(object):

    def __init__(self, data, next = None):
        """Instantiates a Node with default next of None"""
        self.data = data
        self.next = next

And the Main body:

from node import Node

class DropOutStack(object):

    def __init__(self, n):
        self._top = None
        self._size = 0
        self._maxlen = n #Appointed last variable that we are interested in finding

    def push(self, newItem):
        """Inserts newItem at top of stack."""
        self._top = Node(newItem, self._top)
        if self._size < self._maxlen:
            self._size += 1
        #Pops off last link if max length has been reached
        else:
            while self._top.next.next != None:
                self._top = self._top.next
            removedItem = self._top.next.data
            self._top.next = None


    def pop(self):
        """Removes and returns the item at top of the stack.
        If stack is empty, returns none with an error message."""
        try:
            oldItem = self._top.data
            self._top = self._top.next
            self._size -= 1
            return oldItem
        except AttributeError:
            print "ERROR: Cannot pop. Stack is empty"
            return None

    def peek(self):
        """Returns the item at top of the stack.
        If stack is empty, returns none with an error message."""
        try:
            return self._top.data
        except AttributeError:
            print "ERROR: Cannot peek. Stack is empty"
            return None            

    def __len__(self):
        """Returns the number of items in the stack."""
        return self._size

    def isEmpty(self):
        return len(self) == 0

    def __str__(self):
        """Items strung from bottom to top."""

        # Helper recurses to end of nodes
        def strHelper(probe):
            if probe is None:
                return ""
            else:
                return strHelper(probe.next) + \
                       str(probe.data) + " "

        return strHelper(self._top)

The problem seems to be located in the push method. I think my code is only going to the third node in the list, but I want it to work with a stack 5 values long (n in this case is 5).

What do you guys think I'm doing wrong? Do I need another .next in there, to make it self._top.next.next.next?

Here is a sample output I am getting with the main function:

def main():
    s = DropOutStack(5)
    for i in xrange(10):
        s.push(i+1)
        print s

1 
1 2 
1 2 3 
1 2 3 4 
1 2 3 4 5 
1 2 3 4 5 6 
1 2 3 4 5 6 7 
1 2 3 4 5 6 7 8 
1 2 3 4 5 6 7 8 9 
1 2 3 4 5 6 7 8 9 10

The output should look like this after 1 2 3 4 5

P.S. I know I could do the same thing with queues. But we're trying to mess with stacks here.

EDIT: Edited push method a bit.

Please describe your problem. What does your program do? What should it do instead? How can the error be reproduced? — Martin Thoma
The program is supposed to create a Drop-Out Stack, which when put in a given length (n) would let you push values into the stack until you reached the given length, removing the oldest value each time you add a new while and never going over given max length (n). Edited main question with sample output — A Computer

John La Rooy John La Rooy · Accepted Answer · 2013-05-03T05:41:14

You should use a local variable (top say) to traverse the stack instead of modifying self._top

def push(self, newItem):
    """Inserts newItem at top of stack."""
    self._top = Node(newItem, self._top)
    #Pops off last link if max length has been reached
    top = self._top
    if self._size >= self._maxlen:
        while top.next.next != None:
            top = top.next
        removedItem = top.next.data
        top.next = None
    else:
        self._size += 1

You should also not increment size if you are adding and removing an item

How do you do a Drop-Out Stack in python?

1 Answers