When integers join the queue

Question

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 code-golf, so the submission with the least amount of bytes wins!

Answer 1

Python 2, 56 53 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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

JavaScript, 70 63 53 50 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.

Answer 6

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.

Answer 7

Pure Bash, 72

Input given as command-line parameters.

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

Try it online.

Answer 8

Haskell, 41 bytes

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

Answer 9

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

Answer 10

Julia, 78 76 73 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.

Answer 11

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.

Try it online! Or verify all test cases.

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)

Answer 12

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

Answer 13

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

Try it online.

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

Answer 14

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

Answer 15

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

Answer 16

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!

Answer 17

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

Answer 18

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.

Answer 19

PHP, 70 bytes

foreach($argv as$v)+$v?$r[]=$v:array_shift($r);krsort($r);print_r($r);

Answer 20

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));
    }
}

Answer 21

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, !)

Answer 22

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

Answer 23

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!

Answer 24

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.

Answer 25

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

Answer 26

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

Answer 27

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.

Answer 28

Zsh, 46 bytes

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

Try it online!

Answer 29

Julia 0.7, 41 bytes

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

Try it online!