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 & [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]

• 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

Lua, 115 bytes

t,a,s=table,arg,{}for i=1,#a do v=0+a[i]if v>0 then t.insert(s,1,v)else t.remove(s,1)end end print(t.concat(s,","))


quite simple iterates the arguments pushes and pops them to a table

Try it online!

• You might want to add a TIO-link, I have no idea how to test this. – ბიმო Aug 1 '18 at 12:08
• Added a try it online link, sorry for the inconvenience I forget it most of the time :) – Lycea Aug 1 '18 at 12:19

Scheme, 115 bytes

Like all lisp variants, scheme is based around linked lists. Linked Lists are often used to implement stacks. So I thought scheme might be a competitive language for this challenge. However, I failed to find a way to leverage Scheme's easily accessible built-ins for stack building to overcome Scheme's sheer verbosity. I love scheme, but sometimes its just too long...

(define(g c)(define(f l s)(cond((null? l)s)((= 0(car l))(f(cdr l)(cdr s)))(else(f(cdr l)(cons(car l)s)))))(f c'()))


Lua, 99 Bytes

I started looking for improvements for this answer, but ended with a solution that I find sufficently different to be an answer on its own.

As usual, you can Try it online!

It takes input as a list of arguments, and outputs each number separated by commas. The top of the stack (first element to pop()) is the last one printed

r={}for i=1,#arg
do
a=arg[i]+0s=a>0 and a or x
r[#r+(s and 1or 0)]=s
end
print(table.concat(r,","))


Ungolfed

r={}          -- Define our output array
for i=1,#arg  -- iterate over the argument
do
a=arg[i]+0    -- shorthand for the current argument, add 0 to coerce it into a number
s=a>0         -- s define the operation to do in the current loop
and a     -- if a>0, then s=a
or x        -- else, s=x, x isn't initialiazed, so it's equivalent to s=nil

r[#r+         -- modify the end of the array
(s          -- if s is true (which means not nil)
and 1   -- add 1 to the current index to perform a push
or 0)]    -- else, let it alone, which means we overwrite the last value of the table
=s          -- attrib s to that index

--[[
if s is nil, it gives us, ungolfed, r[r.length+0]=nil, which erase the last value we have
if s is a number, it's equivalent to r[r.length+1]=arg[i], or table.push(r, arg[i])
]]
end

print(table.concat(r,",")) -- outputs the table separating each element by commas

• 97 bytes. I think you could also save bytes by using an anonymous function with loadstring, but that's up to you if you want that – Jo King Aug 15 '18 at 7:27

Prolog (SWI), 47 bytes

R-L:-append(A,[_,0|T],L),append(A,T,M),R-M;R=L.


Try it online! Call as output-input.

Explanation

R-L:-
append(A,[_,0|T],L),                       % if list contains _,0
append(A,T,M),R-M;     % then remove it and recurse
R=L. % else we're done, output = input


~\$k*2!:Ivj~
~oNO@k!d<~#


Try it online!

Dart, 69 bytes

f(l){var m=[];l.forEach((n){n>0?m.add(n):m.removeLast();});return m;}


Alternative

f(l,{m=List}){l.forEach((n){n>0?m.add(n):m.removeLast();});return m;}

Try it online!

Naive answer until I find a better way.

Common Lisp, 54 bytes

(let(s)(dolist(x(read)s)(if(= 0 x)(pop s)(push x s))))


Ultra-straightforward implementation!

Try it online!

Burlesque - 27 bytes

%f={Jz?{vvvv}if}ps(%f!)[]e!


But this is rather bad to be honest. Anyway:

%f={Jz?{vvvv}if}             defines f
ps           parse
(%f!)      quoted call to f
[]    intersperse
e!  eval


This essentially inserts a call to f between the numbers.

J            duplicate
z?          zero?
{vvvv}    pop two elemnets
if  if


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

Python 2, 65 bytes

def f(p,s=[]):
for i in p:
if i:s+=i,
else:s.pop()
return s


Try it online!

• Actually, when written this way the function is non-reusable. – user202729 Jul 27 '18 at 13:29
• @user202729 What does non-reusable mean? – Beta Decay Jul 27 '18 at 13:32
• codegolf.meta.stackexchange.com/questions/4939/… – user202729 Jul 27 '18 at 13:34
• @user202729 Oh, I didn't realise – Beta Decay Jul 27 '18 at 13:38

JavaScript (Node.js), 63 bytes

a=>{let b=[];a.map(x=>x?b.push(x):b.pop());return b.reverse();}


Try it online!

Can probably be improved

• 49 bytes in right order a=>a.reduce((r,i)=>i?[i].concat(r):r.slice(1),[]). Reverse order I see nothing beating @Shaggy's answer – Alexis Facques Jul 27 '18 at 12:17
• @AlexisFacques 44 bytes: a=>a.reduce((r,i)=>i?[i,...r]:r.slice(1),[]) – Neil Jul 27 '18 at 12:24

JavaScript (ES6), 44 bytes

This code works directly on the original array rather than creating a new one. This is however longer than @Shaggy's answer.

a=>a.reverse(x=0).filter(n=>n?x?!x--:1:!++x)


Try it online!

Python 3, 186 bytes

l = list()
while True:
one = int(input())
if one<0:
break
elif one==0:
if len(l)>0:
l.pop()
else:
l.append(one)

l.reverse()
print(l)


Try it online!

• You place the language and byte code in your actual answer, not in the comments. – rayryeng Jul 28 '18 at 7:55
• Welcome to PPCG! This seems to be erroring. Also you need to add a byte-count and provide the language name in the answer itself. – ბიმო Jul 28 '18 at 9:23
• @OMᗺ That's because the answer requires a negative integer to indicate EOF (I believe you permitted this in the spec). – O.O.Balance Jul 28 '18 at 10:02
• 94 bytes: bit.ly/2uRGQmj – O.O.Balance Jul 28 '18 at 10:12
• Ah that works! Yes, I did indeed. I took the freedom of editing the answer, if you're not happy with my edit, feel free to format it differently (however language name and byte-count should still be present) and incorporate the suggested golfs. – ბიმო Jul 28 '18 at 11:12

Python 3, 60 bytes

def f(L,r=[]):
for n in L:r=[n]+r if n else r[1:]
return r


Try it online!

Pepe, 57 bytes

rrEEReRerEerEEEEerEERrERREeEreErEEEEereeRrErEEReEEReeEree


Try it online!

Requires the input to end with -1. Note that "Separated by" option must be enabled. You might prefer to change the separator to , (it's a ; by default). Also, putting ,-1 on a newline might help you not accidentally remove the ,-1, preventing infinite loops and browser crashes.

Explanation

Text in brackets [] are values taken from the stack, r is the control-flow stack, R is the data stack

# prepare (11 bytes)
rrEE           # Define [implicit 0] as
Re Re          # Double pop from R
rEe            # Return

# main (29 bytes)
rEEEEe         # Decrement [implicit 0], always returns -1
rEE            # Create label [-1]
RrE            # Prepend 0 to r
RREeE          # Prepend input to R
reE            # Execute 0 (double pop) if [input] was 0
rEEEEe         # Decrement [0] in r, always returns -1
ree           # If [input] wasn't -1, goto label -1

# output (17 bytes)
RrE           # Prepend 0 to r
rEE           # Create label [0]
ReEE ReeE     # Output [pop R] and a newline
ree           # If there's anything on the stack (non-zero), goto [0]


Scala, 61 bytes 48 bytes

(Seq[Int]()/:z)((z,b)=>if(b!=0)b+:z else z.tail)


Usage in the REPL

val z = Seq(1,2,3,4,0,3,2,5,0,1)

(Seq[Int]()/:z)((z,b)=>if(b!=0)b+:z else z.tail)

res0: Seq[Int] = List(1, 2, 3, 3, 2, 1)


Uses shorthand .foldLeft notation/: and .tail for popping items.