Introdução

Uma fila é um tipo de dados abstrato em que os elementos são adicionados à frente (enfileiramento) e removidos da parte traseira (desenfileiramento). Isso também é conhecido como princípio FIFO (primeiro entrar, primeiro a sair) .

É melhor mostrado com um exemplo:

Desafio

Dada uma matriz não vazia que contém números inteiros positivos e elementos que indicam uma desenfileiramento (remoção de um elemento), produza a lista final da fila.

Digamos que Xdenote uma desenfileiramento neste exemplo. Vamos dar uma olhada na seguinte lista:

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

Isso pode ser traduzido para o seguinte pseudo-código da fila:

                   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

Você pode ver que, no final, o resultado é [85, 97]qual é a saída dessa sequência.

Casos de teste

Observe que você pode escolher qualquer outro símbolo ou caractere X, desde que não seja um número inteiro positivo.

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

Isso é código-golfe , então a submissão com a menor quantidade de bytes ganha!

Geléia , 8 bytes

F;@Ṗṛ?¥/

Usa qualquer valor falso ( 0 ou iterável vazio) para desenfileirar.

Experimente online!

Como funciona

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.

Python 2, 56 53 50 bytes

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

Experimente Online!

Retirar da fila é -1. Esse truque permite o fatiamento pitônico fácil da fila.

Mathematica, 102 bytes

Definitivamente não é a solução mais curta, mas não pude resistir porque é meio perversa.

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

Após algumas funções auxiliares, isso define uma função pura que recebe uma string como entrada: na string, os números são separados por vírgulas (o espaço em branco é opcional); o caractere de desenfileiramento é"]" ; e a lista não possui delimitadores na frente ou atrás. Por exemplo, o primeiro exemplo no OP seria inserido como a string "45,],],37,20,],97,],85". A saída da função é uma lista de números.

A função conta quantas linhas de fila "]"estão na sequência de entrada, anexa quantas cópias "f["à frente da sequência e, em seguida, envolve a coisa toda "r[...]". No exemplo acima, isso produz"r[f[f[f[f[45,],],37,20,],97,],85]" ; observe que os colchetes estão equilibrados.

Em seguida, ToExpressioninterpreta a sequência resultante como um pedaço do código do Mathematica e a executa. A função fé convenientemente definida para reter todos os seus argumentos, exceto o primeiro (e também ignora vírgulas à direita; isso é necessário para remover a fila de filas vazias de qualquer maneira) e rconverte a sequência de números resultante em uma lista de números na ordem correta.

Retina , 30 bytes

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

Experimente online!

Remove repetidamente o primeiro número que é (não necessariamente imediatamente) seguido por um Xjunto com isso X, ou um Xno início da string. Em seguida, inverte os números restantes.

JavaScript, 70 63 53 50 43 bytes

Obrigado @ Neil por jogar 10 bytes com x.map em vez de loop e expressão ternária

Obrigado @Arnauld por jogar fora 3 bytes

Obrigado @ETHproductions por jogar fora 7 bytes

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

Experimente online!

Retirar da fila pode ser qualquer valor não numérico que não seja verdadeiro.

Mathematica, 46 45 bytes

Obrigado a ngenisis por economizar 1 byte.

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

Basicamente, o mesmo que a minha resposta Retina, usando a correspondência de padrões. Combinamos repetidamente o primeiro Xe o removemos junto com o primeiro número (se houver). Depois que terminamos, invertemos a lista.

Pure Bash, 72

Entrada fornecida como parâmetros da linha de comandos.

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

Experimente online .

Haskell, 41 bytes

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

MATL , 13 12 bytes

vi"@?@wh}IL)

Entrada é uma matriz de números, com 0 para "desenfileirar".

Saída é números separados por espaços. Um resultado vazio é mostrado como nada.

Experimente online! Ou verifique todos os casos de teste .

Explicação

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

A função é foldl(#)[](também incluída no bytecount com um byte de separação entre eles)

Experimente online!

X é qualquer número inteiro não positivo

EDIT: -1 byte graças a nimi

Julia, 78 76 73 57 bytes

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

Agradecemos a Harrison Grodin por algumas excelentes sugestões de golfe para Julia. Substituído if / else por ternário e por / end com compreensão de lista para uma economia de 16 bytes.

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

Removidos alguns espaços desnecessários para economizar 3 bytes.

Antes de números negativos ou zero serem permitidos:

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

Eu sou bastante novo para Julia; pode haver uma maneira melhor. Usa :Xpara X, que é um símbolo em Julia. Atualizado: agora que 0 é permitido, usa 0 (ou qualquer número negativo) para X, salvando dois caracteres. Atualizado novamente para remover alguns espaços em branco que eu não sabia que não eram necessários.

05AB1E , 12 11 bytes

Guardou um byte graças a Riley

)Evyai¨ëy¸ì

Experimente online!

Explicação

Os desenfileiramentos são indicados por qualquer letra .

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

A pontuação inclui +2 para uso dos sinalizadores -re -n.

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

Experimente online .

Explicação

                            # 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 em $vvez de is_int($v)se todo valor de desenfileiramento pertencer a 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])

Experimente online!

Também 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 de código + -psinalizador.

/\d/?$\=$_.$\:$\=~s/.*
$//}{

Experimente online!

Ele usa uma string ( $\) como a fila: quando a entrada contém um número inteiro ( /\d/?, nós o anexamos no início de $\( $\=$_.$\), caso contrário, removemos o último com s/.*\n$//. No final, $\é implicitamente impresso graças à -pflag (e aqueles incomparáveis}{ ).

Outras abordagens:

• 33 bytes , usando uma matriz como a fila (é a maneira mais natural de fazê-lo em Perl, mas não a mais curta):

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

  Experimente online!

• 52 bytes , usando regex e reverse(acontece exatamente a mesma coisa que a resposta Retina de Martin Ender - graças a quem eu salvei 2 bytes nele). A reversão da lista exige muitos caracteres, porque, para preservar os números inteiros, tenho que converter a string em uma matriz para revertê-la e depois voltar a uma string para imprimi-la. (em say forvez de $_=join$",pode salvar 2 bytes, mas requer -Eou-M5.010 e não é tão interessante).

  s/\d+ (.*?)X ?|^X/$1/&&redo;$_=join$",reverse split

  Experimente 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 pode ser qualquer valor não numérico.

Experimente online

Lote, 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%

Isso foi mais difícil do que precisava ser.

• Embora o Lote possa enumerar o resultado da divisão de uma string, ele não pode remover facilmente um elemento da enumeração.
• Ele pode remover o primeiro item, mas apenas se houver pelo menos um item. Caso contrário, você recebe lixo.

Isso significa que eu a) preciso ter um marcador de fim de fila, que não seja removido eb) preciso manipular a fila de trás para frente, para que novos itens sejam inseridos logo antes do marcador final, para que os itens antigos possam ser removidos da frente, o que significa que eu c) tenho que inverter a fila antes de imprimi-la.

PHP, 70 bytes

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

C #, 115 bytes +33 bytes para usar

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

Método anônimo que retorna uma lista de números inteiros após executar as operações de enfileiramento e desenfileiramento. Inteiros negativos são usados ​​para remover elementos da fila.

Programa completo com método não destruído e casos de teste:

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}

Como entrada, frecebe uma lista com 0o elemento "desenfileirar". Utiliza recursão de cauda com um segundo parâmetro ( b), atuando como um acumulador. Inicialmente, bé o vazio Seq(Nil ).

Explicações:

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

Nota: b dropRight 1 é usado em vez de b.tailevitar a exceção:tail of empty list .

Casos de teste :

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)

ftambém pode trabalhar com outros tipos ( String, char..., mesmo lista heterogênea desses tipos!):

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

Pega uma sequência separada por espaços, imprime uma sequência separada por espaços

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 indica uma desenfileiramento.

Experimente online!

Swift 3, 70 bytes

Supondo que temos uma matriz de Ints como let x = [1, 2,-1,3,-1,4]

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

Observe que [].prefix(0)é uma maneira sorrateira de obter um ArraySlice vazio