# 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? Mar 31, 2017 at 22:55
• @Riley Sure, whatever works best for you Mar 31, 2017 at 22:56
• Can we use a negative number for x (Haskell doesn't support heterogeneous lists) Apr 1, 2017 at 1:05
• ...or other non-non-negative integers like zero or a half? Apr 1, 2017 at 2:41
• @GenericDisplayName Hmm, good point. I'll allow it as long it's not a positive integer Apr 1, 2017 at 8:05

# 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?) Apr 7, 2017 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. Apr 7, 2017 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. Apr 9, 2017 at 2:37

# 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. Apr 1, 2017 at 11:04
• That's not what it said when I posted my answer, but thank for the heads up. Apr 1, 2017 at 13:44

# 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, 2017 at 23:42
• I had posted the first version I got working. Then I ate dinner :P Mar 31, 2017 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 Apr 1, 2017 at 0:01
• x=>x.map(a=>a>0?t.unshift(a):t.pop(),t=[])&&t is even shorter.
– Neil
Apr 1, 2017 at 0:02
• (Or just a? suffices, I guess?)
– Neil
Apr 1, 2017 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 Apr 1, 2017 at 1:35
• (Although you need parentheses around the y:z like x&(y:z) Apr 1, 2017 at 1:53
• It works in my REPL which is part of hugs. I'm not sure of the exact version though. Apr 1, 2017 at 2:31

# 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, 2017 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.

# 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)


# 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! ## 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 ## 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() Jul 28, 2020 at 21:14 # Ruby, 65 54 bytes q=[];(eval$*[0]).each{|i|q=[i]+q;q=q[1..-2]if i<0};p q


The separator can be any negative number.

• Welcome to the site, and nice first answer! Mar 10, 2021 at 20:01

# Python 2, 58 bytes

def f(x,r=[]):
for i in x:r=i and[i]+r or r[:-1]
print r


Try it online!

Uses 0 as a dequeue value

-10 bytes thanks to pxeger

• Mar 11, 2021 at 14:34
• @pxeger Very nice, thanks! Mar 11, 2021 at 14:36

# K (ngn/k), 18 17 bytes

-1 byte from @ngn

(){$[y;y,;-1_]x}/  Try it online! Uses 0 as the dequeue element. • (){...}/ set up a reduction seeded with () (an empty list), over the (implicit) input • $[...]x apply x (the queue) to the result of $[] (cond) • $[y;y,;-1_] depending on the new value (i.e. if it is 0 or isn't), return a function projection either prepending the new value (y,), or dequeuing the last element (-1_)
• $[~y;-1_;y,] -> $[y;y,;-1_] ?
– ngn
Mar 18, 2021 at 10:59

# Zsh, 46 bytes

for a (<&0)$a&&{shift -p;:}||set$a $@ <<<$@


Try it online!

# J, 18 bytes

(*@[;@{}:@];,)/@|.


Try it online!

• (...)/@|. Reverse and reduce by verb in parens...
• }:@];, Create the two options (regular vs deque, represented by 0) as a boxed pair: left elm is the deque case (ie, accumlator with tail removed }:@]) and right elm is the normal case (new elm appended as head ,).
• (*@[...{ Pick the correct case, which is the signum of the left argument in the reduction *@[, from our boxed pair {...
• ;@ And unbox it.

# Julia 0.7, 41 bytes

!a=(q=[];a.|>i->q=i>0?[i;q]:q[1:end-1];q)


Try it online!