MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: MyPrependTo
  • Next by Date: Re: Plot[] problem (plnr) - help !!!
  • Previous by thread: implementing a stack
  • Next by thread: Re: implementing a stack