Implementing a stack

Question

I can't believe we don't have this already.. It's one of the most important data-structures in programming, yet still simple enough to implement it in a code-golf:

Challenge

Your task is to implement a stack that allows pushing and popping numbers, to test your implementation and keep I/O simple we'll use the following setup:

• Input will be a list of non-negative integers

Every positive integer \$n\$ indicates a \$\texttt{push(}n\texttt{)}\$ and every \$0\$ indicates a \$\texttt{pop()}\$ - discarding the top element.

• Output will be the resulting stack

Example

For example if we're given \$[12,3,0,101,11,1,0,0,14,0,28]\$:

$$ \begin{aligned} & 12 & [12] \\ & 3 & [3,12] \\ & 0 & [12] \\ & 101 & [101,12] \\ & 11 & [11,101,12] \\ & 1 & [1,11,101,12] \\ & 0 & [11,101,12] \\ & 0 & [101,12] \\ & 14 & [14,101,12] \\ & 0 & [101,12] \\ & 28 & [28,101,12] \end{aligned} $$

Output will be: \$[28,101,12]\$

Rules

• Input will be a list of non-negative integers in any default I/O format
  • you may use a negative integer to signify the end of a stream of integers
• Output will be a list/matrix/.. of the resulting stack
  • your choice where the top element will be (at the beginning or end), the output just has to be consistent
  • output is flexible (eg. integers separated by new-lines would be fine), the only thing that matters is the order
  • you may use a negative integer to signify the bottom of the stack
• You're guaranteed that there will never be a \$0\$ when the stack is empty

Examples

[] -> []
[1] -> [1]
[1,0,2] -> [2]
[4,0,1,12] -> [12,1]
[8,3,1,2,3] -> [3,2,1,3,8]
[1,3,7,0,0,0] -> []
[13,0,13,10,1,0,1005,5,0,0,0] -> [13]
[12,3,0,101,11,1,0,0,14,0,28] -> [28,101,12]

Answer 1

MATL, 6 bytes

"@?@}x

Input is a row vector of numbers.

The final stack is shown upside down, with the most recent element below.

Try it online! Or verify all test cases.

Explanation

"         % For each element in the input (implicit)
  @       %   Push current element
  ?       %   If non-zero (this consumes the current element)
    @     %     Push current element again
  }       %   Else
    x     %     Delete most recent element
          %   End (implicit)
          % End (implicit)
          % Display (implicit)

Answer 2

Java (JDK 10), 42 bytes

Since "[the] output is flexible [...], the only thing that matters is the order", this changes the input array into a 0-terminated array. Example : [1,0,2] will return [2,0,2] which is to be interpreted as [2,0,2] = [2].

a->{int s=0;for(int v:a)a[v>0?s++:--s]=v;}

Try it online!

Previous versions:

Java (JDK 10), 60 bytes

l->{for(int i;(i=l.indexOf(0))>0;l.remove(i))l.remove(--i);}

Try it online!

Credits:

• -1 byte thanks to O.O.Balance

If I can end the program with errors: 55 bytes

(though everything is properly modified)

l->{for(int i;;l.remove(--i))l.remove(i=l.indexOf(0));}

Try it online!

Answer 3

Sed, 17 Bytes

:;s/[0-9]\+,0//;t

-3 bytes thanks to @OMᗺ, -1 thanks to @eggyal

Because you're guaranteed to never pop an empty list, you don't need anything more than an iterated finite state machine. Regular expressions are a tool for building finite state machines, and sed can iterate. It's a match made in heaven.

Takes input from stdin, like so:

echo '[12,3,0,101,11,1,0,0,14,0,28]' | sed ':;s/[0-9]\+,0,//;t'

Outputs the stack in reverse:

[12,101,28]

Could be smaller by two bytes if my local sed inherently understood character classes like \d, but it doesn't for some reason.

Answer 4

PowerShell, 46 41 40 bytes

$args|%{$x,$a=&({1,$_+$a},{$a})[!$_]};$a

Try it online!

Takes input via splatting, e.g., $z=@(12,3,0,101,11,1,0,0,14,0,28); .\implement-stack.ps1 @z, which on TIO manifests as separate arguments.

$args|%{$x,$a=&({1,$_+$a},{$a})[!$_]};$a    # Full program
$args                                       # Take input via splatting
     |%{                            };      # Loop through each item
              &(              )[!$_]        # Pseudo-ternary, if input is 0 this is 1
        $x,$a=            {$a}              # ... which will pop the first item into $x
           $a=  { ,$_+$a}                   # Else, we append the first item
        $x   =   1                          # ... and drop a dummy value into $x
                                      $a    # Leave $a on pipeline; implicit output

-5 bytes thanks to mazzy.
-1 byte swapping $_ to 1

Answer 5

C (gcc), 62 60 56 55 bytes

-2 -6 bytes thanks to l4m2

-1 byte thanks to ceilingcat.

Uses the permitted notion of -1 terminated arrays. f() calls itself recursively, until fully wound, and then backtracks through the list. r keeps track of how many numbers to discard before printing something. Increases if current item is 0, decreases otherwise. If 0, we need not discard, and can print the number.

r;f(int*l){~*l?f(l+1),*l?r?r--:printf("%d ",*l):r++:0;}

Try it online!

Answer 6

Haskell, 28 bytes

foldl(#)[]
(_:s)#0=s
s#n=n:s

Try it online!

Answer 7

Jelly, 6 bytes

ṣ0Ṗ;¥/

Try it online!

How it works

ṣ0Ṗ;¥/  Main link. Argument: A (array)

ṣ0      Split A at zeroes.
    ¥/  Left-reduce the resulting 2D array by this dyadic chain:
  Ṗ       Pop; discard the last element of the left argument.
   ;      Concatenate the result with the right argument.

Answer 8

R, 45 bytes

o={};for(e in scan())o="if"(e,c(e,o),o[-1]);o

Try it online!

• -4 byte thanks to @Giuseppe

Answer 9

Wolfram Language (Mathematica), 28 bytes

#//.{a___,b_,0,c___}:>{a,c}&

Try it online!

Answer 10

Python 2, 59 57 51 bytes

s=[]
for x in input():s=(s+[x],s[:-1])[x<1]
print s

Try it online!

Answer 11

Python 2, 48 bytes

s=[]
for x in input():s=([x]+s)[2*0**x:]
print s

Try it online!

Answer 12

Brain-Flak, 40 36 bytes

([]){{}{({}<>)<>}([]){{}<>}{}([])}<>

Try it online!

Thanks to @Nitrodon for -4 bytes.

Since Brain-Flak already uses stacks, this is a good puzzle for Brain-Flak.

([]){   while items on stack
    {}      pop stack count
    {       if top element is non-zero
        ({}<>)<> push it on the other stack
    }
    if we're here the stack is either empty or there's a 0 on the stack

    ([])    so, count the stack again
    {{}<>{}<>} if there are items left on the stack, pop the stack count and the last item of the other stack
    {} pop the zero or the stack count
    ([]) count the stack again for next round
}
<>  go to the output stack

Answer 13

Whitespace, 89 bytes

[N
S S N
_Create_Label_LOOP_1][S S S N
_Push_0][S N
S _Duplicate_0][T   N
T   T   _Read_STDIN_as_integer][T   T   T   _Retrieve][S N
S _Duplicate_input][N
T   T   S 
_If_neg_Jump_to_Label_EXIT][S N
S _Duplicate_input][N
T   S T N
_If_0_Jump_to_Label_DROP][N
S N
N
_Jump_to_Label_LOOP_1][N
S S S N
_Create_Label_EXIT][S N
N
_Discard_top][N
S S S S N
_Create_Label_LOOP_2][T N
S T _Print_as_integer][S S S T  S T S N
_Push_10_newline][T N
S S _Print_as_character][N
S T S S N
_Jump_to_Label_LOOP_2][N
S S T   N
_Create_Label_DROP][S N
N
_Discard_top][S N
N
_Discard_top][N
S N
N
_Jump_to_Label_LOOP_1]

Letters S (space), T (tab), and N (new-line) added as highlighting only.
[..._some_action] added as explanation only.

Takes the input-list new-line separated with -1 to indicate we're done with the inputs.

Try it online.

Explanation in pseudo-code:

Start LOOP_1:
  Integer i = STDIN as integer
  If(i is negative):
    Call function EXIT
  If(i is 0):
    Call function DROP
  Go to next iteration of LOOP_1

function EXIT:
  Start LOOP_2:
    Pop and print top as integer
    Print newline
    Go to next iteration of LOOP_2

function DROP:
  Drop the top of the stack
  Go to next iteration of LOOP_1

Answer 14

Python 2, 60 59 57 56 bytes

l=input()
while 0in l:i=l.index(0);l[i-1:i+1]=[]
print l

Try it online!

---

Saved:

• -1 byte, thanks to pushkin

Answer 15

brainfuck, 214 150 bytes

>>,[>++++++[-<-------->]+<[>+++++[-<++++++++>]]>[-<<<[[-]<],[-]>>>>-<<]>>+[<<+<,----------[++++++++++>-]>[->>-<]>[->+<]>]<<<,]<<[[<]++++++++++<]>>[.>]

Reads input as numbers separated by newlines. This must include a single trailing newline. Also expects no leading zeros on each number. Output as a similar newline separated list

Try it online!

Explanation ^{that isn't really an explanation but is actually just the version I was working on with the comments and stuff which may or may not actually be useful to anyone}

Stack format:
0 (0 \d*)*


>>,[
    Setup digit == '0' conditional
    >++++++
    [-<-------->]
    +
    <[
        Read digit != '0'
        Restore the char code
        cond1 is already 1 at this stage
        >+++++
        [-<++++++++>]
    ]>[
        Read digit == '0'
        -
        Pop previous value
        <<<[
            [-]<
        ]
        Skip next input (assumed to be newline)
        ,[-]
        Skip following loop by unsetting loop flag
        >>>>-
        <<
    ]
    
    Move to next stack frame
    >
    Set loop flag
    >+[
        Set bit used for conditional
        <<+
        Read next character
        <,
        Compare with '\n'
        ----------[
            Not '\n': restore the char code
            ++++++++++
            
            >-
        ]>[
            -
            == '\n': Leave as 0
            Unset loop flag
            >>-
            <
        ]
        
        Copy loop flag along
        >
        [- > + <]
        
        Move to loop flag of next stack frame
        >
    ]
    
    <<<
,]


Fill in with newlines
<<[
    Skip to the cell before this value
    [<]
    Put a newline in there
    ++++++++++
    Move to next value
    <
]

Now the tape has the exact values we need to output
>>[.>]

Answer 16

JavaScript, 40 bytes

Outputs in reverse order.

a=>a.map(x=>x?o.push(x):o.pop(),o=[])&&o

Try it online

1 byte saved thanks to Herman L.

Answer 17

Brain-Flak, 32 bytes

([]){{}{({}<>)<>}{}<>{}<>([])}<>

Try it online!

Uses -1 to signify the end of the array (but any number will do really).

Answer 18

V, 10 bytes

ò/ 0⏎b2dw0

Try it online!

Explanation

ò           " run the following, until an error occurs
 / 0⏎       " | goto next zero with space in front (errors if none)
     b      " | jump one word back (to the beginning of element to pop)
      2     " | twice (element & zero itself)
       dw   " | | delete word
         0  " | goto beginning of line

---

Equivalent in Vim, 16 bytes

qq/ 0⏎b2dw0@qq@q

Try it online!

Explanation

Pretty much the same, except recording a macro q and recursively call it:

qq                " record macro q
  / 0⏎b2dw0       " same as in V
           @q     " recursively call q (aborts on error)
             q    " quit recording
              @q  " execute the macro q

Answer 19

Brachylog, 21 bytes

~c₃Ckt[İ,0]≠∧C⟨hct⟩↰|

Try it online!

-1 byte, and more importantly this feels like a much less clunky way of doing this.

~c₃                     % Partition the input into 3 subarrays
   C                    % Call that array-of-arrays C
    kt[İ,0]             % Its second element should be of the form [Integer, 0]
           ≠            % And its elements shouldn't be equal (i.e. 
                        %   the Integer shouldn't be 0)
            ∧C⟨hct⟩     % Then, remove that [İ, 0] element from C
                   ↰    % And call this predicate recursively
                    |   % When the above fails (when it can't find a partition with 
                        %  [İ, 0] in it), then just output the input

Alternate 21 byter: ∋0∧ℕ₁;0;P↺c;Qc?∧P,Q↰| Try it online!

---

Older code:

22 bytes

∋0&b,1;?z{=|¬∋0&}ˢtᵐ↰|

Try it online!

∋0           If input contains a 0, 
&b           Remove input's first element, getting list of "next" elements
,1           Append 1 to that to handle last element
;?z          Zip that with input
{      }ˢ    Select only zipped pairs where
 =|          both elements are equal (to keep 0s followed by 0s)
   ¬∋0&      or the pair doesn't contain a 0
             this removes both the (pairs containing the) value
              that is followed by a 0, and the 0 itself
tᵐ           Recover back the (filtered) input array elements from the zip
↰            Call this predicate recursively 
|            If input contains no 0s, input is the output 

Answer 20

05AB1E, 9 bytes

vy>i¨ëy)˜

Try it online or verify all test cases.

Explanation:

v        # For-each of the items in the input-list:
 y>i     #  If the current item is 0:
  ¨      #   Pop the top item of the list
 ë       #  Else:
  y      #   Push the current item to the stack
   )     #   Wrap the entire stack into a list
         #    i.e. 12 → [12]
         #    i.e. [12] and 3 → [[12], 3]
    ˜    #   Flatten the stack
         #    i.e. [[12], 3] → [12, 3]
         # (and output the list implicitly after the loop)

---

9 bytes alternative:

vy_i\ëy])

Try it online of verify all test cases.

Explanation:

v        # For-each of the items in the input-list:
 y_i     #  If the current item is 0:
  \      #   Discard top item of the stack
 ë       #  Else:
  y      #   Push the current item to the stack
]        # Close both the if-else and for-each (short for `}}`)
 )       # Wrap the entire stack into a list (and output implicitly)

PS: If the output should have been reversed to match the test cases in the challenge description, we can add a trailing R to the second version (so 10 bytes), which reverses the list. Try it online or verify all test cases.

Answer 21

Retina 0.8.2, 18 bytes

^
,
+1`,\d+,0

^,

Try it online! Link includes test cases. Explanation:

^
,

Prefix an extra ,.

+1`,\d+,0

Process all pop operations.

^,

Remove the , if it's still there.

Reversing the numbers would cost an extra 8 bytes:

O^$`\d+

Answer 22

Ruby, 36 bytes

->a{b=[];a.map{|x|x>0?b<<x:b.pop};b}

Try it online!

Anonymous lambda. Outputs in reverse order.

Answer 23

Brain-Flak, 36 bytes

([]){{}{(({}<>))(<>)}{}<>{}<>([])}<>

Try it online!

#Let's call the two stacks in and out

([]){{}                      ([])}    # while not in.empty()
       {        (  )}{}               # if in.peek() != 0
        (({}<>)) <>                   # a = in.pop; out.push(a); out.push(a)
                       <>{}<>         # out.pop()
                                  <>  # switch to out to be printed

Answer 24

Java 10, 75 72 bytes

n->{var s="";for(int i:n)s=(s+","+i).replaceAll(",\\d+,0","");return s;}

Outputs separated by a comma. Top of the stack is last. Try it online here.

Thanks to Olivier Grégoire for golfing 2 bytes.

Please check out Kevin Cruijssen's and Olivier Grégoire's Java answers as well. They take a list-based approach instead, with the latter beating mine by a tidy margin.

Ungolfed:

n -> { // lambda taking an integer array as argument and returning a String
    var s = ""; // we'll be using a String to implement and output the stack
    for(int i : n) // loop through the array
        s = (s + "," + i) // append the next number
               .replaceAll(",\\d+,0", ""); // remove any number followed by a zero
    return s; // output the resulting stack
}

Answer 25

GolfScript, 14 12 bytes

~{.{;}if}/]`

Try it online!

~{.{;}if}/]` Full program, implicit input
~            Eval input
 {      }/   Foreach:
      if       If the value is truthy (!= 0):
  .              Push itself
   {;}         Else: pop the top value
          ]` Push as array representation
             Implicit output

Answer 26

Perl 5 -p, 17 bytes

Thanks @sundar and @DomHastings

s/\d+ 0 ?//&&redo

Try it online!

Answer 27

><>, 25 bytes

i:?\~~
(0:/:^?
!?l:!<oan;

Try it online! (input must be written in ascii. otherwise use this one)

How it works

i:?\~~ checks for 0, continues to ~~ to delete previous entry. otherwise go down to:

(0:/:^? which checks for -1 (no more input), then wrap up to delete -1 and loop:

!?l:!<oan; which outputs each number with a newline, then ends when stack emptied

Answer 28

Husk, 6 bytes

Since there's no Husk answer already and it's my favourite golfing-lang:

F`?:tø

Try it online!

Explanation

F`?:tø  --
F    ø  -- foldl (reduce) with [] as the initial accumulator
 `      -- | flip arguments of
  ?:    -- | | if truthy: apply cons (prepend) to it
    t   -- | | else: return tail
        -- | : returns a function, either prepending the element or dropping 1 element

Alternative solution, 6 bytes

Instead of flipping, we can also just reverse the list and then use a right-fold: Ḟ?:tø↔

Answer 29

Warning: Lots of lines ensue. You have been warned.

---

CJam, 17 bytes

Most dangerous code
(Assumes the stack elements can be separated by only spaces in the output and that the input array can be whatever form we wish)

q~{X0={;}X?}fX]S*

Try it online!

Explanation

q                                    Reads input string
 ~                                   Instantly convert to array since the string is in the CJam format
  {        }fX                       For loop
   X0=                               If X (the array element currently being checked) is equal to 0
      {;}                            Pop the top element from the stack
         X                           Else push X onto the top of the stack
          ?                          If-Else flag
              ]                      Collate all stack elements into an array
               S*                    Put a space between each array element

---

Alternate Code #1, 27 bytes
(Assumes stack elements have to be output in the format shown in the question and that the input array can be whatever form we wish)

q~{X0={;}X?}fX]',S+*'[\+']+

Try it online!

Explanation

q                                    Reads input string
 ~                                   Instantly convert to array since the string is in the CJam format
  {        }fX                       For loop
   X0=                               If X (the array element currently being checked) is equal to 0
      {;}                            Pop the top element from the stack
         X                           Else push X onto the top of the stack
          ?                          If-Else flag
              ]                      Collate stack items into an array
               ',S+                  Add together a comma and a space to create a delimiter
                   *                 Apply the delimiter to the stack
                    '[\+             Append left bracket to the left of the stack text
                        ']+          Append right bracket to the right of the stack text

---

Alternate Code #2, 24 bytes
(Assumes the stack elements can be collated in the output and that the input array has to be in the exact format shown in the question)

q',/~]S*~{X0={;}X?}fX]S*

Try it online!

Explanation

q                        Read input string
 ',/                     Separate by commas (since commas are an invalid array delimiter in CJam)
    ~                    Turn string into an array of substrings that make up the array
     ]S*                 Add spaces in between input numbers to prevent collation in the array
        ~                Turn the string into a valid array representative of the original
         {        }fX    For loop
          X0=            If X (the array element currently being checked) is equal to 0
             {;}         Pop the top element from the stack
                X        Else push X onto the top of the stack
                 ?       If-Else flag
                     ]   Collate all stack elements into an array
                      S* Add a space between each element

---

Safest code for this, 34 bytes
(Assumes stack elements have to be output in the format shown in the question and that the input array has to be in the exact format shown in the question)

q',/~]S*~{X0={;}X?}fX]',S+*'[\+']+

Try it online!

Explanation

q                                      Read input string
 ',/                                   Separate by commas (since commas are an invalid array delimiter in CJam)
    ~                                  Turn string into an array of substrings that make up the array
     ]S*                               Add spaces in between input numbers to prevent collation in the array
        ~                              Turn the string into a valid array representative of the original
         {        }fX                  For loop
          X0=                          If X (the array element currently being checked) is equal to 0
             {;}                       Pop the top element from the stack
                X                      Else push X onto the top of the stack
                 ?                     If-Else flag
                     ]                 Collate stack items into an array
                      ',S+             Add together a comma and a space to create a delimiter
                          *            Apply the delimiter to the stack
                           '[\+        Append left bracket to the left of the stack text
                               ']+     Append right bracket to the right of the stack text

---

Thanks to @Jo King for pointing out that the ones with the collated output are invalid since things like [12] and [1,2] would be indistinguishable.

Thanks also to @Jo King providing a very suitable alternative for the collated outputs and cutting off 9 bytes!

Answer 30

Red, 64 bytes

func[b][a: copy[]foreach n b[either n > 0[insert a n][take a]]a]

Try it online!