Implementing a stack

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 :

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 &  \\ & 3 & [3,12] \\ & 0 &  \\ & 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,0,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] -> 
[12,3,0,101,11,1,0,0,14,0,28] -> [28,101,12]
• It should be noted that, given the conditions, one does not actually need to implement the stack. – Jeff Zeitlin Jul 27 '18 at 11:35
• If you wanted someone to actually implement a stack, you might need to try putting something in the Sandbox. – mbomb007 Jul 27 '18 at 16:33
• @mbomb007: Either is allowed: "your choice where the top element will be (at the beginning or end)" – ბიმო Jul 27 '18 at 16:49
• @mbomb007: It wouldn't be any more difficult if you had to reverse the input, would it? Besides, if you consider the setup as a stack who defines what's the top and what's the bottom and why should one definition be less arbitrary? – ბიმო Jul 27 '18 at 16:57
• @OMᗺ Because the input looks quite a bit like a stack/list/array. Now, the entire challenge is basically remove any number followed by a zero. – mbomb007 Jul 27 '18 at 18:10

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.

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

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.

• 11 bytes and in the right order. – Shaggy Jul 29 '18 at 7:25
• @Shaggy are you planning to post it as your own answer? – Amphibological Jul 29 '18 at 14:25
• TIO is fixed now :-) – ETHproductions Jul 31 '18 at 19:07

Java 10, 837675 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

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.

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.

• 123 bytes: bit.ly/2LEvBXR – O.O.Balance Jul 27 '18 at 12:47
• Why are include guards not included in your total? – Paul Belanger Jul 27 '18 at 12:55
• Because gcc does not require them for this program. If you want to keep them, you can still remove the spaces. But here on PPCG we define a language by its implementation; my golf would thus be C (gcc). – O.O.Balance Jul 27 '18 at 12:58
• Save 1 more byte by replacing else n--; with else--n; – O.O.Balance Jul 27 '18 at 13:11
• Submissions don't necessarily need to be full programs, a function saves you some bytes: Try it online! – ბიმო Jul 27 '18 at 13:34

TIS, 75 bytes

Code:

@0
MOV UP ACC
JGZ U
JLZ Q
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).

Haskell, 51 43 bytes

run s function Try it online

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

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!

âΦε∙GφN²

Run and debug it

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. • Befunge can be a lot more compact then that. 17 bytes – Jo King Aug 1 '18 at 0:39 • @JoKing I've been trying to understand your code all day... now I think I did at last. – Charlie Aug 1 '18 at 12:49 Chip-o, 53 bytes )))))))}v9 ABCDEFGH~8 0123456v~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 0123456v~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. 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! Japt-g, 9 bytes ;®?AiZ:Av Try it online! R+pryr, 44 bytes Reduce(pryr::f("if"(b,c(b,a),a[-1])),scan()) Try it online! Heavily inspired by digEmAll's answer. 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 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. • I don't know MathGolf, but I don't think that ] is necessary. Relevant. – ბიმო Nov 20 '18 at 16:27 • @BMO I'm always unsure on how to interpret that, since MathGolf implicitly joins the stack into a single string. Thus, a stack consisting of [123, 456] would be printed as 123456, which has been used in this answer. I'll ask in the chatroom and try to get some consensus. – maxb Nov 21 '18 at 6:38 • Yeah, I'm not sure about it either. But I would argue that as a function in MathGolf it would be fine (which is most of the time - as here too - fine), however as a full program it's not since it outputs a joined string. – ბიმო Nov 21 '18 at 6:57 • @BMO MathGolf doesn't really have "functions" as of now. I don't know if I'll implement it later. However, the general consensus seems to be that the ] should be included in the byte count, with the reasoning that "The principle that languages are defined by their implementations overrides most others". – maxb Nov 21 '18 at 10:01 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. 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*/,'')
• I can't get it to work with empty input, how does it work? – ბიმო Jul 27 '18 at 13:30
• @OMᗺ I think this should work on empty input and TIO normalizes it to nil for some reason. If you enter a whitespace, it still works. Running in command line should not yield an error I think (I'll check that later). – Peter Lenkefi Jul 27 '18 at 13:36
• @PeterLenkefi You might be able to implement a loop with gsub!, which returns the string if modifications were made and nil otherwise. – benj2240 Jul 30 '18 at 21:58

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
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 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^

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.

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

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
• Anything positive is truthy and there is no negative input -> no need for >0. And you can also run it with php -nr '<code>' <int_1> <int_2> ... <int_n> - without the <? tag. – Titus Jul 28 '18 at 15:31
• But you need NULL!== or it will take zero as end of input. (see your TiO) – Titus Jul 28 '18 at 15:35
• @Titus: Thanks for the tips! Do you have any link to show confirmation that an option like -r <code> can be valid? I'm new to PPCG and am not sure what options and methods I can use for PHP golfing! – Night2 Jul 28 '18 at 15:46
• -r is free; see this thread in meta. You still have to fix the NULL condition. – Titus Jul 28 '18 at 15:55
• The inputs are in string form and '0' is not equal to null as a string. Please see this: Try it online! Not sure why I should use strict comparison in that case. – Night2 Jul 28 '18 at 17:18

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.

• A few tips: 1. A full program would be shorter. 2. in $@ is implicit and can be removed. 3. The if statement can be shortened to ((i))&&o+=($i)||unset o[-1]. – Dennis Jul 29 '18 at 14:56

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.

Clojure, 139 bytes

(defn t[q](loop[c(rest q)n(first q)s '()](if(not(nil? n))(if(= n 0)(recur(rest c)(first c)(rest s))(recur(rest c)(first c)(cons n s)))s)))

Try it online!

Ungolfed

(defn stacktest [col]
(loop [c  (rest col)
n  (first col)
s  '()]
(if (not (nil? n))
(if (= n 0) ; then
(recur (rest c) (first c) (rest s))    ; then - pop
(recur (rest c) (first c) (cons n s))) ; else - push
s)))        ; else

Ruby, 36 bytes

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

Try it online!

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.

F#, 84 bytes

let t v=
let mutable s=List.empty
for i in v do s<-if i=0 then s.Tail else i::s
s

Try it online!

Takes advantage of the fact that in F# a List is a single-linked-list. Popping from the stack just takes the tail of the list (that is, everything after the first element). Pushing to the stack makes the individual value i the head of the list (that is, pre-appends it to the list).

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>