8
$\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$
2
  • 1
    $\begingroup$ Should there be any output if stack == {}? $\endgroup$
    – march
    Jul 21, 2017 at 2:44
  • $\begingroup$ @march good point! In that case fetchFromStack should return False. $\endgroup$
    – Kagaratsch
    Jul 21, 2017 at 2:46

7 Answers 7

9
$\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$
9
  • $\begingroup$ Is there a way to read out each stack without adding or removing anything? $\endgroup$
    – Kagaratsch
    Jul 21, 2017 at 15:02
  • $\begingroup$ I see, so the stack is nested. But how exactly does that contribute to efficiency? $\endgroup$
    – Kagaratsch
    Jul 21, 2017 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, 2017 at 15:39
  • 1
    $\begingroup$ @Kagaratsch. For more on this "linked-list" structure, see the answer here. $\endgroup$
    – march
    Jul 21, 2017 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, 2017 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$
6
  • $\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, 2017 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, 2017 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, 2017 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, 2017 at 3:58
  • $\begingroup$ Right, I think stack1 should get updated. $\endgroup$
    – Carl Woll
    Jul 21, 2017 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$
2
  • 3
    $\begingroup$ TakeDrop[stack, 1] also works here $\endgroup$
    – swish
    Jul 21, 2017 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, 2017 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$
3
  • $\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, 2017 at 12:36
  • 1
    $\begingroup$ Because of HoldFirst s becomes stack (passed by reference) $\endgroup$
    – eldo
    Jul 21, 2017 at 15:20
  • $\begingroup$ I see, that's very handy! $\endgroup$
    – Kagaratsch
    Jul 21, 2017 at 15:28
3
$\begingroup$

New with Mathematica 12.1, you can use the "Queue" DataStructure. For your example:

ds = CreateDataStructure["Queue"];
ds["Push", #]& /@ {one, two, three};

Then, the elements are:

ds["Elements"]

{one, two, three}

Pop the first element:

ds["Pop"]

one

The queue now only has two elements:

ds["Elements"]

{two, three}

You can also query the length of the queue with:

ds["Length"]

2

or only peek at the first element with:

ds["Peek"]
ds["Elements"]

two

{two, three}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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