Dynamically growing an array to implement a stack
M. Hamed
assign to a non-existent index in an array. For example:
a = [0,1]
a[2] =========> Generates an error
I can use a.append(2) but that always appends to the end. Sometimes I
want to use this array as a stack and hence my indexing logic would be
something like:
If you are already at the end (based on your stack pointer):
use append() then index (and inc your pointer)
if not:
index directly (and inc your stack pointer)
If feel that doing this everytime I want to add an element that I have
to check whether it exists or not is too much. Is there any simpler
way to do this?
I know I can do something like this:
a = numpy.zeros(MAX_STACK_SIZE)
but I don't want to predetermine the stack size.
Any help?
Thanks
Paul McGuire
> I have trouble with some Python concept. The fact that you can not
> assign to a non-existent index in an array. For example:
>
> a = [0,1]
> a[2] =========> Generates an error
>
> I can use a.append(2) but that always appends to the end. Sometimes I
> want to use this array as a stack and hence my indexing logic would be
> something like:
>
> If you are already at the end (based on your stack pointer):
> use append() then index (and inc your pointer)
> if not:
> index directly (and inc your stack pointer)
??? The stack pointer is *always* at the end, except don't actually
keep a real stack pointer, let list do it for you. Call append to
push a value onto the end, and pop to pull it off. Or if you are
really stuck on push/pop commands for a stack, do this:
>>> class stack(list):
... push = list.append
...
>>> ss = stack()
>>> ss.push("x")
>>> ss.push("Y")
>>> ss
['x', 'Y']
>>> ss.pop()
'Y'
>>> ss.pop()
'x'
>>> ss.pop()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
IndexError: pop from empty list
-- Paul
Patrick Maupin
Well, if you never want to add intermediate data between your new
element and the stack, you can just do:
stack[index:index + 1] = [newelement]
Regards,
Pat
M. Hamed
Paul, thanks for your example. wasn't familiar with the stack class. I
feel Patrick's method is a lot simpler for my purpose.
Regards.
Lie Ryan
> Thanks Patrick, that is what I was exactly looking for.
>
> Paul, thanks for your example. wasn't familiar with the stack class.
The stack class is nothing but a wrapper that renames append() to
push(); everything you need can be fulfilled by the regular list.
> I feel Patrick's method is a lot simpler for my purpose.
No you don't.
>> Well, if you never want to add intermediate data between your new
>> element and the stack, you can just do:
>>
>> stack[index:index + 1] = [newelement]
that is effectively the same as:
stack.insert(index, newelement)
But if you really want to use list as a stack, you don't want to manage
your stack pointer manually; let `list` manage the stack pointer for you
and use .append() and .pop()
Patrick Maupin
> Thanks Patrick, that is what I was exactly looking for.
You're welcome!
But I have to say, you should consider what Paul and Lie are saying.
In general, when I use a stack, I just use append() and pop(), as they
mention, and let the list automagically keep track of the pointer. (I
don't usually even bother subclassing list, but I will often write
something like push = mylist.append; pop = mylist.pop)
But since I don't know about your specific problem, and you obviously
didn't know you could assign to a slice of a list in this manner, I
focused on what you were asking for.
Paul and Lie are trying to focus more on what you really need than
what you asked for, and since you mentioned the magic word "stack",
they immediately assumed that you meant a standard LIFO, where you
only do operations on a single element at a time on one end of the
list. That's a fair assumption, and if that's the case, you should
consider whether you even need to keep an index around, or you can do
as they suggested and just let the current length of the list serve as
your index.
Regards,
Pat