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

Attache, 35 bytes

{y.=[]_:>{If[_>0,Push&_!y,Pop!y]}y}

Try it online!

Actually implements a stack! For the most part.

54 bytes for a "stackless" approach: Fixpoint!{Flat!{#_=1or _@1>0}\Chop[_,1+Rotate[_=0,1]]}. Didn't spend much time golfing it tho.

Explanation

y.=[] defines an array and _:>{...} iterates over the input array. For each element, we either push it if its > 0 or pop the last element. We return y at the end.

Answer 2

Lua, 141 124 bytes

loadstring'p=loadstring("return "..(...))()r={}t=table for i=1,#p do (0<p[i]and t.insert or t.remove)(r,1,p[i])end return r'

Try it online!

---

Explanation

p=loadstring("return "..(...))() -- deserializes the input ('{1, 2, 3}' becomes a table with 3 elements)
r={} -- initializes the result table
t=table -- just to decrease the number of bytes used
for i=1,#p do -- for each element on the input list (table)
  (0<p[i] and t.insert or t.remove)(r, 1, p[i])
   0<p[i] and t.insert   -- if the element (p[i]) is greater than 0 then 'y' is going to be the function table.insert
                       or t.remove -- else it's going to be the remove function
  (                               ) -- this defines which function will be called (insert or remove)

                                   (          ) -- these are the arguments
                                    r, 1, p[i] -- 'r' is the table, 1 is the position, p[i] is the element
                                    -- the insert function receives 3 arguments, the table which to insert, the position and the value
                                    -- the remove function only receives 2, the table and the position
                                    -- There's no problem with that because the third argument will be ignored
end
return r -- returns the 'r' table

This is an anonymous function.

I hope I did a decent job of explaining how it works hahah

Answer 3

Japt, 14 bytes

;NË¥0?Ao:ApDÃA

Try it online!

Actual TIO doesn't work for some reason (it exits with an error, see here) so I've given a page to the ETHproductions' online Japt interpreter.

Answer 4

Java 10, 83 76 75 74 bytes

a->{for(int i=0;i<a.size();)if(a.get(i++)<1){a.remove(i-=2);a.remove(i);}}

-7 bytes thanks to @O.O.Balance.
-1 byte thanks to @OlivierGrégoire.

Modifies the input-List instead of returning a new one to save bytes.

Try it online.

Explanation:

a->{                        // Method with List parameter and no return-type
  for(int i=0;i<a.size();)  //  Loop `i` in the range [0, size)
    if(a.get(i++)<1){       //   If the current item is 0:
      a.remove(i-=2);       //    Remove the previous item
      a.remove(i);}}        //    As well as the current 0

Answer 5

MarioLANG, 51 47 bytes

> ;+[!>(
"====#"
 (![-<:[
 =#=="!<
!)<   #=
#="

Try it online!

Uses -1 as mark for EOF. Explanation follows:

> ;+[!>     Mario walks to the left, reads an integer, adds 1 and checks if it's 0.
"====#"     If the value is not 0 Mario takes the elevator and starts walking to the left.
 (![-<      Mario takes 1 from the value and checks again if it's 0.
 =#=="      If so Mario skips the elevator and moves the pointer to the left, otherwise he
!)<         takes the elevator down and moves the pointer to the right. Either case
#="         Mario ends up taking the elevator to the start of the level.

>(    This is a loop to print what's left in the data values. Mario walks
"     to the right and falls, moving the pointer to the left and checking
:[    if the value pointed is 0. If it is, Mario skips the command to walk to the left and
!<    falls to end the level. Otherwise he walks to the left and takes the elevator,
#=    printing the value pointed as integer and continuing the loop.

Answer 6

C, 138 bytes

int main(int _,char**v){int n=0,*s=0,i;for(;*++v;){i=atoi(*v);if(i){s=realloc(s,n*4+4);s[n++]=i;}else n--;}while(n--)printf("%i ",s[n]);}

Taking advantage of implicit definitions for printf, atoi, etc, and saving an 'int' by declaring i with the other variables.

202 bytes

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main(int _,char**v){int n=0,*s=NULL;for(;*++v;){int i=atoi(*v);if(i){s=realloc(s,n*4+4);s[n++]=i;}else n--;}while(n--)printf("%i ",s[n]);}

Takes input as command line args, outputs to stdout.

Answer 7

TIS, 75 bytes

Code:

@0
MOV UP ACC
JGZ U
JLZ Q
ADD ANY
JRO -4
Q:MOV ANY DOWN
JMP Q
U:MOV ACC ANY

Layout:

1 2 CS
I0 NUMERIC -
O0 NUMERIC - 32

Try it online!

This implementation requires negative numbers for termination, and all values to be delimited by whitespace. Output is delimited by whitespace as well.

Explanation:

I have one regular computation node. Numeric input comes from above, and numeric output is sent below. To the right, there is a stack node.

Here's the code, with more verbose (and additional) labels:

@0
START: MOV UP ACC     # Get input
       JGZ PUSH       # If input is positive, jump to PUSH
       JLZ STOP       # If input is negative, jump to STOP
                      # Else input is zero, continue at POP
POP:   ADD ANY        # Consume one value from the stack, by adding it to the accumulator
       JRO -4         # Jump back up to the top (new input will overwrite the accumulator)
STOP:  MOV ANY DOWN   # Move one value from the stack to output
       JMP STOP       # Just loop this bit forever
PUSH:  MOV ACC ANY    # Push the value we just read onto the stack
                      # Implicitly jump back to the top

You may have noticed that we use ANY to access the stack instead of RIGHT. We can depend on this to go to the correct place because of a quirk in the implementation of both the original game, and this emulator. Replacing all the ANYs by explicit RIGHTs will give the same solution.

I go into more detail about this behavior in note 2 of this other answer.

Limitations:

TIS has some inherent limitations, which limit the abilities of this implementation quite directly.

First, the numeric datatype only accepts values from -999 to 999. Any values outside this range will be clamped to either -999 or 999.

Additionally, TIS stack nodes only allow a maximum depth of 15 items. Some implementations may deadlock when hitting that limit. Others, like this one, will behave in perhaps-unexpected ways. This specific implementation will just dump any overflow values to the output. (Changing the last line to U:MOV ACC RIGHT will make it do the deadlock thing instead).

Answer 8

Kotlin, 90 bytes

{l:List<Int>->var c=0
l.reversed().filter{if(it<1){c++
0>1}else if(c>0){c--
0>1}else 1>0}}

Try it online!

Answer 9

Haskell, 51 43 bytes

run s function Try it online

(#)[]
(_:r)#(0:s)=r#s
r#(x:s)=(x:r)#s
r#_=r

Answer 10

C, 86 Bytes

c;f(a,n)int*a;{if(!n)c=0;else{f(a+1, n-1);!c&&*a&&printf("%d ",*a)||(c+=2*!*a-1,0);};}

Solution based on recursion. Simply load whole array on a system stack and count number of zeroes from the end and either skip current number (if count is positive) or print it. The resulting stack is printed from left to right, ie. head is on the beggining of the line.

Ungolfed version:

int counter;    
void goo(int * a, int n){
        if (!n) {     // end of the array
            counter = 0;
            return;
        }
        goo(a+1, n-1); // try next number
        if (!*a) { cnt++; return;} //increase number of zeroes;
        if (cnt) { cnt--; return;} //skip current number
        printf("%d ", *a); //print it otherwise
    }

Try it on Ideone!

Answer 11

Stax, 8 bytes

âΦε∙GφN²

Run and debug it

Answer 12

Befunge-93, 37 bytes

v<
 |   :<
 $
 $
>>&:1+|
>:v :$<
^._@

Try it online!

My first answer in Befunge!

Uses -1 as EOF. As Befunge already uses a stack internally, I just need to do the push and pop operations given the values at the input.

Answer 13

Ruby, 36 bytes

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

Try it online!

Answer 14

dc, 24 bytes

[*+]sP[?d0=Pd0<l]dslxsxf

Try it online!

Input is one number per line and terminate with a negative number but remember that negative numbers are input with a leading underscore not a dash. There's something punny about implementing this in a stack based language and using the operand stack as the data structure. I'm especially happy about the *+ to "pop" the zero and the previous input.

Answer 15

Scala, 50 bytes

(List[Int]()/:v)((x,i)=>if (i==0)x.tail else i::x)

Usage in the REPL

scala> val v = List(12,3,0,101,11,1,0,0,14,0,28)
v: List[Int] = List(12, 3, 0, 101, 11, 1, 0, 0, 14, 0, 28)

scala> (List[Int]()/:v)((x,i)=>if (i==0)x.tail else i::x)
res0: List[Int] = List(28, 101, 12)

scala>

Answer 16

Chip -o, 53 bytes

)))))))}v9
ABCDEFGH`~8
0123456`v~S
)))))))~]T
abcdefg

Try it online!

For the TIO here, I use a Bash wrapper to allow "easier" number inputs. Numbers are given as values like \x3f, so that printf can do the conversion to the actual byte values for us. However, this is only a wrapper, or test harness, or whatever, and as such it is technically unnecessary.

This treats each byte of input as a 'signed byte', meaning that it will accept values 0 (0x00) through 127 (0x7f) as input, and anything else is a terminator (by virtue of being negative).

However, thanks to the -o flag, we don't need to provide an explicit terminator, since the interpreter will provide an infinite series of -1 (0xff) values upon exhaustion of STDIN.

Explanation:

Chip is a 2D language, so the various elements seen generally interact with their four neighbors. Here's the highlights of the structure:

)))))))}v9      This chunk will, given a positive value, push it onto the stack,
ABCDEFGH`~8     and given zero, pop a value off the stack. Only the low 7 bits are
0123456         stored, since we never need to push/pop negatives.

The stack push control (9) is set from the result of ORing ()) the low 7 bits of the input together (A - G), and XORing (}) the result with the high bit of the input (H). The stack pop control (8) is set by that same calculation, but inverted (~).

The end result is that 1 - 127 cause a push, and -128 - 0 cause a pop.

The stack bits (0-6) push/pop based on what the control values resolve to. If pushing, they will read from the corresponding input bits (A - G).

       H
0123456`v~S   This chunk will pop values to the output (or to the void if we
)))))))~]T    had a zero), and terminate the program if the stack is empty.
abcdefg

When the stack (0 - 6) is popped, we want to send that data to the output bits (a - g). Actually, we always send a value to the output, because in Chip you are either peeking or popping, and difference is only whether the value is kept for the future.

If the input was non-negative, due to the high bit (H) being unset, we want to suppress the output (S), preventing anything from being written to STDOUT.

On the way to the output, we also OR all the bits together again ()) to see if the stack has been emptied. If all bits are zero, it's empty, so we terminate (T). To prevent premature termination (since on the first cycle the stack is empty, and we always either peek or pop), we also use an AND (]) to ensure that we have a negative input value.

Answer 17

Japt -g, 9 bytes

;®?AiZ:Av

Try it online!

Answer 18

R+pryr, 44 bytes

Reduce(pryr::f("if"(b,c(b,a),a[-1])),scan())

Try it online!

Heavily inspired by digEmAll's answer.

Answer 19

ReRegex, 19 bytes

[^0,]\d*,0,//#input

Very simple solution, Looks for a non-zero number, followed by a zero, and removes both of them.

Takes input in the form of ,1,2,3,

Try it online!

Test Battery

Answer 20

MathGolf, 7 bytes

Æ_╜Å;;]

Try it online!

Explanation

I wish I could do something clever to save a byte, it seems as if it should be possible.

Æ        For-each over the input with the next 5 operators
 _       Duplicate TOS
  ╜      Else without if, executes the next block if TOS is false
   Å;;   Discard two elements
      ]  Wrap everything in array

This answer has the opposite order compared to the examples in the challenge.

Answer 21

Rust, 66 bytes

Takes a vector and returns a vector. The head of the stack comes last in the output.

|l|{let mut r=vec!();for&e in&l{if e>0{r.push(e)}else{r.pop();}}r}

Try It Online

Answer 22

Vyxal W, 6 bytes

0\_VṄĖ

Try it Online!

-2 thanks to Aaron Miller

Answer 23

Charcoal, 12 bytes

ＦＡ¿ι⊞υι¬⊟υＩυ

Try it online! Link is to verbose version of code. Explanation:

ＦＡ

Loop over the input list.

¿ι

Test for zero.

⊞υι

If non-zero, push to the predefined empty list.

¬⊟υ

Otherwise pop the value, and ignore it by taking the logical negation which is always zero and therefore prints an empty line.

Ｉυ

Print each element of the list on its own line.

Answer 24

Ruby, 53 bytes

l=[];gets.split.map{|s|a=s.to_i;a>0?l<<a:l.pop};$><<l

The input needs to be separated by spaces. I'm working on a solution with gsub, but it does not re-run matching when it gets to the end. I would be happy if someone could help me fix this:

gets.gsub(/\d+ 0\s*/,'')

Answer 25

Small Basic, 218 bytes

A Script that takes input as a series of integers and outputs to the TextWindow object.

Note, terminal "s are not required for code to function and do not contribute to the bytecount.

n=" "
x=""
While n<>""
If n=0Then 
k=Stack.PopValue(x)
Else 
Stack.PushValue(x,n)
EndIf
n=TextWindow.Read()
EndWhile
o=Stack.PopValue(x)
k=Stack.GetCount(x)
For i=2To k
o=o+","+Stack.PopValue(x)
EndFor
TextWindow.Write(o)

Try it at SmallBasic.com! Requires IE/Silverlight

-8 bytes thanks to @OMᗺ for removing [ and ]

Input / Output

Answer 26

Retina, 13 bytes

Takes the input list separated by newlines.

+0`\b\d+¶0¶?

Try it online!

Repeatedly remove the first occurrence of a number followed by a zero. Stack is returned upside-down.

Reversing the order of the lines is 4 more bytes (add to end of program). To avoid a possible leading newline, surround the input with newlines, similar to how the input in the examples uses brackets.

G^`

Answer 27

Octave, 56 bytes

s=[];for i=input(''),if i,s=[i s];else s(1)=[];end,end,s

Try it online!

Implementation is simple. Create an empty stack / array s, then declare a list of values (i.e. [12, 3, 0, 101, 11, 1, 0, 0, 14, 0, 28]), iterate through each element and if the element is non-zero, simply place the element at the front. Otherwise, remove the first value inside the stack. Once we're done, show the result to the screen.

Answer 28

PHP (>=5.4), 68 66 bytes

(-2 bytes by fixing a condition, thanks to Titus)

<?for(;null!=$n=$argv[++$i];)$n?$a[]=$n:array_pop($a);print_r($a);

To run it:

php -n <filename> <int_1> <int_2> ... <int_n>

Example:

php -n stack.php 12 3 0 101 11 1 0 0 14 0 28

Or Try it online!

Using r option per Titus's suggestion, this can be counted as 64 bytes:

Example:

php -nr "for(;null!=$n=$argv[++$i];)$n?$a[]=$n:array_pop($a);print_r($a);" 12 3 0 101 11 1 0 0 14 0 28

Answer 29

Bash, 81 , 50 bytes

for i;{ ((i))&&o+=($i)||unset o[-1];};echo ${o[@]} 

Try it online!

Packed in function because, tio doesn't show output without it for some reason.

Answer 30

Java 8, 65 bytes

flexible output permitting... the output stack is stored in the input array, with zero or more terminating -1 values

a->{int x=0,y=0;for(int e:a){a[y++]=-1;a[e>0?x++:--x]=e>0?e:-1;}}

all the remaining numbers on the stack are placed at the front of the array. Reaching -1 in the array indicates the end of the stack.