       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
> 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:= a = {};

In:= Do[push[a,j], {j,1,10}]

In:= a
Out= {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}

In:= Do[x = pop[a]; Print[x], {5}]
10
9
8
7
6

In:= a
Out= {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[]}, a = a[]; tmp]

In:= a = {};

In:= Do[betterpush[a,j], {j,1,10}]

In:= a

Out= {10, {9, {8, {7, {6, {5, {4, {3, {2, {1, {}}}}}}}}}}}
In:= Do[x = betterpop[a]; Print[x], {5}]
10
9
8
7
6

In:= a
Out= {5, {4, {3, {2, {1, {}}}}}}

Here is a demo of the speed difference.

In:= a1 = {}; a2 = {};

In:= Timing[Do[push[a1,j], {j,1,1000}]]
Out= {0.28 Second, Null}

In:= Timing[Do[push[a1,j], {j,1,10000}]]
Out= {24.62 Second, Null}

In:= Timing[Do[betterpush[a2,j], {j,1,10000}]]
Out= {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