# Remove element from list and store it in variable?

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?

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

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)$). • Is there a way to read out each stack without adding or removing anything? Jul 21 '17 at 15:02 • I see, so the stack is nested. But how exactly does that contribute to efficiency? Jul 21 '17 at 15:31 • 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)\$). Jul 21 '17 at 15:39
• @Kagaratsch. For more on this "linked-list" structure, see the answer here. Jul 21 '17 at 16:02
• @Kagaratsch If you need this I think you could add a counter, and increment/decrement it in the definition of push/pop. Nov 18 '17 at 21:13

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, {}}} *)

• @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! Jul 21 '17 at 2:52
• 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. Jul 21 '17 at 2:53
• 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. Jul 21 '17 at 3:34
• @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? Jul 21 '17 at 3:58
• Right, I think stack1 should get updated. Jul 21 '17 at 4:03

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 *)

ClearAll[fetch]
stack={one,two,three};
fetch[stack_List/;stack =!= {}]:={First@stack,Rest@stack}
fetch[stack_List]:={{},{}};


And now

The first definition could also be written as

 fetch[stack_List /; Length@stack > 0] := {First@stack, Rest@stack}

• TakeDrop[stack, 1] also works here Jul 21 '17 at 3:14
• @swish good point. But one needs a check for empty stack. Always too many ways to do the same in Mathematica :) Jul 21 '17 at 3:16

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*)

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


• 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? Jul 21 '17 at 12:36
• Because of HoldFirst s becomes stack (passed by reference)
– eldo
Jul 21 '17 at 15:20
• I see, that's very handy! Jul 21 '17 at 15:28