7
$\begingroup$

In many programming languages there are functions that remove an element from a set while giving back that element. E.g. I'd like to have a function FetchFromStack that does the following:

stack = {one, two, three};
element = FetchFromStack[stack]
stack

one

{two, three}

Of course I can implement it like:

If[stack==={}, element=False, element = stack[[1]]]
If[Length[stack]>1, stack = stack[[2;;]], stack={} ]

but this seems much too hacky of a solution to me. Is there a proper routine in Mathematica that does this? If not, what would be the best way to implement it?

$\endgroup$
  • 1
    $\begingroup$ Should there be any output if stack == {}? $\endgroup$ – march Jul 21 '17 at 2:44
  • $\begingroup$ @march good point! In that case fetchFromStack should return False. $\endgroup$ – Kagaratsch Jul 21 '17 at 2:46
7
$\begingroup$

Maybe something like:

push[stackID_][e_] := Last[$Stack[stackID] = {$Stack[stackID], e}]

pop[stackID_] := Replace[$Stack[stackID],
    {
    {s_, e_} :> ($Stack[stackID] = s; e),
    _ -> Missing["Empty"]
    }
]

stack[stackID_] := $Stack[stackID]

empty[stackID_] := Quiet[Unset@$Stack[stackID];, Unset::norep]

$Stack[_]={};

For example, push 1 through 5 to stack id 1:

push[1] /@ Range[5]

{1, 2, 3, 4, 5}

Then, pop 6 elements from stack id 1:

Table[pop[1], {6}]

{5, 4, 3, 2, 1, Missing["Empty"]}

Note that the stack is implemented as a nested list instead of a flat list for efficiency reasons. So:

empty[1]
push[1] /@ Range[3];
stack[1]

{{{{}, 1}, 2}, 3}

Changing the implementation to a flat list is simple, although you will take a performance hit for long stacks ($O(n)$ vs $O(1)$).

$\endgroup$
  • $\begingroup$ Is there a way to read out each stack without adding or removing anything? $\endgroup$ – Kagaratsch Jul 21 '17 at 15:02
  • $\begingroup$ I see, so the stack is nested. But how exactly does that contribute to efficiency? $\endgroup$ – Kagaratsch Jul 21 '17 at 15:31
  • 1
    $\begingroup$ I couldn't find a good question/answer discussing why Append/AppendTo is bad, but the short answer is that AppendTo[list, elem] makes a copy of list (hence $O(n)$) while list = {list, elem} does not (hence $O(1)$). $\endgroup$ – Carl Woll Jul 21 '17 at 15:39
  • 1
    $\begingroup$ @Kagaratsch. For more on this "linked-list" structure, see the answer here. $\endgroup$ – march Jul 21 '17 at 16:02
  • 1
    $\begingroup$ @Kagaratsch If you need this I think you could add a counter, and increment/decrement it in the definition of push/pop. $\endgroup$ – Carl Woll Nov 18 '17 at 21:13
5
$\begingroup$

Here is one possible implementation that is somewhat Mathematica-idiomatic. Using your list:

stack = {one, two, three};

ClearAll@fetchFromStack
Attributes[fetchFromStack] = HoldAll
fetchFromStack[stack_Symbol /; Evaluate[stack] === {}] := (stack = {};False)
fetchFromStack[stack_Symbol : {elem_}] := (stack = {}; elem)
fetchFromStack[stack_Symbol] := Module[{x = stack[[1]]},
  stack = stack[[2 ;;]];
  x
 ]

Then:

stack = {one, two, three};
Table[{fetchFromStack[stack], stack}, {5}]
(* {{one, {two, three}}, {two, {three}}, {three, {}}, {False, {}}, {False, {}}} *)
$\endgroup$
  • $\begingroup$ @Kagaratsch. Thanks, but that accept was too fast! I feel like this question could get a lot of attention and have some really good answers, and it won't get as much attention if there's an accept on it! $\endgroup$ – march Jul 21 '17 at 2:52
  • 1
    $\begingroup$ OK, removed it for now. :) Will put it back tomorrow, if no one shows up with a different implementation that does this orders of magnitude faster. $\endgroup$ – Kagaratsch Jul 21 '17 at 2:53
  • $\begingroup$ The problem with this approach is if you have two stacks, stack1 and stack2, and you try something like: curStack = stack1; fetchFromStack[curStack] it won't work. $\endgroup$ – Carl Woll Jul 21 '17 at 3:34
  • $\begingroup$ @CarlWoll. I'm not sure I follow, so I might not understand something about how "stack"s are supposed to be interact. If stack1 = {one, two, three}, and we run curStack = stack1;, then the definition curStack = {one, two, three} is associated with curStack, and it gets updated using fetchFromStack as normal. Is the problem that fetchFromStack[currStack] won't update stack1? Is that the desired functionality? $\endgroup$ – march Jul 21 '17 at 3:58
  • $\begingroup$ Right, I think stack1 should get updated. $\endgroup$ – Carl Woll Jul 21 '17 at 4:03
5
$\begingroup$

One more:

ClearAll[fetch];
SetAttributes[fetch, HoldFirst];
fetch[stack_Symbol] := If[Length[stack] > 0,
  Module[{h}, {{h}, stack} = TakeDrop[stack, 1]; h],
  False
]

Now

stack = {one, two, three};
fetch[stack]
fetch[stack]
fetch[stack]
fetch[stack]
(* one *)
(* two *)
(* three *)
(* False *)
$\endgroup$
4
$\begingroup$
ClearAll[fetch]
stack={one,two,three};
fetch[stack_List/;stack =!= {}]:={First@stack,Rest@stack}
fetch[stack_List]:={{},{}};

And now

Mathematica graphics

The first definition could also be written as

 fetch[stack_List /; Length@stack > 0] := {First@stack, Rest@stack}
$\endgroup$
  • 3
    $\begingroup$ TakeDrop[stack, 1] also works here $\endgroup$ – swish Jul 21 '17 at 3:14
  • $\begingroup$ @swish good point. But one needs a check for empty stack. Always too many ways to do the same in Mathematica :) $\endgroup$ – Nasser Jul 21 '17 at 3:16
3
$\begingroup$

I was thinking of how to not explicitly check for empty set case, that's what I came up with:

SetAttributes[fetchFromStack, HoldFirst];
fetchFromStack[stack_] := Module[{pop},
  {stack, pop} = Reap@ReplacePart[stack, 1 :> (Sow[First@stack]; Nothing)];
  FirstCase[pop, {x_} :> x, False]
  ]

stack = {one, two, three}
fetchFromStack[stack]
fetchFromStack[stack]
fetchFromStack[stack]
fetchFromStack[stack]
(*one, two, three, False*)
$\endgroup$
3
$\begingroup$
SetAttributes[fetch, HoldFirst];
fetch[s_ /; Length@s > 0] := With[{o = First@s}, s = Rest@s; o]
fetch[_] := False

stack = {1, 2, 3, 4};

Table[{fetch@stack, stack}, {Length@stack + 1}] // MatrixForm

enter image description here

$\endgroup$
  • $\begingroup$ Does this mean, even though s is an internal variable of routine fetch, it still saves its changes (s = Rest@s;) into the outside list stack that was passed to it? Isn't that kind of weird? $\endgroup$ – Kagaratsch Jul 21 '17 at 12:36
  • 1
    $\begingroup$ Because of HoldFirst s becomes stack (passed by reference) $\endgroup$ – eldo Jul 21 '17 at 15:20
  • $\begingroup$ I see, that's very handy! $\endgroup$ – Kagaratsch Jul 21 '17 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.