44
\$\begingroup\$

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]
\$\endgroup\$
  • 12
    \$\begingroup\$ It should be noted that, given the conditions, one does not actually need to implement the stack. \$\endgroup\$ – Jeff Zeitlin Jul 27 '18 at 11:35
  • \$\begingroup\$ If you wanted someone to actually implement a stack, you might need to try putting something in the Sandbox. \$\endgroup\$ – mbomb007 Jul 27 '18 at 16:33
  • \$\begingroup\$ @mbomb007: Either is allowed: "your choice where the top element will be (at the beginning or end)" \$\endgroup\$ – ბიმო Jul 27 '18 at 16:49
  • \$\begingroup\$ @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? \$\endgroup\$ – ბიმო Jul 27 '18 at 16:57
  • \$\begingroup\$ @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. \$\endgroup\$ – mbomb007 Jul 27 '18 at 18:10

76 Answers 76

1
\$\begingroup\$

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!

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

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'()))

Try it Online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Jo King Aug 15 '18 at 7:27
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

Ahead, 23 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Common Lisp, 54 bytes

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

Ultra-straightforward implementation!

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

Python 2, 65 bytes

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

Try it online!

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

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

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – Alexis Facques Jul 27 '18 at 12:17
  • 2
    \$\begingroup\$ @AlexisFacques 44 bytes: a=>a.reduce((r,i)=>i?[i,...r]:r.slice(1),[]) \$\endgroup\$ – Neil Jul 27 '18 at 12:24
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ You place the language and byte code in your actual answer, not in the comments. \$\endgroup\$ – rayryeng Jul 28 '18 at 7:55
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – ბიმო Jul 28 '18 at 9:23
  • 1
    \$\begingroup\$ @OMᗺ That's because the answer requires a negative integer to indicate EOF (I believe you permitted this in the spec). \$\endgroup\$ – O.O.Balance Jul 28 '18 at 10:02
  • \$\begingroup\$ 94 bytes: bit.ly/2uRGQmj \$\endgroup\$ – O.O.Balance Jul 28 '18 at 10:12
  • \$\begingroup\$ 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. \$\endgroup\$ – ბიმო Jul 28 '18 at 11:12
0
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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]
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.