When integers join the queue

Introduction

A queue is an abstract data type where elements are added to the front (enqueue) and removed from the back (dequeue). This is also known as the FIFO (First In First Out) principle.

It is best shown with an example:

Challenge

Given a non-empty array that contains positive integers and elements that indicate a dequeue (removing an element), output the final list of the queue.

Let's say that X denotes a dequeue in this example. Let's take a look at the following list:

[45, X, X, 37, 20, X, 97, X, 85]


This can be translated to the following queue-pseudo code:

                   Queue
Enqueue 45    ->   45
Dequeue       ->
Dequeue       ->              (dequeue on an empty queue is a no-op)
Enqueue 37    ->   37
Enqueue 20    ->   20 37
Dequeue       ->   20
Enqueue 97    ->   97 20
Dequeue       ->   97
Enqueue 85    ->   85 97


You can see that in the end, the result is [85, 97], which is the output for this sequence.

Test cases

Note that you may choose any other symbol or character for X, as long as it's not a positive integer.

[1, X, 2, X, 3, X]      ->     []
[1, 2, X]               ->     [2]
[1, 2, 3]               ->     [3, 2, 1]
[1, 2, X, X, X, 3]      ->     [3]
[1, 2, X, 3, X, 4]      ->     [4, 3]


This is , so the submission with the least amount of bytes wins!

• Can it be a space separated string Instead of an array? – Riley Mar 31 '17 at 22:55
• @Riley Sure, whatever works best for you – Adnan Mar 31 '17 at 22:56
• Can we use a negative number for x (Haskell doesn't support heterogeneous lists) – Generic Display Name Apr 1 '17 at 1:05
• ...or other non-non-negative integers like zero or a half? – Jonathan Allan Apr 1 '17 at 2:41
• @GenericDisplayName Hmm, good point. I'll allow it as long it's not a positive integer – Adnan Apr 1 '17 at 8:05

Jelly, 8 bytes

F;@Ṗṛ?¥/


Uses any falsy value (0 or empty iterable) to dequeue.

Try it online!

How it works

F;@Ṗṛ?¥/  Main link. Argument: A (array)

/  Reduce A by the link to the left.
¥     Combine the two links to the left into a dyadic chain.
F             Flatten the left argument.
ṛ?        If the right argument is truthy:
;@             Concatenate the right argument and the flattened left argument.
Else:
Ṗ            Pop; remove the last element of the flattened left argument.
This is why flattening is required, as Ṗ doesn't handle integers
as intended for this challenge.

• Actually it's not forbidden. Only positive integers are forbidden, 0 is neutral. – Erik the Outgolfer Apr 1 '17 at 11:04
• That's not what it said when I posted my answer, but thank for the heads up. – Dennis Apr 1 '17 at 13:44

Python 2, 5653 50 bytes

q=[]
for i in input():q=[[i]+q,q[:i]][i<0]
print q


Try it Online!

Dequeue is -1. This trick allows easy pythonic slicing of the queue.

Mathematica, 102 bytes

Definitely not the shortest solution, but I couldn't resist because it's kind of perverse.

r=Reverse@{##}&
a_~f~b___:=b
f[a_,b___,]:=b
ToExpression[{"r[","f["~Table~StringCount[#,"]"],#}<>"]"]&


After some helper functions, this defines a pure function that takes a string as input: in the string, numbers are separated by commas (whitespace is optional); the dequeue character is "]"; and the list does not have delimiters in the front or back. For instance, the first example in the OP would be input as the string "45,],],37,20,],97,],85". The output of the function is a list of numbers.

The function counts how many dequeues "]" are in the input string, appends that many copies of "f[" to the front of the string, and then surrounds the whole thing by "r[...]". In the example above, this produces "r[f[f[f[f[45,],],37,20,],97,],85]"; notice the brackets are balanced.

Then, ToExpression interprets the resulting string as a piece of Mathematica code and executes it. The function f is conveniently defined to retain all its arguments except the first (and also ignores trailing commas; this is necessary to handle dequeueing empty queues anyway), and r converts the resulting sequence of numbers into a list of numbers in the right order.

• Is the comma in line 3 at b___, meant to be there? It works, but the comma turns red because of it. (also, what's the difference between lines 2 and 3?) – numbermaniac Apr 7 '17 at 7:39
• Good eye :) Line 2 is equivalent to f[a_,b___]:=b (without the comma), while line 3 is equivalent to f[a_,b___,Null]:=b. In both cases, b___ refers to any number of arguments (including none at all). Line 3 is more specific, so is always used before line 2 when appropriate. So the function f ignores its first argument, and also ignores its last argument if that argument is Null. This was necessary to handle dequeueing an empty queue. Note that a typical input will yield an expression like r[f[f[f[5,3,],2,],],11], where each comma before ] again denotes a Null. – Greg Martin Apr 7 '17 at 8:00
• Wow, very nice :). By the way, I think it's actually 102 bytes; you may have counted an extra newline character at the end. – numbermaniac Apr 9 '17 at 2:37

Retina, 30 bytes

1+\d+,(.*?)X,?|^X,
$1 O^$\d+


Try it online!

Repeatedly removes the first number that's (not necessarily immediately) followed by an X together with that X, or an X at the beginning of the string. Then reverses the remaining numbers.

JavaScript, 70635350 43 bytes

Thanks @Neil for golfing off 10 bytes with x.map instead of for loop and ternary expression

Thanks @Arnauld for golfing off 3 bytes

Thanks @ETHproductions for golfing off 7 bytes

x=>(t=[],x.map(a=>+a?t=[a,...t]:t.pop()),t)


Try it online!

Dequeue can be any non-numeric value other than true.

• This would be shorter if you used a ternary instead of an if statement, and shorter still if you used map instead of a loop, and even shorter still if you used an expression instead of a block. See the tips. – Neil Mar 31 '17 at 23:42
• I had posted the first version I got working. Then I ate dinner :P – fəˈnɛtɪk Mar 31 '17 at 23:44
• You can do x=>(t=[],x.map(a=>a>0?t.unshift(a):t.pop()),t) to save quite a few bytes on the return – ETHproductions Apr 1 '17 at 0:01
• x=>x.map(a=>a>0?t.unshift(a):t.pop(),t=[])&&t is even shorter. – Neil Apr 1 '17 at 0:02
• (Or just a? suffices, I guess?) – Neil Apr 1 '17 at 0:03

Mathematica, 46 45 bytes

Thanks to ngenisis for saving 1 byte.

Reverse[#//.{_Integer:0,a___,X,b___}:>{a,b}]&


Basically the same as my Retina answer, using pattern matching. We repeatedly match the first X and remove it along with the first number (if one exists). After we're done, we reverse the list.

Pure Bash, 72

Input given as command-line parameters.

for a;{
[ ${a/X} ]&&q=(${a:n++,0} ${q[@]})||((n-=n>0)) } echo${q[@]::n}


Haskell, 41 bytes

x&y:z|y<1=init x&z|w<-y:x=w&z
x&y=x
([]&)

• Ninja'd :) seems like we had the same idea – Generic Display Name Apr 1 '17 at 1:35
• (Although you need parentheses around the y:z like x&(y:z) – Generic Display Name Apr 1 '17 at 1:53
• It works in my REPL which is part of hugs. I'm not sure of the exact version though. – Michael Klein Apr 1 '17 at 2:31

MATL, 13 12 bytes

vi"@?@wh}IL)


Input is an array of numbers, with 0 for "dequeue".

Output is numbers separated by spaces. An empty result is shown as nothing.

Explanation

v        % Concatenate stack contents: gives []. This will grow to represent the queue
i        % Input numeric array
"        % For each entry in the input array
@?     %   If current entry is non-zero
@wh  %     Prepend current entry to the queue
}      %   Else
IL)  %     Remove last element from the queue
%   End (implicit)
% End (implicit)
% Display (implicit)


Haskell, 41 40 Bytes

l#a|a>0=a:l|l>[]=init l|1>0=l


Function is foldl(#)[] (Also included in bytecount with a byte of separation in between)

Try it online!

X is any non-positive integer

EDIT: -1 byte thanks to nimi

• You can flip the last two guards to save a byte: |l>[]=init l|1>0=l – nimi Apr 1 '17 at 6:53

Julia, 787673 57 bytes

f(a)=(q=[];[x<1?q=q[2:end]:push!(q,x)for x=a];reverse(q))


Thanks to Harrison Grodin for some excellent Julia golfing suggestions. Replaced if/else with ternary and for/end with list comprehension for a savings of 16 bytes.

f(a)=(q=[];for x in a if x<1 q=q[2:end]else q=[q...,x]end end;reverse(q))


Removed some unnecessary spaces for a savings of 3 bytes.

Before negative numbers or zero were allowed:

f(a)=(q=[];for x in a if x==:X q=q[2:end] else q=[q...,x] end end;r everse(q))


Ungolfed:

function dequeue(list)
queue = []

for x in list
if x < 1
queue = queue[2:end]
else
queue = [queue..., x]
end
end

reverse(queue)
end


I'm fairly new to Julia; there may be a better way. Uses :X for X, which is a Symbol in Julia. Updated: Now that 0 is allowed, uses 0 (or any negative number) for X, saving two characters. Updated again to remove some whitespace that I didn't realize wasn't needed.

05AB1E, 12 11 bytes

Saved a byte thanks to Riley

)Evyai¨ëy¸ì


Try it online!

Explanation

Dequeues are denoted by any letter.

)             # wrap stack in a list (pushes empty list)
Ev           # for each y in evaluated input
yai        # if y is a letter
¨       # remove the first element of the list
ëy¸ì   # else, prepend y to the list


GNU Sed, 43

Score includes +2 for use of the -r and -n flags.

G
s/X\n( *|(.*)\b\S+ *)$/\2/ s/\n/ / h$p


Explanation

                            # Implicitly read the next line
G                           # append a newline, then the contents of the hold space
s/X\n( *|(.*)\b\S+ *)$/\2/ # If the input was an X, remove it, the newline, and any element at the end s/\n/ / # Otherwise if the input was not an X, it is simply enqueued by removing the newline between it and the rest of the line h # save a copy of the queue to the hold space$p                          # since we're using -n to suppress output at the end of processing each input line, then this explicit print is required in the last line


PHP, 85 Bytes

<?$r=[];foreach($_GET as$v)is_int($v)?array_unshift($r,$v):array_pop($r);print_r($r);


-8 Bytes $v instead of is_int($v)if every dequeue value belongs to false

Python 3, 95 94 bytes

def f(x):q=[];[*map(lambda s:exec(("q.pop(0)"if q else"","q+=[s]")[s!="X"]),x)];print(q[::-1])


Try it online!

Also 94 bytes:

def f(x):q=[];[*map(lambda s:exec((("","q.pop(0)")[q>[]],"q+=[s]")[s!="X"]),x)];print(q[::-1])


Perl 5, 28 + 1 = 29 bytes

28 bytes of code + -p flag.

/\d/?$\=$_.$\:$\=~s/.*
$//}{  Try it online! It uses a string ($\) as the queue: when the input contains an integer (/\d/?, we append it at the beginning of $\ ($\=$_.$\), and otherwise, we remove the last one with s/.*\n$//. At the end, $\ is implicitly printed thanks to -p flag (and those unmatched }{).

Other approaches:

• 33 bytes, using an array as the queue (it's the most natural way to do it in Perl I think, but not the shortest):

/X/?pop@F:unshift@F,$_}{$_="@F"


Try it online!

• 52 bytes, using regex and reverse (it happens to be quite exactly the same thing as Martin Ender's Retina answer - thanks to whom I saved 2 bytes on it). Reversing the list takes a lot of characters though, because to preserve the integers, I have to convert the string to an array to reverse it, then back to a string to print it. (say for instead of $_=join$", can save 2 bytes, but it requires -E or -M5.010 and it's not that interesting).

s/\d+ (.*?)X ?|^X/$1/&&redo;$_=join$",reverse split  Try it online! Python 3, 107 bytes def f(x): r = [] for i in x:exec("try:r.pop(0)\nexcept:8;r+=i,".split(";")[type(i)==int]) return r[::-1]  Dequeuer can be any non-numeric value. Try it online Batch, 160 bytes @set s=. @for %%n in (%*)do @if %%n==X (call set s=%%s:* =%%)else call set s=%%s:~,-1%%%%n . @set t= @for %%n in (%s:~,-1%)do @call set t= %%n%%t%% @echo%t%  This was harder than it needed to be. • Although Batch can enumerate the result of splitting a string, it can't easily remove an element from the enumeration. • It can remove the first item, but only if there is at least one item. Otherwise you get garbage. This means that I a) need to have an end-of-queue marker, which doesn't get removed, and b) have to manipulate the queue back-to-front, so new items get inserted in just before the end marker, so that old items can be removed from the front, which then means I c) have to reverse the queue before printing it. PHP, 70 bytes foreach($argv as$v)+$v?$r[]=$v:array_shift($r);krsort($r);print_r(\$r);


C#, 115 bytes +33 bytes for using

l=>{var r=new List<int>();foreach(var n in l)if(n<0)try{r.RemoveAt(0);}catch{}else r.Add(n);r.Reverse();return r;};


Anonymous method which returns a list of integers after performing the en-queuing and dequeuing operations. Negative integers are used for removing elements from the queue.

Full program with ungolfed method and test cases:

using System;
using System.Collections.Generic;

public class Program
{
static void PrintList(List<int> list)
{
var s = "{";
foreach (int element in list)
s += element + ", ";
if (s.Length > 1)
s += "\b\b";
s += "}";
Console.WriteLine(s);
}

public static void Main()
{
Func<List<int>, List<int>> f =
l =>
{
var r = new List<int>();
foreach (var n in l)
if (n < 0)
try
{
r.RemoveAt(0);
}
catch
{ }
else
r.Add(n);
r.Reverse();
return r;
};

// test cases:
var list = new List<int>(new[]{1, -1, 2, -1, 3, -1});   // {}
PrintList(f(list));

list = new List<int>(new[]{1, 2, -1});  // {2}
PrintList(f(list));

list = new List<int>(new[]{1, 2, 3});   // {3, 2, 1}
PrintList(f(list));

list = new List<int>(new[]{1, 2, -1, -1, -1, 3});   // {3}
PrintList(f(list));

list = new List<int>(new[]{1, 2, -1, 3, -1, 4});    // {4, 3}
PrintList(f(list));
}
}


Scala, 97 bytes

type S=Seq[_];def f(a:S,b:S):S=a match{case h::t=>f(t,if(h==0)b dropRight 1 else h+:b);case _=>b}


As input, f takes a list with 0 as the "dequeue" element. It uses tail-recursion with a second parameter (b), acting as an accumulator. Initially, b is the empty Seq (Nil).

Explanations :

type S=Seq[_]                               // defines a type alias (save 1 byte since Seq[_] is used 3 times)
def f(a: S, b: S): S = {                    // a is the initial list, b is an accumulator
a match {
case h::t =>                        // if a is non-empty
f(t,                            // recursive call to f with 1st parameter as the tail
if (h==0) b dropRight 1     // if h == 0 (dequeue) then remove last element of b,
else h+:b                   // otherwise, just add h at the beginning of b in recursive call
)
case _ => b                         // when the list is empty, return b (final result)
}
}


Note : b dropRight 1 is used instead of b.tail to avoid exception : tail of empty list.

Test cases :

f(Seq(45, 0, 0, 37, 20, 0, 97, 0, 85), Nil)     // List(85, 97)
f(Seq(1, 0, 2, 0, 3, 0), Nil)                   // List()
f(Seq(1, 2, 0), Nil)                            // List(2)
f(Seq(1, 2, 3), Nil)                            // List(3, 2, 1)
f(Seq(1, 2, 0, 0, 0, 3), Nil)                   // List(3)
f(Seq(1, 2, 0, 3, 0, 4), Nil)                   // List(4, 3)


f can also work with other types (String, char, ..., even heterogeneous list of those types!) :

f(Seq(false, '!', "world", 0, "Hello"), Nil)    // List(Hello, world, !)


REXX, 115 bytes

arg n
do while n>''
parse var n m n
if m=X then pull
else queue m
end
o=
do while queued()>0
pull a
o=a o
end
say o


Takes a space-separated string, prints a space separated string

C++, 122 119 bytes

#import<list>
void f(std::list<int>o,std::list<int>&q){for(int i:o)if(i)q.push_front(i);else if(q.size())q.pop_back();}


0 indicates a dequeue.

Try it online!

• Suggest i?q.push_front(i):q.size()?q.pop_back():(void)0 instead of if(i)q.push_front(i);else if(q.size())q.pop_back() – ceilingcat Jul 28 '20 at 21:14

Swift 3, 70 bytes

Assuming we have an array of Ints like let x = [1, 2,-1,3,-1,4]

print(x.reduce([].prefix(0)){(a,i)in return i>0 ?[i]+a:a.dropLast(1)})


Note that [].prefix(0) is a sneaky way to get an empty ArraySlice