1

I am trying to solve this problem:

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. There- fore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOf- Stacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack). Bonus: Implement a function popAt(int index) which performs a pop operation on a specific sub-stack.

So I wrote the code:

#!/bin/env python

from types import *

class Stack:

    def __init__(self):
        self.items = []
        self.capacity = 3
        self.stackscount = 0

    def create(self):
        id = self.stackscount + 1
        id = str(id) + "_stack"
        # How to create a new instance of Stack class at runtime ?
        # the __init__ must be run too.

    def push(self, item):
        if self.size() <= self.capacity:
            self.items.append(item)
        else:
            self.create()

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

    def popAt(self):
        pass

    def peek(self):
        return self.items[len(self.items)-1]

    def size(self):
        return len(self.items)

s = Stack()
s.push(10)

How do I create a new s type object dynamically at runtime? I searched on the internet and found that using new.instance or new.classobj is the solution but when I did so my new object did not seem to have items from __init__ function. In python3, type() seems to be the answer but the docs doesn't have any examples.

Improve this question
5
  • You have misunderstood the problem - where is SetOfStacks? Commented Nov 10, 2014 at 14:41
  • I think ultimately the problem is to: 1. create a stack class that is able to push, pop, peek methods 2. the stack class must be able to create new stack objects when a stack object it was pushing to is full. I don't think setofstacks or stack as name for the class matters at this point. Commented Nov 10, 2014 at 14:42
  • 2
    No, the SetOfStacks creates a new Stack when the existing stacks are full. Stack is just responsible for refusing to accept any new items when full, SetOfStacks is responsible for creating additional space. The capacity should be the capacity of each Stack, not the number of stacks in the SetOfStacks (which is initially one and will increase as necessary). Commented Nov 10, 2014 at 14:45
  • Thank you, is this the right direction? <code> class SetOfStacks: def __init__(self): s = Stack() def create(self): self.stackscount = self.stackscount + 1 stacks = [Stack()] </code> Commented Nov 10, 2014 at 15:07
  • No, I would expect your __init__ to contain self.stacks = [Stack()] (i.e. a list, currently containing a single Stack). Assuming create would be called when the last Stack in self.stacks is full, it should .append a new Stack, not create a new list. Commented Nov 10, 2014 at 15:08

3 Answers 3

Reset to default
2

You've confused yourself by referring to a "type object". In Python that means the class itself, not its instances.

To create new Stack objects, simply do what you're already doing: call the Stack class. You can append them to a list:

stacks = [Stack() for _ in range(5)]

However, as jon points out, that won't solve your problem since you haven't defined the SetOfStacks class.

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

1 Comment

Thank you for the reply, I see what you did there. That's exactly what I wanted to do. Your code is simple and clear. So stacks is a list of Stack() objects, right?
1

You could simply use a parent-child relation : when a Stack is full, it creates a child and delegate next pushes to it. It could lead to : 

class Stack:

    def __init__(self, parent = None, id=None):
        self.stackscount = 0
        self.capacity = 3
        self.items = []
        self.parent = parent
        self.id = id
        self.child = None

    def create(self):
        id = self.stackscount + 1
        id = str(id) + "_stack"
        return Stack(self, id)

    def push(self, item):
        if self.size() <= self.capacity:
            self.items.append(item)
        else:
            if self.child is None:
                self.child = self.create()
            self.child.push(item)

    def pop(self):
        if self.child is not None:
            item = self.child.pop()
            if len(self.child.items) == 0:
                self.child = None
        else:
            item = self.items.pop()
        return item

    def popAt(self):
        pass

    def peek(self):
        if self.child is not None:
            item = self.child.peek()
        else:
            item = self.items[len(self.items)-1]
        return item

    def size(self):
        l = len(self.items)
        if self.child is not None:
            l += self.child.size()
        return l

s = Stack()
s.push(10)

popAt is still to be implemented, but I tested it and it correctly creates new stacks when pushing and empties and removes them when popping.

The implementation of popAt will require some evolutions to current pop implementation, to allow removing an intermediate stack :

def pop(self):
    if self.child is not None:
        item = self.child.pop()
        if len(self.child.items) == 0:
            self.child = self.child.child
            if self.child is not None:
                self.child.parent = self
    else:
        item = self.items.pop()
    return item

def popAt(self, stacknumber):
    s = self
    for i in range(stacknumber):
        s = s.child
        if s is None:
            return None
    if len(s.items) == 0:
        return None
    item = s.items.pop()
    if len(s.items) == 0 and s.parent is not None:
        s.parent.child = s.child
        if s.child is not None:
            s.child.parent = s.parent
    return item
Improve this answer

2 Comments

Thanks for this! How do I see all children at once? I tried: [200]: s.child.child.items Out[200]: [5] In [201]: s.child.items Out[201]: [3, 4] In [202]: s.items Out[202]: [1, 2]
In this implementation, you cannot see all children at once, since each Stack has only one child. Is's more like a double linked list.
1

The type() function is indeed what you are looking for. Documentation can be found here: https://docs.python.org/2/library/functions.html#type

You can call it like this:

# Bases is a tuple of parent classes to inherit
bases = Stack,

# Dict contains extra properties for the class, for example if you want to add a class variable or function
dict_ = {}

# Construct the class
YourClass = type('YourClass', bases, dict_)

# Create an instance of the class
your_instance = YourClass()

It looks like you are just looking at instance creation though:

class Stack(object):

    def create(self):
        id = self.stackscount + 1
        id = str(id) + "_stack"
        # How to create a new instance of Stack class at runtime ?
        # the __init__ must be run too.
        stack = Stack()
Improve this answer

2 Comments

thank you for the reply! I don't understand the part Yourclass = type('YourClass', bases, dict_) and then your_instance = YourClass(). To me it looks like am creating a new class based off my Stack class. Can I not just create a new object (an instance) of Stack class directly?
@sindhus: the second example shows you to create instances. The first how to create new classes :)

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.