Re: implementing a stack
- To: mathgroup at smc.vnet.net
- Subject: [mg15980] Re: [mg15922] implementing a stack
- From: Daniel Lichtblau <danl>
- Date: Fri, 19 Feb 1999 03:27:02 -0500
- References: <199902180433.XAA11534@smc.vnet.net.>
- Sender: owner-wri-mathgroup at wolfram.com
Will Self wrote:
>
> I would like to implement a simple stack in Mathematica.
> I can use PrependTo for "push", but in that case how do
> I implement "pop"? I have thought about this and I see
> that I can do it by creating a global variable that keeps
> a list of pairs: the symbols that serve as the names
> of the stacks, and the stacks themselves; and having pop
> and push access and manipulate this list. Is that really
> what I have to do?
>
> Explicitly,
> push[a, 1] should push the number 1 onto the stack a, and
> return nothing,
> and
> pop[a] should return whatever is on the top of stack a, and
> reset a to be the rest of the stack.
>
> Will Self
The short answer is to use the HoldFirst attribute. You can do it as
below, but I'd advise against it.
SetAttributes[push, HoldFirst]
SetAttributes[pop, HoldFirst]
push[a_,e_] := PrependTo[a,e]
pop[a_] := With[{tmp=First[a]}, a = Rest[a]; tmp]
Quick test:
In[25]:= a = {};
In[26]:= Do[push[a,j], {j,1,10}]
In[27]:= a
Out[27]= {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
In[28]:= Do[x = pop[a]; Print[x], {5}]
10
9
8
7
6
In[29]:= a
Out[29]= {5, 4, 3, 2, 1}
Much better is to avoid PrependTo and Rest because for lists of length n
these are O(n) operations in speed and memory usage. Instead just nest
the lists as below.
SetAttributes[betterpush, HoldFirst]
SetAttributes[betterpop, HoldFirst]
betterpush[a_,e_] := a = {e,a}
betterpop[a_] := With[{tmp=a[[1]]}, a = a[[2]]; tmp]
In[46]:= a = {};
In[47]:= Do[betterpush[a,j], {j,1,10}]
In[48]:= a
Out[48]= {10, {9, {8, {7, {6, {5, {4, {3, {2, {1, {}}}}}}}}}}}
In[49]:= Do[x = betterpop[a]; Print[x], {5}]
10
9
8
7
6
In[50]:= a
Out[50]= {5, {4, {3, {2, {1, {}}}}}}
Here is a demo of the speed difference.
In[51]:= a1 = {}; a2 = {};
In[52]:= Timing[Do[push[a1,j], {j,1,1000}]]
Out[52]= {0.28 Second, Null}
In[54]:= Timing[Do[push[a1,j], {j,1,10000}]]
Out[54]= {24.62 Second, Null}
In[55]:= Timing[Do[betterpush[a2,j], {j,1,10000}]]
Out[55]= {0.73 Second, Null}
Daniel Lichtblau
Wolfram Research
- References:
- implementing a stack
- From: wself@viking.emcmt.edu (Will Self)
- implementing a stack